Intreoir idirghníomhach ar cheathairchrainn

Cén Fáth a Bhfuil Tábhacht ag Quadtrees Níos Mó ná a Shílfeá

Gach uair a bhrúnn tú chun súmáil ar léarscáil dhigiteach, má chuireann tú ceist ar bhialanna in aice láimhe, nó má fhéachann tú ar rianaitheoir cabhlaigh fíor-ama a nuashonraíonn mórán deilbhíní feithicle gan do bhrabhsálaí a mheilt ar deireadh, tá seans maith ann go bhfuil quadtree ag déanamh an ardú mór ar an gcúlra. Tá Quadtrees ar cheann de na struchtúir sonraí galánta sin nach gcloisfidh an chuid is mó daoine faoi, ach tá siad i gcumhacht go ciúin ar chuid de na córais is tábhachtaí maidir le feidhmíocht i mbogearraí nua-aimseartha - ó bhrath imbhuailtí físchluiche go córais faisnéise geografacha a phróiseálann na milliúin fiosrúchán spásúlachta in aghaidh an tsoicind. Ní hamháin gur forbróir níos fearr tú a thuiscint conas a oibríonn siad; athraíonn sé go bunúsach an dóigh a smaoiníonn tú ar eagrú agus cuardach trí shonraí spásúla. Cibé an bhfuil tú ag tógáil ardán loighistic seachadta, painéal anailíse bunaithe ar shuíomh, nó go simplí ag iarraidh 50,000 pointe sonraí a sholáthar ar chanbhás gan an brabhsálaí a bhualadh, tairgeann quadtrees réiteach atá iomasach agus thar a bheith éifeachtach.

Cad go díreach atá i gCeathrú Crann?

Is struchtúr sonraí crann é cuadrann ina bhfuil ceathrar páistí go díreach i ngach nód inmheánach, gach ceann acu a léiríonn ceathrú amháin de spás déthoiseach. Samhlaigh go dtógfaidh tú réigiún cearnach agus roinn i gceithre chearnóg chothroma é - iarthuaisceart, oirthuaisceart, iardheisceart agus oirdheisceart. Is féidir gach ceann de na cearnóga sin a roinnt níos mó i gceithre chearnóg eile, agus mar sin de, go hathchúrsach, go dtí go sroicheann tú riocht stad éigin. Is gnách go mbíonn an riocht stad sin ina uasdoimhneacht nó ina thairseach don líon pointí sonraí is féidir le nód amháin a choinneáil sula gcaithfeadh sé scoilt.

Tá áilleacht an chur chuige seo ina nádúr oiriúnaitheach. Déantar limistéir atá dlúth le pointí sonraí a fhoroinnt i gcealla míne agus níos míne, agus fanann limistéir tearca mar réigiúin mhóra neamhroinnte. Chruthódh quadtree ina stórálfaí láithreacha 10,000 siopa caife ar fud na tíre foranna domhain, mionsonraithe thar Manhattan - áit a bhféadfadh 300 siopa a bheith laistigh de chúpla ciliméadar cearnach - agus ag coinneáil stráicí móra de Wyoming tuaithe mar nód aonair gan scoilt ina bhfuil nialas nó pointe amháin. Is é an taifeach oiriúnaitheach seo a fhágann go bhfuil cuadchrainn chomh cumhachtach i gcomparáid le heangach réidh, a chuirfeadh amú mór cuimhne ar chealla folmha.

Rinne Raphael Finkel agus J.L. Bentley cur síos ar an gcoincheap ar dtús i 1974, agus ó shin i leith tá sé scaipthe i leaganacha éagsúla: stórálann cuadchrainn phointe péirí comhordanáidí aonair, seasann cuad-chrainn réigiúin achair spásúla (úsáideach le haghaidh comhbhrú íomhánna), agus láimhseálann cuadchrainn imeall línte agus cuair. Déanann gach leagan optamaithe le haghaidh cásanna úsáide difriúla, ach fanann an bunphrionsabal um fhoroinnt athfhillteach mar a chéile trasna gach ceann díobh.

Conas a oibríonn ionsá agus ceisteanna

Chun pointe a chur isteach i gceathrú crann, tosaíonn tú ag an bhfréamh nód agus cinneann tú cé acu de na ceithre cheathrú ina bhfuil an pointe. Filleann tú isteach i nód linbh an cheathrú sin ansin agus déanann tú an próiseas arís. Má shroicheann tú nód duille nár sháraigh a thoilleadh (go hiondúil a shocraítear go 1 nó 4 phointe), ní gá duit ach an pointe a stóráil ansin. Má tá an duilleog ag cumas cheana féin, scoilteann sé i gceithre leanbh, athdháileann sé na pointí atá ann cheana féin ina measc, agus ansin cuireann sé an pointe nua isteach sa leanbh cuí. Críochnaíonn an próiseas seo go hiondúil in am O(log n) le haghaidh dáileadh cothrom, cé gur féidir leis na cásanna is measa ina bhfuil sonraí an-chnuasach feidhmíocht a dhíghrádú.

