Réamhrá
Thug mé an tuarascáil seo i mBéarla ag comhdháil GopherCon Russia 2019 i Moscó agus i Rúisis ag cruinniú i Nizhny Novgorod. Táimid ag caint faoi innéacs bitmap - nach bhfuil chomh coitianta ná B-tree, ach nach lú suimiúil. Roinnt óráidí ag an gcomhdháil i mBéarla agus athscríbhinní téacs i Rúisis.
Breathnóimid ar conas a oibríonn innéacs bitmap, nuair a bhíonn sé níos fearr, nuair a bhíonn sé níos measa ná innéacsanna eile, agus cad iad na cásanna go bhfuil sé i bhfad níos tapúla ná iad; Feicfimid cé na DBMSanna coitianta a bhfuil innéacsanna giotáin acu cheana féin; Déanaimis iarracht ár gcuid féin a scríobh in Go. Agus “do mhilseog” úsáidfimid leabharlanna réamhdhéanta chun ár mbunachar sonraí speisialaithe sár-ghasta féin a chruthú.
Tá súil agam go mbeidh mo shaothair úsáideach agus suimiúil duit. Téigh!
Réamhrá
Dia duit gach duine! Tá sé sé tráthnóna agus táimid go léir thar a bheith tuirseach. Am iontach chun labhairt faoi teoiric innéacs leadránach bunachar sonraí, ceart? Ná bí buartha, beidh cúpla líne de chód foinse agam anseo agus ansiúd. 🙂
Ar aon dul leis sin, tá an tuarascáil lán d’eolas, agus níl mórán ama againn. Mar sin a ligean ar tús a chur leis.
Inniu labhróidh mé faoi na nithe seo a leanas:
- cad is innéacsanna ann;
- cad is innéacs bitmap ann;
- cá n-úsáidtear é agus cá NACH n-úsáidtear é agus cén fáth;
- cur i bhfeidhm simplí i Go agus streachailt beag leis an tiomsaitheoir;
- beagán níos lú simplí, ach cur i bhfeidhm i bhfad níos táirgiúla i Go cóimeálaí;
- “fadhbanna” innéacsanna giotáin;
- feidhmithe reatha.
Mar sin, cad iad innéacsanna?
Is struchtúr sonraí ar leith é an t-innéacs a choinnímid agus a nuashonraímid chomh maith leis na príomhshonraí. Úsáidtear é chun an cuardach a bhrostú. Gan innéacsanna, bheadh gá le dul tríd na sonraí go hiomlán (próiseas ar a dtugtar scanadh iomlán) agus tá castacht algartamaíoch líneach ag baint leis an bpróiseas seo. Ach de ghnáth bíonn méideanna ollmhóra sonraí i mbunachair sonraí agus bíonn castacht líneach ró-mhall. Go hidéalach, gheobhaimid logartamach nó ceann tairiseach.
Is ábhar thar a bheith casta é seo, atá lán le subtleties agus comhbhabhtálacha, ach tar éis breathnú ar na blianta fada d’fhorbairt bunachar sonraí agus taighde, táim sásta a rá nach bhfuil ach cúpla cur chuige a úsáidtear go forleathan chun innéacsanna bunachar sonraí a chruthú.
Is é an chéad chur chuige ná an spás cuardaigh a laghdú go hordlathach, agus an spás cuardaigh á roinnt ina chodanna níos lú.
Déanaimid é seo de ghnáth ag baint úsáide as cineálacha éagsúla crann. Sampla a bheadh ann ná bosca mór ábhar i do closet ina bhfuil boscaí níos lú ábhar roinnte i dtopaicí éagsúla. Má theastaíonn ábhair uait, is dócha go bhféachfaidh tú orthu i mbosca a deir "Ábhair" seachas ceann a deir "Fianáin," ceart?
Is é an dara cur chuige ná an eilimint nó an grúpa eilimintí atá ag teastáil a roghnú láithreach. Déanaimid é seo i léarscáileanna hash nó in innéacsanna droim ar ais. Tá úsáid léarscáileanna hash an-chosúil leis an sampla roimhe seo, ach in ionad bosca boscaí, tá dornán boscaí beaga de mhíreanna deiridh agat i do closet.
Is é an tríú cur chuige ná deireadh a chur leis an ngá atá le cuardach. Déanaimid é seo ag baint úsáide as scagairí Bloom nó scagairí cuach. Tugann an chéad cheann freagra láithreach, rud a shábhálann tú ó bheith ag cuardach.
Is é an cur chuige deireanach ná úsáid iomlán a bhaint as an gcumhacht go léir a thugann crua-earraí nua-aimseartha dúinn. Is é seo go díreach a dhéanaimid in innéacsanna bitmap. Sea, agus iad á n-úsáid ní mór dúinn uaireanta dul tríd an innéacs iomlán, ach déanaimid é thar a bheith éifeachtach.
Mar a dúirt mé, tá ábhar na n-innéacsanna bunachar sonraí ollmhór agus lán de chomhréiteach. Ciallaíonn sé seo gur féidir linn roinnt cur chuige a úsáid ag an am céanna uaireanta: más gá dúinn an cuardach a bhrostú níos mó fós, nó más gá dúinn gach cineál cuardaigh féideartha a chlúdach.
Inniu labhróidh mé faoin gcur chuige is lú aithne díobh seo - innéacsanna bitmap.
Cé mise chun labhairt ar an ábhar seo?
Oibrím mar cheannaire foirne ag Badoo (b'fhéidir go bhfuil tú níos eolach ar ár dtáirge eile, Bumble). Tá níos mó ná 400 milliún úsáideoir ar fud an domhain cheana féin agus go leor gnéithe a roghnaíonn an cluiche is fearr dóibh. Déanaimid é seo trí úsáid a bhaint as seirbhísí saincheaptha, lena n-áirítear innéacsanna giotánmap.
Mar sin, cad is innéacs bitmap ann?
Úsáideann innéacsanna giotánmap, mar a thugann an t-ainm le fios, léarscáileanna giotán nó tacair ghiotán chun innéacs cuardaigh a chur i bhfeidhm. Ó radharc éan, tá an t-innéacs seo comhdhéanta de léarscáil ghiotán amháin nó níos mó den sórt sin a léiríonn aon eintiteas (cosúil le daoine) agus a n-airíonna nó paraiméadair (aois, dath súl, etc.), agus algartam a úsáideann oibríochtaí giotán (AGUS, OR, NOT ) chun an cheist chuardaigh a fhreagairt.
Deirtear linn go bhfuil innéacsanna bitmap is fearr a oireann agus an-fheidhmeach do chásanna ina bhfuil cuardaigh a chomhcheanglaíonn ceisteanna thar go leor colúin cardinality íseal (smaoineamh ar "dath súl" nó "stádas pósta" i gcoinne rud éigin cosúil le "fad ó lár na cathrach"). Ach taispeánfaidh mé níos déanaí go n-oibríonn siad go breá le haghaidh colúin ard cardinality freisin.
Breathnaímid ar an sampla is simplí de innéacs bitmap.
Samhlaigh go bhfuil liosta de na bialanna Moscó againn a bhfuil airíonna dénártha mar seo:
- in aice le meitreo;
- tá páirceáil phríobháideach ann;
- tá veranda ann (has terrace);
- is féidir leat tábla a chur in áirithe (glacann áirithintí);
- oiriúnach do vegetarians (cairdiúil vegan);
- daor (daor).
Tabhair seicheamh uimhir do gach bialann ag tosú ó 0 agus leithroinnimid cuimhne ar 6 ghiotán (ceann do gach saintréith). Déanfaimid na bitmaps seo a líonadh ansin ag brath ar cibé an bhfuil an mhaoin seo ag an mbialann nó nach bhfuil. Má tá veranda ag bialann 4, socrófar giotán Uimh. 4 sa léarscáil ghiotán “tá veranda” ag 1 (mura bhfuil veranda ann, ansin go dtí 0).
Anois tá an t-innéacs bitmap is simplí againn, agus is féidir linn é a úsáid chun ceisteanna ar nós:
- “Taispeáin dom bialanna atá neamhdhíobhálach don vegetarian”;
- “Taispeáin dom bialanna neamhchostasach le veranda inar féidir leat bord a chur in áirithe.”
Conas? A ligean ar a fháil breathnú. Tá an chéad iarratas an-simplí. Níl le déanamh againn ach an léarscáil ghiotán atá “cairdiúil le glasraí” a ghlacadh agus é a dhéanamh ina liosta de na bialanna a bhfuil a gcuid píosaí nochta.
Tá an dara iarratas beagán níos casta. Ní mór dúinn an Giotán NOT a úsáid ar an léarscáil ghiotán “daor” chun liosta de na bialanna neamhchostasach a fháil, ansin AGUS é leis an léarscáil ghiotán “an féidir liom tábla a chur in áirithe” agus AGUS an toradh leis an léarscáil ghiotán “tá veranda”. Beidh liosta de bhunaíochtaí a chomhlíonann ár gcritéir go léir sa ghiotán a bheidh mar thoradh air. Sa sampla seo, níl anseo ach bialann Yunost.
Tá go leor teoiric i gceist, ach ná bíodh imní ort, feicfimid an cód go han-luath.
Cá n-úsáidtear innéacsanna giotáin?
Má innéacsaíonn tú léarscáil ghiotán Google, bainfidh 90% de na freagraí le Oracle DB ar bhealach amháin nó ar bhealach eile. Ach is dócha go dtacaíonn DBMSanna eile lena leithéid de rud fionnuar, ceart? Níl i ndáiríre.
A ligean ar dul tríd an liosta de na príomh-amhrastach.
Ní thacaíonn MySQL le hinnéacsanna léarscáileanna giotán fós, ach tá Togra ann a mholann an rogha seo a chur leis ().
Ní thacaíonn PostgreSQL le hinnéacsanna giotáin, ach úsáideann sé léarscáileanna giotán simplí agus oibríochtaí giotán chun torthaí cuardaigh a chomhcheangal thar innéacsanna iolracha eile.
Tá innéacsanna bitset ag Tarantool agus tacaíonn sé le cuardaigh shimplí orthu.
Tá bitfields simplí ag Redis) gan an cumas chun iad a chuardach.
Ní thacaíonn MongoDB le hinnéacsanna bitmap fós, ach tá Togra ann freisin a thugann le tuiscint go gcuirfí leis an rogha seo
Úsáideann Elasticsearch léarscáileanna giotán go hinmheánach).
- Ach tá comharsa nua le feiceáil inár dteach: Pilosa. Is bunachar sonraí nua neamhghaolmhar é seo atá scríofa in Go. Níl ann ach innéacsanna giotánmap agus bunaítear gach rud orthu. Déanfaimid labhairt faoi beagán níos déanaí.
Cur i bhfeidhm in Go
Ach cén fáth a mbaintear úsáid chomh hannamh as innéacsanna giotáin? Sula bhfreagróidh mé an cheist seo, ba mhaith liom a thaispeáint duit conas innéacs bitmap an-simplí a chur i bhfeidhm in Go.
Go bunúsach, níl sna bitmaps ach píosaí sonraí. In Go, bainimis úsáid as slisní beart chuige seo.
Tá léarscáil ghiotán amháin againn le haghaidh tréith bialainne amháin, agus léiríonn gach giotán sa léarscáil ghiotán an bhfuil an mhaoin seo ag bialann ar leith nó nach bhfuil.
Beidh dhá fheidhm chúntóra de dhíth orainn. Bainfear úsáid as ceann amháin chun ár gcuid giotánmaps a líonadh le sonraí randamacha. Randamach, ach le dóchúlacht áirithe go bhfuil gach maoin ag an mbialann. Mar shampla, creidim gur fíorbheagán bialann i Moscó nach féidir leat bord a chur in áirithe, agus feictear dom go bhfuil thart ar 20% de na bunaíochtaí oiriúnach do veigeatóirí.
Déanfaidh an dara feidhm an léarscáil ghiotán a thiontú ina liosta de bhialanna.
Chun an cheist a fhreagairt “Taispeáin dom bialanna neamhchostasach a bhfuil patio acu agus ar féidir leo áirithintí a dhéanamh,” teastaíonn oibríocht dhá ghiotán uainn: NOT agus AND.
Is féidir linn ár gcód a shimpliú beagán trí úsáid a bhaint as an oibreoir níos casta AND NOT.
Tá feidhmeanna againn do gach ceann de na hoibríochtaí sin. Téann an bheirt acu trí na slices, tóg na heilimintí comhfhreagracha ó gach ceann acu, iad a chomhcheangal le beagán oibríochta agus cuir an toradh isteach sa slice mar thoradh air.
Agus anois is féidir linn ár gcuid léarscáileanna agus feidhmeanna a úsáid chun an cheist chuardaigh a fhreagairt.
Níl an fheidhmíocht chomh hard sin, cé go bhfuil na feidhmeanna an-simplí agus sábháladh muid go leor airgid trí gan slice iarmhartach nua a thabhairt ar ais gach uair a glaodh an fheidhm.
Tar éis beagán próifílithe a dhéanamh le pprof, thug mé faoi deara go raibh leas iomlán a bhaint as ceann amháin an-simplí ach an-tábhachtach in easnamh ar an tiomsaitheoir Go: inlining feidhm.
Is é an fírinne go bhfuil eagla uafásach ar an tiomsaitheoir Go roimh lúba a théann trí slisní, agus go ndiúltaíonn sé go catagóiriúil feidhmeanna inlíne a bhfuil lúba den sórt sin iontu.
Ach níl aon eagla orm agus is féidir liom amadán a dhéanamh ar an tiomsaitheoir trí goto a úsáid seachas lúb, mar a bhí sna seanlaethanta maithe.
Agus, mar a fheiceann tú, anois beidh an tiomsaitheoir sásta ár bhfeidhm a inlíneáil! Mar thoradh air sin, bainistímid thart ar 2 mhicreathonnta a shábháil. Ní dona!
Is furasta an dara tranglam a fheiceáil má fhéachann tú go géar ar aschur an tionóil. Chuir an tiomsaitheoir seiceáil teorann slice díreach taobh istigh den lúb is teo againn. Is é fírinne an scéil gur teanga shábháilte í Go, tá eagla ar an tiomsaitheoir go bhfuil mo thrí argóint (trí shlisne) de mhéideanna éagsúla. Tar éis an tsaoil, ansin beidh an fhéidearthacht teoiriciúil ann go dtarlódh ró-sreabhadh maolánach mar a thugtar air.
Cuirimis an tiomsaitheoir ar a shuaimhneas trína thaispeáint dó go bhfuil na slisní uile ar an méid céanna. Is féidir linn é seo a dhéanamh trí sheic shimplí a chur leis ag tús ár bhfeidhme.
Agus é seo á fheiceáil, scipeann an tiomsaitheoir an tseic go sona sásta, agus sa deireadh táimid ag sábháil 500 nana-seicind eile.
Búistéirí móra
Ceart go leor, d’éirigh linn roinnt feidhmíochta a bhaint amach as ár gcur i bhfeidhm simplí, ach tá an toradh seo i ndáiríre i bhfad níos measa ná mar is féidir le crua-earraí reatha.
Níl le déanamh againn ach oibríochtaí giotán bunúsacha, agus déanann ár bpróiseálaithe iad go han-éifeachtach. Ach, ar an drochuair, déanaimid “beatha” dár bpróiseálaí le píosaí an-bheag oibre. Comhlíonann ár bhfeidhmeanna oibríochtaí ar bhonn beart-ar-beart. Is féidir linn ár gcód a athrú go héasca chun oibriú le smután 8 beart ag baint úsáide as slisní UInt64.
Mar a fheiceann tú, chuir an t-athrú beag seo dlús lenár gclár ocht n-uaire trí mhéid an bhaisc a mhéadú faoi XNUMX n-uaire. Is féidir a rá go bhfuil an gnóthachan líneach.
Cur i bhfeidhm i gcóimeálaí
Ach ní hé seo an deireadh. Is féidir lenár bpróiseálaithe oibriú le smután de 16, 32 agus fiú 64 beart. Tugtar sonraí iolracha teagaisc aonair ar oibríochtaí “leathana” den sórt sin (SIMD; treoir amháin, go leor sonraí), agus tugtar veicteoiriú ar an bpróiseas chun cód a athrú ionas go n-úsáideann sé oibríochtaí den sórt sin.
Ar an drochuair, tá an tiomsaitheoir Go i bhfad ó bheith den scoth ag veicteoiriú. Faoi láthair, is é an t-aon bhealach chun cód Go a veicteoiriú ná na hoibríochtaí seo a thógáil agus a chur de láimh ag baint úsáide as Go assembler.
Is Beast aisteach é Go assembler. Is dócha go bhfuil a fhios agat go bhfuil baint mhór ag teanga tionóil le hailtireacht an ríomhaire a bhfuil tú ag scríobh dó, ach ní hé sin an cás in Go. Tá cóimeálaí Go níos cosúla le IRL (teanga ionadaíochta idirmheánach) nó teanga idirmheánach: tá sé neamhspleách ar an ardán go praiticiúil. Thug Rob Pike feidhmíocht den scoth ar an ábhar seo roinnt blianta ó shin ag GopherCon i Denver.
Ina theannta sin, úsáideann Go formáid neamhghnách Plan 9, atá difriúil ó na formáidí AT&T agus Intel a nglactar leo go ginearálta.
Tá sé sábháilte a rá nach é scríobh Go assembler de láimh an spraoi is mó.
Ach, go fortunately, tá dhá uirlis ardleibhéil ann cheana féin a chuidíonn linn assembler Go a scríobh: PeachPy agus avo. Gineann an dá fhóntas cóimeálaí Go ó chód ardleibhéil scríofa i Python agus Go, faoi seach.
Simplíonn na fóntais seo rudaí cosúil le leithdháileadh clár, lúba scríbhneoireachta, agus go ginearálta simplíonn siad an próiseas chun dul isteach i saol an chláir tionóil in Go.
Bainfidh muid úsáid as avo, mar sin beidh ár gcláir a bheith beagnach rialta cláir Go.
Seo an chuma atá ar an sampla is simplí de chlár avo. Tá príomh()fheidhm againn, a shainmhíníonn ann féin an fheidhm Add(), arb é an bhrí atá leis ná dhá uimhir a shuimiú. Tá feidhmeanna cúntóra anseo chun paraiméadair a fháil de réir ainm agus ceann de na cláir phróiseálaithe saor in aisce agus oiriúnach a fháil. Tá feidhm chomhfhreagrach ag gach oibríocht próiseálaí ar avo, mar atá le feiceáil in ADDQ. Ar deireadh, feicimid feidhm chúntóra chun an luach mar thoradh air a stóráil.
Trí ghlaoch a chur ar go Gene, déanfaimid an clár a fhorghníomhú ar avo agus mar thoradh air sin, ginfear dhá chomhad:
- add.s leis an gcód mar thoradh air in Go assembler;
- stub.go le ceanntásca feidhmeanna chun an dá shaol a nascadh: Téigh agus cóimeálaí.
Anois go bhfuil feicthe againn cad a dhéanann avo agus conas, a ligean ar breathnú ar ár bhfeidhmeanna. Chuir mé an dá leagan scálach agus veicteoireach (SIMD) de na feidhmeanna i bhfeidhm.
Breathnaímid ar na leaganacha scálacha ar dtús.
Mar a tharla sa sampla roimhe seo, táimid ag iarraidh clár cuspóir ginearálta saor in aisce agus bailí, ní gá dúinn fritháirimh agus méideanna na n-argóintí a ríomh. Déanann avo seo go léir dúinn.
Bhaineamar úsáid as lipéid agus goto (nó jumps) chun feidhmíocht a fheabhsú agus cleas a chur ar an tiomsaitheoir Go, ach anois táimid á dhéanamh ón tús. Is é an pointe ná gur coincheap ardleibhéil iad timthriallta. I gcóimeálaí, níl againn ach lipéid agus geansaithe.
Ba cheart go mbeadh an cód atá fágtha eolach agus intuigthe cheana féin. Déanaimid aithris ar lúb le lipéid agus geansaí, tógfaimid píosa beag sonraí ónár dhá shlisne, cuir le chéile iad le beagán oibríochta (AGUS NACH sa chás seo) agus ansin cuir an toradh isteach sa slice mar thoradh air. Gach.
Is é seo an chuma atá ar an gcód cóimeálaí deiridh. Ní raibh orainn fritháirimh agus méideanna a ríomh (aibhsithe i glas) nó súil a choinneáil ar na cláir a úsáideadh (aibhsithe i dearg).
Má dhéanaimid comparáid idir feidhmíocht chur i bhfeidhm na teanga tionóil le feidhmíocht an fhorfheidhmithe is fearr in Go, feicfimid go bhfuil sé mar an gcéanna. Agus táthar ag súil leis seo. Tar éis an tsaoil, ní dhearnamar aon rud speisialta - rinneamar a atáirgeadh cad a dhéanfadh tiomsaitheoir Go.
Ar an drochuair, ní féidir linn iallach a chur ar an tiomsaitheoir ár bhfeidhmeanna scríofa i dteanga tionóil a inlíneáil. Níl a leithéid de ghné ag an tiomsaitheoir Go faoi láthair, cé go bhfuil iarratas déanta é a chur leis le tamall maith.
Sin é an fáth go bhfuil sé dodhéanta aon leas a bhaint as feidhmeanna beaga sa teanga tionóil. Ní mór dúinn feidhmeanna móra a scríobh, nó an pacáiste nua matamaitice/giotáin a úsáid, nó an teanga cóimeálaí a sheachbhóthar.
Breathnaímid anois ar na leaganacha veicteora dár bhfeidhmeanna.
Mar shampla seo, chinn mé AVX2 a úsáid, agus mar sin úsáidfimid oibríochtaí a oibríonn ar smután 32-byte. Tá struchtúr an chóid an-chosúil leis an leagan scálach: paraiméadair luchtaithe, ag iarraidh clár comhroinnte saor in aisce, etc.
Nuáil amháin is ea go n-úsáideann oibríochtaí veicteora níos leithne cláir leathana speisialta. I gcás smután 32 beart, is cláir iad seo a bhfuil réamhshocrú déanta orthu le Y. Sin an fáth a bhfeiceann tú an fheidhm YMM() sa chód. Dá mba rud é go raibh mé ag baint úsáide as AVX-512 le smután 64-giotán, is é Z an réimír.
Is é an dara nuálaíocht gur chinn mé leas iomlán a bhaint as ar a dtugtar lúb unrolling, rud a chiallaíonn ocht n-oibríochtaí lúb a dhéanamh de láimh roimh léim go dtí tús an lúb. Laghdaíonn an leas iomlán a bhaint seo líon na mbrainsí sa chód, agus tá sé teoranta ag líon na gclár saor in aisce atá ar fáil.
Bhuel, cad mar gheall ar fheidhmíocht? Tá sí go hálainn! Bhaineamar luasghéarú seacht n-uaire amach i gcomparáid leis an réiteach Go is fearr. Go hiontach, ceart?
Ach d’fhéadfaí fiú an cur chun feidhme seo a luathú trí úsáid a bhaint as AVX-512, prefetching nó JIT (tiomsaitheoir díreach in am) don sceidealóir fiosrúchán. Ach is cinnte gur ábhar é seo do thuarascáil ar leith.
Fadhbanna le hinnéacsanna bitmap
Anois agus muid cheana féin tar éis féachaint ar innéacs giotánmap a chur i bhfeidhm go simplí in Go agus innéacs i bhfad níos táirgiúla i dteanga tionóil, déanaimis labhairt ar deireadh cén fáth a n-úsáidtear innéacsanna giotánmap chomh hannamh sin.
Luann páipéir níos sine trí fhadhb le hinnéacsanna bitmap, ach tá páipéir níos nuaí agus maíonn mé nach bhfuil siad ábhartha a thuilleadh. Ní bheidh muid ag tumadh go domhain isteach i ngach ceann de na fadhbanna seo, ach féachfaimid orthu go dromchlach.
Fadhb na cardinality ard
Mar sin, cuirtear in iúl dúinn nach bhfuil innéacsanna bitmap oiriúnach ach do réimsí le cardinality íseal, is é sin, iad siúd nach bhfuil mórán luachanna acu (mar shampla, inscne nó dath súl), agus is é an chúis atá leis ná go bhfuil gnáth-léiriú réimsí den sórt sin (ceann amháin). giotán in aghaidh an luacha) i gcás cardinality ard, tógfaidh sé an iomarca spáis agus, ina theannta sin, is annamh a líonfar na hinnéacsanna giotánmap seo.
Uaireanta b'fhéidir go n-úsáidfimid léiriú difriúil, mar an ceann caighdeánach a úsáidimid chun uimhreacha a léiriú. Ach ba é teacht na halgartaim comhbhrú a d'athraigh gach rud. Le fiche nó tríocha bliain anuas, tá eolaithe agus taighdeoirí tar éis teacht suas le líon mór halgartaim comhbhrú le haghaidh bitmaps. Is é an buntáiste is mó a bhaineann leo ná nach gá léarscáileanna giotán a dhí-chomhbhrú chun oibríochtaí giotán a dhéanamh - is féidir linn oibríochtaí giotán a dhéanamh go díreach ar léarscáileanna giotán comhbhrúite.
Le déanaí, tá cineálacha cur chuige hibrideacha tar éis tosú ag teacht chun cinn, cosúil le bitmaps roaring. Úsáideann siad ag an am céanna trí uiríll dhifriúla le haghaidh bitmaps - bitmaps iad féin, eagair agus ritheann giotán mar a thugtar orthu - agus cothromaíocht eatarthu chun feidhmíocht a uasmhéadú agus tomhaltas cuimhne a íoslaghdú.
Is féidir leat giotánmaps roaring a fháil sna feidhmchláir is coitianta. Tá líon mór feidhmiúcháin ann cheana féin do raon leathan teangacha ríomhchlárúcháin, lena n-áirítear níos mó ná trí fheidhmiúchán le haghaidh Go.
Cur chuige eile a chuideoidh linn déileáil leis an ard-cairdiúlacht ná binning. Samhlaigh go bhfuil páirc agat a léiríonn airde duine. Uimhir snámhphointe is ea airde, ach ní smaoiníonn daoine air mar sin. Maidir linn níl aon difríocht idir airde 185,2 cm agus 185,3 cm.
Tarlaíonn sé gur féidir linn luachanna comhchosúla a ghrúpáil i ngrúpaí laistigh de 1 cm.
Agus má tá a fhios againn freisin gur fíorbheagán daoine atá níos giorra ná 50 cm agus níos airde ná 250 cm, ansin is féidir linn go bunúsach réimse le cardinality gan teorainn a iompú isteach i réimse le cardinality de thart ar 200 luach.
Ar ndóigh, más gá, is féidir linn scagadh breise a dhéanamh ina dhiaidh sin.
Fadhb Ard Bandaleithid
Is í an chéad fhadhb eile le hinnéacsanna bitmap ná go mbíonn sé an-chostasach iad a nuashonrú.
Caithfidh bunachair shonraí a bheith in ann sonraí a nuashonrú agus d’fhéadfadh go mbeadh na céadta fiosrúchán eile ag cuardach na sonraí. Teastaíonn glais uainn chun fadhbanna a bhaineann le rochtain chomhthráthach ar shonraí nó fadhbanna comhroinnte eile a sheachaint. Agus sa chás go bhfuil glas mór amháin ann, tá fadhb ann - cion an ghlais, nuair a bhíonn an glas seo ina bhac.
Is féidir an fhadhb seo a réiteach nó dul timpeall air trí úsáid a bhaint as bearrtha nó trí innéacsanna leagan a úsáid.
Is rud simplí agus dea-aitheanta é Sharding. Is féidir leat innéacs léarscáil ghiotán a shard mar a dhéanfá ar aon sonraí eile. In ionad glas mór amháin, gheobhaidh tú a bunch de glais bheaga agus mar sin fáil réidh le cion glas.
Is é an dara bealach chun an fhadhb a réiteach ná innéacsanna leagan a úsáid. Is féidir leat cóip amháin den innéacs a úsáideann tú chun cuardach nó léamh a bheith agat, agus cóip a úsáideann tú chun scríobh nó nuashonrú. Agus uair amháin i dtréimhse áirithe ama (mar shampla, uair amháin gach 100 ms nó 500 ms) déanann tú iad a dhúbailt agus a mhalartú. Ar ndóigh, níl an cur chuige seo infheidhme ach amháin i gcásanna inar féidir le d’iarratas innéacs cuardaigh beagán chun deiridh a láimhseáil.
Is féidir an dá chur chuige seo a úsáid go comhuaineach: is féidir leat innéacs leagan mionghearrtha a bheith agat.
Ceisteanna níos casta
Is í an fhadhb dheireanach le hinnéacsanna giotáin ná go gcuirtear in iúl dúinn nach bhfuil siad oiriúnach go maith do chineálacha ceisteanna níos casta, mar cheisteanna réise.
Go deimhin, má cheapann tú faoi, níl oibríochtaí giotán cosúil le AND, OR, etc. an-oiriúnach le haghaidh ceisteanna a la “Taispeáin dom óstáin le rátaí seomra idir 200 agus 300 dollar in aghaidh na hoíche.”
Réiteach naive agus an-mhí-chiallmhar a bheadh ann na torthaí a ghlacadh le haghaidh gach luach dollar agus iad a chomhcheangal le oibríocht NÓ beagán ciallmhar.
Réiteach beagán níos fearr a bheadh ann ná grúpáil a úsáid. Mar shampla, i ngrúpaí de 50 dollar. Chuirfeadh sé seo dlús lenár bpróiseas faoi 50 uair.
Ach is furasta an fhadhb a réiteach freisin trí úsáid a bhaint as radharc a cruthaíodh go sonrach don chineál seo iarratais. I bpáipéir eolaíocha a thugtar air bitmaps raon-ionchódaithe.
Sa léiriú seo, ní hamháin go socróimid beagán amháin le haghaidh luach éigin (mar shampla, 200), ach socróimid an luach seo agus gach rud níos airde. 200 agus os a chionn. Mar an gcéanna le haghaidh 300: 300 agus os a chionn. Agus mar sin de.
Ag baint úsáide as an léiriú seo, is féidir linn an cineál seo d'fhiosrúchán cuardaigh a fhreagairt ach an t-innéacs a thrasnú faoi dhó díreach. Gcéad dul síos, gheobhaidh muid liosta de na hóstáin a bhfuil costas an seomra níos lú nó $300, agus ansin beidh muid a bhaint as é siúd a bhfuil an costas seomra níos lú nó $199. Réidh.
Beidh ionadh ort, ach is féidir fiú geoqueries ag baint úsáide as innéacsanna bitmap. Is é an cleas ná léiriú geoiméadrach a úsáid a thimpeallaíonn do chomhordanáid le figiúr geoiméadrach. Mar shampla, S2 ó Google. Ba cheart go bhféadfaí an figiúr a léiriú i bhfoirm trí líne trasnacha nó níos mó is féidir a uimhriú. Ar an mbealach seo is féidir linn ár ngeoquery a iompú isteach i roinnt fiosruithe “ar feadh na bearna” (mar aon leis na línte uimhrithe seo).
Réitigh Réite
Tá súil agam go bhfuil suim agam duit agus go bhfuil uirlis úsáideach eile agat anois i do Arsenal. Más gá duit rud éigin mar seo a dhéanamh riamh, beidh a fhios agat cén bealach le breathnú.
Mar sin féin, níl an t-am, an fhoighne ná na hacmhainní ag gach duine chun innéacsanna giotánmap a chruthú ón tús. Go háirithe cinn níos forbartha, ag baint úsáide as SIMD, mar shampla.
Ar ámharaí an tsaoil, tá roinnt réitigh réamhdhéanta ann chun cabhrú leat.
Giotán roaring
Ar an gcéad dul síos, tá an leabharlann bitmaps roaring chéanna ar labhair mé faoi cheana. Tá na coimeádáin agus na hoibríochtaí giotán riachtanacha go léir ann a bheidh ag teastáil uait chun innéacs léarscáil ghiotán iomlán a dhéanamh.
Ar an drochuair, i láthair na huaire, níl aon cheann de na feidhmiúcháin Go ag baint úsáide as SIMD, rud a chiallaíonn go bhfuil feidhmiúcháin Go níos lú feidhmíochta ná feidhmiúcháin C, mar shampla.
gruagach
Táirge eile a chabhróidh leat is ea an Pilosa DBMS, nach bhfuil ann ach innéacsanna giotáin. Is réiteach réasúnta nua é seo, ach tá sé ag buachan hearts ag luas mór.
Úsáideann Pilosa bitmaps roaring go hinmheánach agus tugann sé an cumas duit iad a úsáid, a shimpliú agus a mhíníonn na rudaí go léir ar labhair mé fúthu thuas: grúpáil, giotáin raon-ionchódaithe, coincheap an réimse, etc.
Breathnaímis go gasta ar shampla de Pilosa a úsáid chun ceist a bhfuil cur amach agat uirthi cheana féin a fhreagairt.
Tá an sampla an-chosúil leis an méid a chonaic tú roimhe seo. Cruthaímid cliant chuig an bhfreastalaí Pilosa, cruthaímid innéacs agus na réimsí riachtanacha, ansin líonaimid ár réimsí le sonraí randamacha le dóchúlachtaí agus, ar deireadh, déanaimid an fiosrúchán coitianta.
Tar éis sin, úsáidimid NACH ar an réimse "daor", ansin trasnaigh an toradh (nó AGUS é) leis an réimse "ardán" agus leis an réimse "áirithintí". Agus ar deireadh, faigheann muid an toradh deiridh.
Tá súil agam go mbeidh an cineál innéacs nua seo le feiceáil go luath amach anseo freisin i DBMSanna mar MySQL agus PostgreSQL - innéacsanna bitmap.
Conclúid
Mura bhfuil tú tar éis titim i do chodladh go fóill, go raibh maith agat. Bhí orm teagmháil a dhéanamh go hachomair ar go leor ábhar mar gheall ar an am teoranta, ach tá súil agam go raibh an chaint úsáideach agus b'fhéidir fiú spreagúil.
Is maith eolas a bheith agat ar innéacsanna bitmap, fiú mura bhfuil siad de dhíth ort faoi láthair. Lig dóibh a bheith ina uirlis eile i do bhosca uirlisí.
D'fhéachamar ar chleasanna feidhmíochta éagsúla le haghaidh Go agus rudaí nach láimhseálann tiomsaitheoir Go go han-mhaith fós. Ach tá sé seo fíor-úsáideach go mbeadh a fhios ag gach ríomhchláraitheoir Go.
Sin go léir a theastaigh uaim a insint duit. Go raibh maith agat!
Foinse: will.com