gabatarwa
Na ba da wannan rahoto cikin Turanci a taron GopherCon Russia 2019 a Moscow da kuma cikin Rashanci a wani taro a Nizhny Novgorod. Muna magana ne game da fihirisar bitmap - ƙasa da na kowa fiye da itacen B, amma ba ƙasa da ban sha'awa ba. Rabawa jawabai a wurin taron a cikin Turanci da rubutun rubutu a cikin Rashanci.
Za mu dubi yadda index bitmap ke aiki, lokacin da ya fi kyau, lokacin da ya fi sauran fihirisa muni, kuma a waɗanne lokuta yana da sauri fiye da su; Bari mu ga wane mashahurin DBMSs sun riga sun sami fihirisar bitmap; Mu yi kokarin rubuta namu a Go. Kuma "don kayan zaki" za mu yi amfani da shirye-shiryen dakunan karatu don ƙirƙirar namu ƙwararrun bayanai masu sauri.
Ina fatan cewa ayyukana za su kasance masu amfani da ban sha'awa a gare ku. Tafi!
Gabatarwar
Sannu duka! Karfe shida na yamma kuma duk mun gaji sosai. Babban lokaci don magana game da ka'idar ma'auni mai ban sha'awa, daidai? Kar ku damu, zan sami layuka biyu na lambar tushe nan da can. 🙂
Dukkanin barkwanci a gefe, rahoton yana cike da bayanai, kuma ba mu da lokaci mai yawa. Don haka mu fara.
A yau zan yi magana akan abubuwa kamar haka:
- menene alamomi;
- menene ma'anar bitmap;
- inda aka yi amfani da shi da kuma inda ba a yi amfani da shi da kuma dalilin da ya sa;
- aiwatarwa mai sauƙi a cikin Go da ɗan gwagwarmaya tare da mai tarawa;
- ƴan ƙasa mai sauƙi, amma aiwatar da aiki mai inganci a cikin mai tarawa Go;
- "matsalolin" na ma'anar bitmap;
- aiwatar da data kasance.
To mene ne ma'auni?
Fihirisar ita ce keɓantaccen tsarin bayanai wanda muke kiyayewa da sabuntawa baya ga manyan bayanai. Ana amfani da shi don hanzarta bincike. Idan ba tare da fihirisa ba, bincike na buƙatar shiga cikin bayanan gaba ɗaya (wani tsari da ake kira cikakken scan), kuma wannan tsari yana da sarƙaƙƙiyar algorithmic madaidaiciya. Amma rumbun adana bayanai yawanci suna ƙunshe da ɗimbin bayanai kuma haɗaɗɗiyar layi ta yi jinkirin yawa. Da kyau, za mu sami logarithmic ko akai-akai.
Wannan batu ne mai sarkakiya, mai cike da wayo da sauye-sauye, amma bayan duban shekarun ci gaban bayanai da bincike, zan so in ce akwai wasu hanyoyin da ake amfani da su sosai don ƙirƙirar bayanan bayanan.
Hanya ta farko ita ce a rage matsayi na bincike, tare da rarraba sararin binciken zuwa ƙananan sassa.
Yawancin lokaci muna yin haka ta amfani da bishiyoyi iri-iri. Misali zai zama babban akwati na kayan a cikin kabad ɗinku wanda ya ƙunshi ƙananan akwatunan kayan da aka raba zuwa batutuwa daban-daban. Idan kuna buƙatar kayan, ƙila za ku neme su a cikin akwati da ke cewa "Materials" maimakon wanda ya ce "Kukis," daidai?
Hanya ta biyu ita ce nan da nan zabar abin da ake so ko rukuni na abubuwa. Muna yin haka a cikin taswirorin zanta ko jujjuya fihirisa. Yin amfani da taswirorin zanta ya yi kama da misalin da ya gabata, amma maimakon kwalin kwalaye, kuna da tarin ƙananan kwalaye na abubuwa na ƙarshe a cikin kabad ɗinku.
Hanya ta uku ita ce kawar da buƙatar nema. Muna yin wannan ta amfani da matattarar Bloom ko matattarar cuckoo. Na farko suna ba da amsa nan take, suna ceton ku daga yin bincike.
Hanya ta ƙarshe ita ce yin cikakken amfani da duk ƙarfin da kayan aikin zamani ke ba mu. Wannan shine ainihin abin da muke yi a cikin fihirisar bitmap. Ee, lokacin amfani da su wani lokaci muna buƙatar shiga cikin duka fihirisar, amma muna yin shi da kyau sosai.
Kamar yadda na ce, batun jigon bayanan bayanai yana da yawa kuma yana cike da sasantawa. Wannan yana nufin cewa a wasu lokuta muna iya amfani da hanyoyi da yawa a lokaci guda: idan muna buƙatar hanzarta binciken har ma, ko kuma idan muna buƙatar rufe duk nau'ikan bincike mai yuwuwa.
A yau zan yi magana game da mafi ƙarancin sanannun tsarin waɗannan - maƙasudin bitmap.
Wanene zan yi magana kan wannan batu?
Ina aiki azaman jagorar ƙungiyar a Badoo (watakila kun san sauran samfuranmu, Bumble). Mun riga muna da masu amfani sama da miliyan 400 a duk faɗin duniya da fasali da yawa waɗanda ke zabar mafi kyawun wasa a gare su. Muna yin wannan ta amfani da sabis na al'ada, gami da firikwensin bitmap.
To menene ma'anar bitmap?
Fihirisar Bitmap, kamar yadda sunan ke nunawa, yi amfani da bitmaps ko bitsets don aiwatar da fihirisar bincike. Daga kallon idon tsuntsu, wannan fihirisa ta ƙunshi ɗaya ko fiye da irin waɗannan taswirorin da ke wakiltar kowane mahalli (kamar mutane) da kaddarorinsu ko sigogi (shekaru, launi na ido, da sauransu), da algorithm ta amfani da ayyukan bit (DA, KO, BA, BA. ) don amsa tambayar nema.
An gaya mana cewa firikwensin bitmap sun fi dacewa kuma suna yin aiki sosai ga lokuta inda akwai bincike da ke haɗa tambayoyi a cikin ginshiƙan ƙananan ginshiƙai (tunanin "launi na ido" ko " matsayin aure" tare da wani abu kamar "nisa daga tsakiyar gari"). Amma zan nuna daga baya cewa suna aiki da kyau don manyan ginshiƙai kuma.
Bari mu kalli misali mafi sauƙi na fihirisar bitmap.
Yi tunanin cewa muna da jerin gidajen cin abinci na Moscow tare da kaddarorin binary kamar waɗannan:
- kusa da metro;
- akwai filin ajiye motoci masu zaman kansu;
- akwai veranda (yana da terrace);
- za ku iya ajiye tebur (ya yarda da ajiyar kuɗi);
- dace da masu cin ganyayyaki (mai cin ganyayyaki);
- tsada (tsada).
Bari mu ba kowane gidan cin abinci lambar jeri farawa daga 0 kuma mu ware ƙwaƙwalwar ajiya don 6 bitmaps (ɗaya ga kowane hali). Za mu cika waɗannan taswirar bitmaps dangane da ko gidan abinci yana da wannan kayan ko a'a. Idan gidan cin abinci 4 yana da veranda, to bit No. 4 a cikin "yana da veranda" bitmap za a saita zuwa 1 (idan babu veranda, to 0).
Yanzu muna da mafi sauƙin fihirisar bitmap mai yuwuwa, kuma za mu iya amfani da shi don amsa tambayoyi kamar:
- "Nuna mani gidajen cin abinci masu cin ganyayyaki";
- "Nuna mini gidajen abinci marasa tsada tare da veranda inda za ku iya ajiye tebur."
yaya? Mu duba. Buƙatun farko abu ne mai sauqi qwarai. Abin da kawai za mu yi shi ne ɗaukar taswirar "abinci mai cin ganyayyaki" kuma mu juya shi cikin jerin gidajen cin abinci waɗanda raƙuman su ya bayyana.
Buƙatun na biyu ya ɗan fi rikitarwa. Muna buƙatar amfani da taswirar NOT akan bitmap na "tsada" don samun jerin gidajen cin abinci marasa tsada, sannan kuma tare da "zan iya yin littafi" bitmap da kuma sakamakon tare da "akwai veranda" bitmap. Sakamakon bitmap ɗin zai ƙunshi jerin cibiyoyin da suka dace da duk ƙa'idodin mu. A cikin wannan misalin, wannan gidan cin abinci na Yunost ne kawai.
Akwai ka'idar da yawa a ciki, amma kada ku damu, za mu ga lambar nan da nan.
Ina ake amfani da fihirisar bitmap?
Idan ku Google bitmap fihirisa, 90% na amsoshin za su kasance masu alaƙa da Oracle DB ta wata hanya ko wata. Amma wasu DBMSs tabbas suna goyan bayan irin wannan abu mai sanyi, daidai? Ba da gaske ba.
Bari mu shiga cikin jerin manyan wadanda ake zargi.
MySQL har yanzu bai goyi bayan firikwensin bitmap ba, amma akwai shawara da ke ba da shawarar ƙara wannan zaɓi ().
PostgreSQL baya goyan bayan firikwensin bitmap, amma yana amfani da taswirori masu sauƙi da ayyukan bita don haɗa sakamakon bincike a cikin sauran fihirisa da yawa.
Tarantool yana da firikwensin bitset kuma yana goyan bayan bincike mai sauƙi akan su.
Redis yana da sauƙi bitfields) ba tare da ikon neman su ba.
MongoDB har yanzu bai goyi bayan firikwensin bitmap ba, amma akwai kuma shawara da ke ba da shawarar ƙara wannan zaɓin.
Elasticsearch yana amfani da bitmaps a ciki).
- Amma wani sabon maƙwabci ya bayyana a gidanmu: Pilosa. Wannan sabon bayanai ne mara alaƙa da aka rubuta a cikin Go. Ya ƙunshi fihirisar bitmap kawai kuma yana dogara da komai akan su. Za mu yi magana game da shi kadan kadan.
Aiwatarwa a cikin Go
Amma me yasa ba a cika amfani da fihirisar bitmap ba? Kafin amsa wannan tambayar, Ina so in nuna muku yadda ake aiwatar da fihirisar bitmap mai sauƙi a cikin Go.
Bitmaps ainihin guda ne na bayanai. A cikin Go, bari mu yi amfani da yankan byte don wannan.
Muna da taswira guda ɗaya don halayen gidan abinci guda ɗaya, kuma kowane bit a cikin bitmap ɗin yana nuna ko wani gidan abinci yana da wannan kayan ko a'a.
Za mu buƙaci ayyukan mataimaka biyu. Za a yi amfani da ɗaya don cike maps ɗin mu da bayanan bazuwar. Bazuwar, amma tare da wasu yuwuwar cewa gidan abincin yana da kowane kadara. Alal misali, na yi imani cewa akwai ƙananan gidajen cin abinci a Moscow inda ba za ku iya ajiye tebur ba, kuma yana da alama cewa kusan kashi 20% na cibiyoyin sun dace da masu cin ganyayyaki.
Aiki na biyu zai maida bitmap ɗin zuwa jerin gidajen abinci.
Don amsa tambayar "Nuna mani gidajen cin abinci marasa tsada waɗanda ke da baranda kuma za su iya yin ajiyar zuciya," muna buƙatar ayyuka guda biyu: BA da DA.
Za mu iya sauƙaƙa lambar mu kaɗan ta amfani da mafi hadaddun kuma BA mai aiki ba.
Muna da ayyuka ga kowane ɗayan waɗannan ayyukan. Dukansu biyu suna shiga cikin yankan, ɗauki abubuwan da suka dace daga kowannensu, haɗa su tare da ɗan aiki kaɗan kuma sanya sakamakon a cikin yanki da aka samu.
Kuma yanzu za mu iya amfani da bitmaps da ayyukan mu don amsa tambayar nema.
Ayyukan ba haka ba ne, kodayake ayyukan suna da sauƙi kuma mun adana kuɗi da yawa ta hanyar rashin mayar da sabon yanki na sakamakon duk lokacin da aka kira aikin.
Bayan yin ɗan taƙaitaccen bayanin martaba tare da ppprof, na lura cewa mai tarawa Go ya ɓace ɗaya mai sauƙi amma ingantawa mai mahimmanci: aikin inlining.
Gaskiyar ita ce, mai tarawa Go yana da matukar tsoron madaukai da ke ratsa yanki, kuma ya ki yarda da ayyukan layi waɗanda ke ɗauke da irin waɗannan madaukai.
Amma ba na jin tsoro kuma zan iya yaudarar mai tarawa ta hanyar amfani da goto maimakon madauki, kamar a zamanin da.
Kuma, kamar yadda kuke gani, yanzu mai tarawa zai lissafta aikin mu cikin farin ciki! Sakamakon haka, muna gudanar da adana kusan 2 micro seconds. Ba sharri ba!
Ƙaƙwalwar kwalba na biyu yana da sauƙi don ganin idan kun duba da kyau a kan fitowar taron. Mai tarawa ya ƙara duban iyaka a cikin mafi kyawun madauki. Gaskiyar ita ce, Go shine yare mai aminci, mai tarawa yana tsoron cewa gardama na uku (yanki uku) suna da girma dabam dabam. Bayan haka, to, za a sami yiwuwar yiwuwar faruwar abin da ake kira buffer ambaliya.
Bari mu sake tabbatar wa mai tarawa ta hanyar nuna masa cewa duk yankan girmansu ɗaya ne. Za mu iya yin haka ta ƙara dubawa mai sauƙi a farkon aikin mu.
Ganin haka, mai tarawa cikin farin ciki ya tsallake cak ɗin, kuma mun ƙare da adana wasu 500 nanoseconds.
Manyan nama
Da kyau, mun sami nasarar fitar da wasu ayyuka daga aiwatarwa mai sauƙi, amma wannan sakamakon ya fi muni fiye da yadda zai yiwu tare da kayan aikin yanzu.
Duk abin da muke yi shi ne ayyukan bit na asali, kuma na'urori masu sarrafa mu suna yin su da inganci sosai. Amma, abin takaici, muna "ciyar da" na'urar sarrafa mu tare da ƙananan ƙananan aiki. Ayyukanmu suna yin ayyuka akan tsarin byte-by-byte. Za mu iya sauƙi tweak lambar mu don aiki tare da chunks 8-byte ta amfani da yankan UInt64.
Kamar yadda kuke gani, wannan ɗan ƙaramin canji ya haɓaka shirinmu sau takwas ta hanyar ƙara girman batch da sau takwas. Ana iya cewa ribar ta layi ce.
Aiwatar a cikin mai tarawa
Amma wannan ba ƙarshen ba ne. Masu sarrafawa namu na iya aiki tare da chunks na 16, 32 har ma da 64 bytes. Irin waɗannan ayyuka na “faɗaɗɗen” ana kiransu bayanan koyarwa guda ɗaya (SIMD; umarni ɗaya, bayanai da yawa), kuma tsarin canza lambar don yin amfani da irin waɗannan ayyukan ana kiransa vectorization.
Abin takaici, Go compiler yayi nisa da inganci a vectorization. A halin yanzu, hanya ɗaya tilo don tantance lambar Go shine ɗauka da sanya waɗannan ayyukan da hannu ta amfani da Go assembler.
Tafi mai tarawa baƙon dabba ce. Kila ka san cewa yaren taro wani abu ne da ke da alaƙa da gine-ginen kwamfutar da kake rubutawa, amma ba haka lamarin yake ba a Go. Go mai haɗawa ya fi kama da IRL (harshen wakilci na tsakiya) ko tsaka-tsakin harshe: a zahiri mai zaman kansa dandamali ne. Rob Pike ya ba da kyakkyawan aiki akan wannan batu shekaru da yawa da suka gabata a GopherCon a Denver.
Bugu da kari, Go yana amfani da tsarin tsari na 9 wanda ba a saba gani ba, wanda ya sha bamban da tsarin AT&T da Intel gaba daya karbabbe.
Yana da kyau a ce rubuta Go assembler da hannu ba shine mafi daɗi ba.
Amma, an yi sa'a, akwai manyan kayan aiki guda biyu waɗanda ke taimaka mana mu rubuta Go assembler: PeachPy da avo. Dukansu abubuwan amfani guda biyu suna samar da mai tara Go daga lambar matakin da aka rubuta cikin Python da Go, bi da bi.
Waɗannan abubuwan amfani suna sauƙaƙe abubuwa kamar rabon rajista, rubuta madaukai, kuma gabaɗaya suna sauƙaƙe tsarin shiga duniyar shirye-shiryen taro a Go.
Za mu yi amfani da avo, don haka shirye-shiryenmu za su kasance kusan shirye-shiryen Go na yau da kullun.
Wannan shine misalin mafi sauƙi na shirin avo yayi kama. Muna da babban () aiki, wanda ke bayyana a cikin kanta aikin Ƙara (), wanda ma'anarsa shine ƙara lambobi biyu. Akwai ayyuka masu taimako a nan don samun sigogi ta suna kuma samun ɗaya daga cikin rajistar masu sarrafawa masu kyauta kuma masu dacewa. Kowane aikin sarrafawa yana da aikin da ya dace akan avo, kamar yadda aka gani a ADDQ. A ƙarshe, muna ganin aikin mai taimako don adana ƙimar da aka samu.
Ta hanyar kiran go generated, za mu aiwatar da shirin a kan avo kuma a sakamakon haka, za a samar da fayiloli guda biyu:
- add.s tare da lambar da aka samu a cikin Go assembler;
- stub.go tare da kanun labarai na aiki don haɗa duniyoyi biyu: Je da mai tarawa.
Yanzu da muka ga abin da avo yake yi da kuma yadda, bari mu dubi ayyukanmu. Na aiwatar da nau'ikan scalar da vector (SIMD) na ayyukan.
Bari mu fara duba nau'ikan scalar.
Kamar yadda yake a cikin misalin da ya gabata, muna neman rajista na kyauta kuma mai inganci, ba ma buƙatar ƙididdige ƙididdigewa da girma don muhawarar. avo yayi mana wannan duka.
Mun kasance muna amfani da lakabi da goto (ko tsalle) don inganta aiki da yaudarar mai tarawa Go, amma yanzu muna yin shi daga farko. Ma'anar ita ce hawan keke babban ra'ayi ne. A cikin masu tarawa, muna da lakabi da tsalle-tsalle kawai.
Ya kamata lambar da ta rage ta zama saba da fahimta. Muna yin koyi da madauki tare da labels da tsalle-tsalle, ɗaukar ɗan ƙaramin bayanai daga yankanmu guda biyu, haɗa su da ɗan aiki kaɗan (BA a cikin wannan yanayin ba) sannan mu sanya sakamakon a cikin yanki da aka samu. Duka.
Wannan shine yadda lambar mai tarawa ta ƙarshe tayi kama. Ba dole ba ne mu ƙididdige ƙididdigewa da girma (wanda aka haskaka da kore) ko kuma mu ci gaba da lura da rajistar da aka yi amfani da ita (wanda aka yi alama da ja).
Idan muka kwatanta aikin aiwatar da harshen taro tare da aiwatar da mafi kyawun aiwatarwa a cikin Go, za mu ga cewa iri ɗaya ne. Kuma ana sa ran hakan. Bayan haka, ba mu yi wani abu na musamman ba - mun sake buga abin da Go compiler zai yi.
Abin takaici, ba za mu iya tilasta wa mai tarawa yin layi da ayyukanmu da aka rubuta cikin yaren taro ba. Mai tarawa Go a halin yanzu ba shi da irin wannan fasalin, kodayake an sami buƙatar ƙara shi na ɗan lokaci kaɗan.
Wannan shine dalilin da ya sa ba shi yiwuwa a sami wani fa'ida daga ƙananan ayyuka a cikin harshe taro. Muna buƙatar ko dai rubuta manyan ayyuka, ko amfani da sabon kunshin lissafi/bits, ko ƙetare yaren masu tarawa.
Bari yanzu mu kalli nau'ikan ayyukanmu na vector.
Don wannan misali, na yanke shawarar yin amfani da AVX2, don haka za mu yi amfani da ayyukan da ke aiki akan 32-byte chunks. Tsarin lambar ya yi kama da sigar scalar: sigogin lodi, neman rajistar raba kyauta, da sauransu.
Ɗayan ƙirƙira ita ce manyan ayyukan vector suna amfani da faffadan rajista na musamman. A cikin yanayin chunks 32-byte, waɗannan rajistan rajista ne da aka riga aka shigar da Y. Wannan shine dalilin da ya sa kuke ganin aikin YMM() a cikin lambar. Idan ina amfani da AVX-512 tare da 64-bit chunks, prefix zai zama Z.
Bidi'a ta biyu ita ce, na yanke shawarar yin amfani da ingantawa da ake kira loop unrolling, wanda ke nufin yin ayyukan madaukai guda takwas da hannu kafin yin tsalle zuwa farkon madauki. Wannan haɓakawa yana rage yawan rassan da ke cikin lambar, kuma an iyakance shi da adadin rajistar kyauta da ake samuwa.
To, game da wasan kwaikwayo fa? Tana da kyau! Mun sami saurin gudu kusan sau bakwai idan aka kwatanta da mafi kyawun maganin Go. Abin burgewa, dama?
Amma ko da wannan aiwatarwa na iya yuwuwar haɓakawa ta amfani da AVX-512, prefetching ko JIT (mai tarawa kawai) don mai tsara tambaya. Amma tabbas wannan batu ne don wani rahoto na daban.
Matsaloli tare da fihirisar bitmap
Yanzu da mun riga mun duba sauƙaƙe aiwatar da fihirisar bitmap a cikin Go da kuma wanda ya fi dacewa a cikin yaren taro, bari a ƙarshe muyi magana game da dalilin da yasa ba a cika amfani da fihirisar bitmap ba.
Tsofaffin takardu sun ambaci matsaloli guda uku tare da fihirisar bitmap, amma sabbin takardu kuma ina jayayya cewa ba su da mahimmanci. Ba za mu nutse cikin kowane ɗayan waɗannan matsalolin ba, amma za mu dube su da sama.
Matsalar high cardinality
Don haka, an gaya mana cewa firikwensin bitmap sun dace ne kawai ga filayen da ke da ƙarancin kadi, wato, waɗanda ke da ƙima kaɗan (misali, jinsi ko launin ido), kuma dalilin shine wakilcin da aka saba na irin waɗannan filayen (ɗaya ɗaya). bit a kowace ƙima) a cikin yanayin babban kadinanci, zai ɗauki sarari da yawa kuma, haka ma, waɗannan fihirisar taswirar bitmap ba za su cika da kyau ba (da wuya).
Wani lokaci muna iya amfani da wakilci daban, kamar daidaitaccen wanda muke amfani da shi don wakiltar lambobi. Amma zuwan matsawa algorithms ne ya canza komai. A cikin shekarun da suka gabata, masana kimiyya da masu bincike sun fito da adadi mai yawa na matsawa algorithms don bitmaps. Babban fa'idarsu ita ce, babu buƙatar damfara bitmaps don aiwatar da ayyukan bit - za mu iya yin ayyukan bit kai tsaye akan taswirar bitmaps.
Kwanan nan, hanyoyin haɗin gwiwar sun fara bayyana, kamar ruri-ruwan bitmaps. A lokaci guda suna amfani da wakilci daban-daban guda uku don bitmaps - bitmaps kansu, tsararraki da abin da ake kira bit runs - da daidaitawa tsakanin su don haɓaka aiki da rage yawan amfani da ƙwaƙwalwa.
Kuna iya samun taswirar bitmaps masu ruri a cikin shahararrun aikace-aikace. An riga an sami adadi mai yawa na aiwatarwa don nau'ikan shirye-shirye iri-iri, gami da aiwatarwa sama da uku don Go.
Wata hanyar da za ta iya taimaka mana mu magance babban kadinanci ana kiranta binning. Ka yi tunanin kana da filin da ke wakiltar tsayin mutum. Tsayi lamba ce mai iyo, amma mu mutane ba ma tunanin haka. A gare mu babu bambanci tsakanin tsayin 185,2 cm da 185,3 cm.
Sai dai itace cewa za mu iya tara irin wannan dabi'u zuwa kungiyoyi a cikin 1 cm.
Kuma idan kuma mun san cewa mutane kaɗan ne suka fi guntu cm 50 kuma sun fi 250 cm tsayi, to za mu iya da gaske juya filin da ke da Cardinality mara iyaka zuwa filin da ke da kimar darajar kusan 200.
Tabbas, idan ya cancanta, zamu iya yin ƙarin tacewa daga baya.
Matsala mai girma
Matsala ta gaba tare da fihirisar bitmap ita ce sabunta su na iya yin tsada sosai.
Dole ne ma'ajin bayanai su sami damar sabunta bayanai yayin da yuwuwar ɗaruruwan wasu tambayoyi ke neman bayanan. Muna buƙatar makullai don guje wa matsaloli tare da samun damar bayanai na lokaci ɗaya ko wasu matsalolin rabawa. Kuma inda akwai babban kulle guda ɗaya, akwai matsala - jayayya ta kulle, lokacin da wannan makullin ya zama abin ƙyama.
Ana iya magance wannan matsalar ko kuma a kewaye ta ta amfani da sharding ko yin amfani da fihirisar siga.
Sharding abu ne mai sauƙi kuma sananne. Kuna iya share fihirisar bitmap kamar yadda kuke yi da sauran bayanai. Maimakon babban kulle ɗaya, za ku sami gungu na ƙananan makullai don haka ku kawar da jayayyar kullewa.
Hanya ta biyu don magance matsalar ita ce yin amfani da fitattun fitattun bayanai. Kuna iya samun kwafi ɗaya na fihirisar da kuke amfani da ita don bincike ko karantawa, da kuma wanda kuke amfani da shi don rubutawa ko sabuntawa. Kuma sau ɗaya a cikin ƙayyadaddun lokaci (misali, sau ɗaya kowane 100 ms ko 500 ms) kuna kwafi su kuma ku canza su. Tabbas, wannan dabarar tana aiki ne kawai a cikin lamuran da aikace-aikacenku zai iya ɗaukar ma'anar bincike kaɗan.
Ana iya amfani da waɗannan hanyoyi guda biyu a lokaci guda: za ku iya samun fihirisar da aka ƙera.
Tambayoyi masu rikitarwa
Matsala ta ƙarshe tare da firikwensin bitmap ita ce an gaya mana cewa ba su dace da ƙarin hadaddun nau'ikan tambayoyin ba, kamar tafsirin tambaya.
Lalle ne, idan kun yi tunani game da shi, ayyukan bit kamar AND, OR, da dai sauransu ba su dace da tambayoyin ba a la "Nuna mini otal tare da farashin daki daga 200 zuwa 300 daloli a kowace dare."
Magani mara hankali da rashin hikima shine ɗaukar sakamakon kowane darajar dala kuma a haɗa su tare da aiki na bitwise KO.
Magani mafi kyau dan kadan shine amfani da rukuni. Misali, a rukunin daloli 50. Wannan zai hanzarta aiwatar da mu da sau 50.
Amma kuma ana samun sauƙin magance matsalar ta hanyar amfani da ra'ayi da aka ƙirƙira musamman don irin wannan tambaya. A cikin takaddun kimiyya ana kiran sa da kewayo-encoded bitmaps.
A cikin wannan wakilcin, ba wai kawai saita bit ɗaya don wasu ƙima ba (misali, 200), amma saita wannan ƙimar da duk abin da ya fi girma. 200 zuwa sama. Daidai ga 300: 300 da sama. Da sauransu.
Yin amfani da wannan wakilci, za mu iya amsa irin wannan tambayar ta hanyar ketare maƙasudin sau biyu kawai. Da farko, za mu sami jerin sunayen otal ɗin da ɗakin ɗakin ya yi ƙasa da $ 300, sannan za mu cire daga ciki waɗanda farashin ɗakin bai yi ƙasa da $ 199 ba. Shirya
Za ku yi mamaki, amma ko da geoqueries yana yiwuwa ta amfani da fihirisar bitmap. Dabarar ita ce yin amfani da wakilcin geometric wanda ke kewaye da haɗin gwiwar ku tare da adadi na geometric. Misali, S2 daga Google. Adadin ya kamata ya kasance mai yiwuwa a wakilci a cikin nau'i na layi uku ko fiye da ke haɗuwa waɗanda za a iya ƙidaya. Ta wannan hanyar za mu iya juyar da binciken mu zuwa tambayoyi da yawa "tare da rata" (tare da waɗannan layukan ƙididdiga).
Shirye-shiryen da aka shirya
Ina fatan ina sha'awar ku kadan kuma yanzu kuna da wani kayan aiki mai amfani a cikin arsenal. Idan kuna buƙatar yin wani abu kamar wannan, za ku san hanyar da za ku duba.
Koyaya, ba kowa bane ke da lokaci, haƙuri, ko albarkatu don ƙirƙirar firikwensin bitmap daga karce. Musamman mafi ci gaba, ta amfani da SIMD, misali.
Sa'ar al'amarin shine, akwai shirye-shiryen mafita da yawa don taimaka muku.
Bitmaps masu ruri
Na farko, akwai ɗakin karatu na bitmaps guda ɗaya wanda na riga na yi magana akai. Ya ƙunshi duk kwantenan da ake buƙata da ayyukan bita waɗanda za ku buƙaci yin cikakken ma'aunin bitmap.
Abin takaici, a halin yanzu, babu ɗaya daga cikin aiwatar da Go da ke amfani da SIMD, wanda ke nufin cewa aiwatar da Go bai cika aiki ba fiye da aiwatar da C, misali.
Pilosa
Wani samfurin da zai iya taimaka maka shine Pilosa DBMS, wanda, a gaskiya, kawai yana da fihirisar bitmap. Wannan sabon bayani ne, amma yana cin nasara ga zukata cikin sauri.
Pilosa yana amfani da bitmaps masu ruri a ciki kuma yana ba ku ikon amfani da su, sauƙaƙawa da bayyana duk abubuwan da na yi magana a sama: haɗawa, taswirar kewayon bitmaps, manufar filin, da sauransu.
Bari mu yi saurin duba misalin amfani da Pilosa don amsa tambayar da kuka riga kuka saba da ita.
Misalin yayi kama da abin da kuka gani a baya. Mun ƙirƙiri abokin ciniki zuwa uwar garken Pilosa, ƙirƙirar fihirisa da filayen da ake buƙata, sannan mu cika filayenmu da bayanan bazuwar tare da yuwuwar kuma, a ƙarshe, aiwatar da tambayar da aka saba.
Bayan haka, muna amfani da BA akan filin "tsada", sa'an nan mu haɗa sakamakon (ko DA shi) tare da filin "terrace" kuma tare da filin "Reservations". Kuma a ƙarshe, muna samun sakamako na ƙarshe.
Ina fata da gaske cewa a nan gaba wannan sabon nau'in fihirisar zai kuma bayyana a cikin DBMSs kamar MySQL da PostgreSQL - indexes bitmap.
ƙarshe
Idan har yanzu ba ku yi barci ba, na gode. Dole ne in tabo batutuwa da yawa a taƙaice saboda ƙayyadaddun lokaci, amma ina fatan jawabin ya kasance mai amfani kuma watakila ma yana da kuzari.
Fihirisar Bitmap suna da kyau a sani game da su, koda kuwa ba kwa buƙatar su a yanzu. Bari su zama wani kayan aiki a cikin akwatin kayan aiki.
Mun duba dabaru daban-daban na wasan kwaikwayon don Go da abubuwan da mai tarawa Go bai yi da kyau ba tukuna. Amma wannan yana da matuƙar amfani ga kowane mai shirye-shiryen Go ya sani.
Abin da nake so in gaya muku ke nan. Na gode!
source: www.habr.com