Fiosrúchán raoin — gach pointe a aimsiú laistigh d'achar dronuilleogach ar leith — is ea an áit a lonraíonn cuadchrainn go fírinneach. In ionad gach pointe i do thacar sonraí a sheiceáil (oibríocht O(n)), tosaíonn tú ag an bhfréamh agus cuireann tú ceist shimplí ar gach nód: an dtrasnaíonn teorainn an nód seo le mo dhronuilleog chuardaigh? Mura bhfuil, gearrann tú an fochrainn iomlán - d'fhéadfadh go gcuirfí deireadh leis na mílte pointí ó bhreithniú i gcomparáid amháin. Má bhíonn crosbhealach ann, filleann tú arís ar na leanaí cuí. Cuirtear pointí a aimsítear i nóid dhuilleog laistigh den dronuilleog cuardaigh leis an tacar torthaí.

Déan machnamh ar shampla praiticiúil: tá tacar sonraí de 100,000 suíomh custaiméara agat agus caithfidh tú gach duine a aimsiú laistigh de gha 5 chiliméadar ó oscailt siopa nua. Éilíonn cur chuige brúidiúil 100,000 ríomh achair. D'fhéadfadh go laghdódh ceathrú crann dea-thógtha é sin go díreach 200-500 seiceáil trí dheireadh a chur go tapa ar réigiúin gheografacha ar fad nach bhfuil forluí acu le do limistéar cuardaigh. Sin feabhas feidhmíochta de 200x nó níos mó — an difríocht idir ceist a thógann 800 milleasoicind agus 4 milleasoicind a thógáil.

Feidhmchláir Fhíordhomhanda a Ritheann ar Quadtrees

Síneann feidhmeanna quadtrees i bhfad níos faide ná ríomheolaíocht acadúil. Tá siad mar bhunús le córais a úsáideann na billiúin daoine go laethúil, go minic gan iad a thuiscint.

• Mapáil agus loingseoireacht: Úsáideann seirbhísí ar nós Google Maps agus Mapbox córais tíleanna ar nós cuadrann chun íomhánna léarscáile a sheirbheáil. Foroinneann gach leibhéal súmáil tíleanna i gceathrar leanaí, agus is é sin an fáth go leanann comhordanáidí tíleanna léarscáile patrún z/x/y a léiríonn seoladh ceathrúchrainn. Nuair a dhéanann tú zúmáil isteach i mbloc cathrach, ní gá ach an t-ualach tíleanna ardtaifigh ábhartha - fanann an chuid eile den domhan ar réiteach garbh.
• Brath imbhuailte i gcluichí: Úsáideann innill chluiche cuadraoin (agus a gcomhghleacaí 3D, octrens) chun a bhrath go héifeachtach nuair a imbhuaileann rudaí. In ionad gach péire réad a thástáil – tromluí O(n²) le 1,000 eintiteas ar an scáileán – ní seiceálann an t-inneall ach réada a bhfuil an chill chuadrann chéanna acu, agus laghdaítear seiceálacha go dtí uimhir inláimhsithe.
• Comhbhrú íomhánna: Is féidir le ceathrúchrainn réigiúin íomhánna a chomhbhrú trí phicteilíní cóngaracha a roinneann dathanna comhchosúla i mbloic níos mó a chumasc. Tá sé seo mar bhunús le halgartaim chomhbhrú ar leith a ghnóthaíonn cóimheasa comhbhrú 10:1 agus a chothaíonn dílseacht amhairc i réimsí nach bhfuil mórán sonraí iontu.
• Bainistíocht cabhlaigh agus lóistíocht: Úsáideann cuideachtaí seachadta innéacsú spáis chun tiománaithe a mheaitseáil le horduithe in aice láimhe i bhfíor-am. Ligeann quadtree do chóras seolta an cheist a fhreagairt láithreach "cad iad na 5 thiománaí is gaire don láthair bailithe seo?" thar flít de na mílte feithiclí ag nuashonrú a suíomhanna GPS gach cúpla soicind.
• Anailís Geospásúil: Braitheann ardáin a chomhiomlánaíonn sonraí gnó bunaithe ar shuíomh — léarscáileanna dlúis custaiméara, barrfheabhsú na gcríoch díolacháin, anailís socrúcháin stórais — ar struchtúir sonraí spáis chun na fiosrúcháin seo a dhéanamh idirghníomhach seachas baiscphróiseáilte.

Is é an príomh-léargas atá taobh thiar de quadtrees ná nach gá don chuid is mó de na fiosrúcháin spáis an chuid is mó de na sonraí a scrúdú. Trí spás a eagrú go ordlathach, déanann tú cuardaigh brúidiúla a chlaochlú go trasnuithe spriocdhírithe - ag iompú soicind ina milleasoicindí agus ag déanamh idirghníomhú fíor-ama fiú le tacair shonraí ollmhóra.

Crainn Cheathair a Thógáil Ó Scratch

Is ionadh é cur i bhfeidhm cuadrann bunúsach, fiú d'fhorbróirí idirmheánacha. Níl ach cúpla comhpháirt ag teastáil ón gcroístruchtúr: teorainn (an t-achar dronuilleogach a chlúdaíonn an nód), acmhainn (na huasphointí roimh scoilteadh), eagar pointí, agus tagairtí do cheithre nóid linbh (níl ar dtús). Is féidir an fheidhm ionsáite iomlán a scríobh faoi 30 líne de chód i bhformhór na dteangacha.

Cruthaíonn an oibríocht scoilte ceithre nód linbh nua, gach ceann acu ag clúdach ceathrú amháin de theorainn an tuismitheora. I gcás tuismitheoir le teorainn (x, y, leithead, airde), faigheann an leanbh oirthuaisceart (x + leithead / 2, y, leithead / 2, airde / 2), faigheann an iarthuaisceart (x, y, leithead / 2, airde / 2), agus mar sin de. Tar éis scoilteadh, déantar na pointí atá ann cheana féin a athdháileadh ar na páistí cuí. Botún coitianta is ea dearmad a dhéanamh ar raon pointí an tuismitheora a ghlanadh tar éis athdháilte, rud a fhágann go mbíonn dúbailt ar thorthaí le linn fiosruithe.

Maidir le húsáid táirgeachta, tá tábhacht le roinnt leas iomlán a bhaint as. Is gnách go n-éiríonn níos fearr le cumas an nód a shocrú go 4-8 pointe ná cumas 1, toisc go laghdaíonn sé doimhneacht crann agus forchostais rudaí nód. Má chuirtear uasteorainn doimhneachta (go hiondúil 8-12 leibhéal) cosc ​​ar chásanna paiteolaíocha ina mbíonn comhordanáidí comhionanna ag go leor pointí ó chrainn atá gan teorainn dhomhain a chruthú. Agus maidir le tacair shonraí dinimiciúla ina n-aistrítear pointí - cosúil le rianú feithiclí - beidh meicníocht bainte nó straitéis uait chun an crann a atógáil go tréimhsiúil, ós rud é nach ndéanann crainn chuaird féinchothromú mar a dhéanann crainn dhubh-dhearga.

Quadtrees in Ardáin Ghnó agus Anailísíocht

Déileálann ardáin ghnó nua-aimseartha níos mó agus níos mó le sonraí spásúla, cibé an suíomhanna custaiméirí, criosanna seachadta, críocha díolacháin nó rianú sócmhainní iad. Ní hé an dúshlán a bhaineann leis na sonraí seo a stóráil ach is féidir iad a fhiosrú i bhfíor-am ar scála. Nuair is gá do ghnó atá ag feidhmiú ar fud 50 cathair dlús custaiméara, tiománaithe seachadta bealaigh a shamhlú, nó anailís a dhéanamh ar fheidhmíocht díolacháin réigiúnach, cinneann an bhunstraitéis innéacsaithe spáis cé acu an lódálann an painéal i 200 milleasoicind nó 20 soicind.

Is cúis amháin é seo go mbaineann ardáin mar Mewayz — a chomhtháthaíonn 207 modúl a chuimsíonn CRM, sonrascadh, bainistíocht cabhlaigh, áirithint agus anailísíocht isteach in OS gnó amháin — tairbhe as láimhseáil éifeachtach sonraí spásúla faoin gcochall. Nuair is gá do mhodúl bainistíochta cabhlaigh 500 feithicil gníomhach a thaispeáint ar léarscáil, nó nuair a dhéanann modúl CRM amhairc ar 138,000+ suíomh úsáideora le haghaidh pleanáil críche, ní dhéanann cur chuige naive scála. Fágann struchtúir innéacsaithe spáis ar nós cuadchrainn (nó a gcoibhéisí bunachar sonraí, mar shampla crainn R-R PostGIS agus innéacsanna spáis MySQL) go bhfuil sé indéanta na gnéithe seo a thairiscint gan crua-earraí de ghrád fiontair a bheith ag teastáil uathu.

Do ghnóthais a dhéanann meastóireacht ar ardáin, tá an beir leat praiticiúil: ní hamháin go n-úsáideann uirlisí a láimhseálann sonraí suímh agus spásúlachta go maith algartaim bhréige ar mhaithe leis. Tá siad ag déanamh difríochta idir córas áirithinte ar féidir leis na soláthraithe seirbhíse atá ar fáil a thaispeáint laistigh de 10 gciliméadar agus ceann a thógann 8 soicind chun na torthaí céanna a lódáil. Is ionann feidhmíocht ag an leibhéal seo go díreach agus taithí úsáideora agus, sa deireadh, ioncam.

Quadtrees vs. Struchtúir Sonraí Spásúla Eile

Ní hé Quadtrees an t-aon rogha le haghaidh innéacsú spáis, agus cabhraíonn sé leat an uirlis cheart a roghnú má thuigeann tú na roghanna eile. R-crainn, a úsáidtear go forleathan i mbunachair sonraí mar PostGIS agus modúl R* Tree de chuid SQLite, eagraítear sonraí ina ndronuilleoga teorannacha íosta agus láimhseálann ceisteanna raoin agus cuardaigh na gcomharsan is gaire go héifeachtach. De ghnáth is fearr leo cuadchrainn le haghaidh stórála diosca-bhunaithe mar go n-íoslaghdaíonn siad oibríochtaí I/O, agus is é sin an fáth go n-úsáideann formhór na mbunachair shonraí spásúlachta leaganacha R-crann go hinmheánach seachas crainn chuadroma.

Crainn K-d spás deighilte ag baint úsáide as scoilteanna ailínithe ailínithe (ag x ar dtús, ansin ag y, ansin ag x arís) agus tá siad ar fheabhas le haghaidh cuardaigh na gcomharsan is gaire i toisí measartha. Is gnách go n-éiríonn leo níos fearr ná ceathairchrainn nuair a bhíonn an toiseachas íseal agus an tacar sonraí statach, ach bíonn sé níos deacra iad a nuashonrú go dinimiciúil. Glacann Geohashes cur chuige difriúil ar fad, ag ionchódú domhanleithead agus domhanfhad i teaghrán aonair ina léiríonn réimíreanna roinnte gaireacht spásúil - rud a fhágann go bhfuil siad oiriúnach le haghaidh innéacsú bunachar sonraí agus taisceadh ach nach bhfuil siad chomh solúbtha le haghaidh fiosrúcháin raon treallach.

Coinníonn Quadtrees a gcuid féin i gcásanna a bhaineann lena láidreachtaí: innéacsú spásúil cuimhneacháin, tacair sonraí dinimiciúla a gcuirtear isteach agus a scriostar go minic, feidhmchláir léirshamhlaithe ina mapálann an struchtúr greille ordlathach go nádúrtha chun leibhéil a zúmáil, agus cásanna ina bhfuil tábhacht le simplíocht an chur chun feidhme. Maidir le feidhmchlár tosaigh a fhágfaidh 10,000 pointe sonraí ar chanbhás le pan-agus-zoom, éireoidh le quadtree a chuirtear i bhfeidhm i 100 líne de JavaScript níos fearr ná aon réiteach a thacaíonn le bunachar sonraí trí dheireadh a chur le latency líonra.

Ag Tosú: Na Chéad Chéimeanna Praiticiúla Eile

Más mian leat do thuiscint ar cheathair-chrainn a dhoimhniú seachas a bheith ag léamh fúthu, is é an cur chuige is éifeachtaí ná ceann a thógáil ó thaobh amhairc de. Cruthaigh feidhmchlár simplí ar chanbhás ina gcuireann cliceáil pointí leis, agus féachaint ar fhoroinnt an chrainn i bhfíor-am. Cuir dronuilleog cheist raoin leis ar féidir leat a tharraingt timpeall agus aibhsigh na pointí a aimsíonn sé. Tógann an idirghníomhaíocht phraiticiúil seo le hintiúlacht nach féidir le haon mhéid léitheoireachta a mheaitseáil - feicfidh tú láithreach cén fáth a chruthaíonn sonraí cnuasaithe crainn níos doimhne agus conas a chuireann iompar bearradh le linn fiosrúcháin deireadh le raon mór spáis.

I gcás feidhmchláir táirgthe, smaoinigh ar na treoirlínte seo: má tá do shonraí ina gcónaí i mbunachar sonraí, bain úsáid as an innéacsú spásúil a sholáthraíonn do bhunachar sonraí (innéacsanna PostGIS, MySQL Spatial, MongoDB 2dsphere) seachas cuadchrainn a chur i bhfeidhm sa chód iarratais. Má tá léirshamhlú taobh an chliaint nó próiseáil cuimhneacháin á déanamh agat, tugann leabharlanna ar nós d3-quadtree le haghaidh JavaScript nó pyquadtree do Python feidhmithe a bhfuil tástáil catha orthu. Agus má tá ardán á thógáil agat a láimhseálann sonraí suímh de chineál ar bith - ó sheoltaí custaiméirí go ródú seachadta go bainistíocht críche - infheistigh an t-am chun innéacsú spásúlachta a thuiscint, mar go gcruthóidh sé go bunúsach cad is féidir le d'iarratas a dhéanamh ar scála.

Is prionsabal níos leithne san eolaíocht ríomhaireachta é Quadtrees: gurb é an struchtúr a roghnaíonn tú do do shonraí a shocraíonn na ceisteanna is féidir leat a fhreagairt go héifeachtach. Is féidir le liosta comhréidh de chomhordanáidí "tabhair na pointí go léir dom" a fhreagairt, ach is féidir le quadtree freagra a thabhairt "tabhair dom na pointí go léir in aice le anseo" - agus is féidir é a dhéanamh go tapa go leor chun mothú ar an toirt. I ndomhan ina bhfuil comhpháirt spásúil ag 73% de shonraí gnó de réir meastacháin tionscail, ní hamháin go bhfuil an cumas sin acadúil. Is buntáiste iomaíoch é.

Ceisteanna Coitianta

Cad is cuadrann ann agus conas a oibríonn sé?

Is struchtúr sonraí crann-bhunaithe é cuadrann a roinneann go hathchúrsach spás déthoiseach ina cheithre cheathrú chothroma. Is féidir le gach nód líon teoranta pointí sonraí a shealbhú sula roinntear iad i gceithre nód linbh. Déanann an deighilt ordlathach seo ceisteanna spásúlachta - cosúil le gach pointe a aimsiú laistigh d'achar ar leith - thar a bheith tapa, ag laghdú am cuardaigh ó líneach go logartamach i bhformhór na gcásanna praiticiúla.

Cá úsáidtear cuadchrainn go coitianta i bhfeidhmchláir fhíorshaoil?

Cumhachtaíonn Quadtrees raon leathan córas lena n-áirítear léarscáileanna digiteacha a bhfuil feidhmiúlacht pinch-go-zoom acu, deais rianaithe cabhlaigh fíor-ama, innill bhrath imbhuailtí físchluiche, agus córais faisnéise geografacha a phróiseálann na milliúin fiosrúchán spásúlachta in aghaidh an tsoicind. Is féidir le haon fheidhmchlár a bhfuil gá aige le cuardach éifeachtach, ionsá nó bainistiú a dhéanamh ar réada atá scaipthe thar spás déthoiseach leas a bhaint as innéacsú cuadrann.

Conas a chuirtear cuadchrainn i gcomparáid le struchtúir sonraí spásúla eile?

Murab ionann agus eangacha comhréidh, cuireann cuadchrainn a dtaifeach in oiriúint do dhlús na sonraí — fanann limistéir tearca garbh agus foroinneann réigiúin phlódaithe tuilleadh. I gcomparáid le crainn k-d, tá cuadchrainn níos simplí a chur i bhfeidhm agus is fearr a oireann do shonraí 2T a dháiltear go haonfhoirmeach. Láimhseálann R-crainn réigiúin fhorluiteacha ar bhealach níos galánta, ach bíonn bua ag na ceathrúchrainn ar luas ionsáite agus is fusa iad a chomhthreomharú le haghaidh ualaí oibre fíor-ama.

An féidir le quadtrees cabhrú le feidhmíocht a bharrfheabhsú i mbogearraí gnó?

Go deimhin. Baineann aon uirlis ghnó a láimhseálann sonraí suímh, anailísíocht spáis, nó deais idirghníomhacha leas as leas iomlán a bhaint as quadtree. Déanann ardáin cosúil le Mewayz, OS gnó 207-modúl ag tosú ar $19/mo, giaráil struchtúir sonraí éifeachtacha taobh thiar de na radhairc chun eispéiris thapa, fhreagracha a sheachadadh - ó léarscáileanna aimsitheora stórais go hanailís fíor-ama thar na mílte pointe sonraí.