Ro-ràdh eadar-ghnìomhach air quadtrees

Carson a tha Quadtrees nas cudromaiche na tha thu a’ smaoineachadh

Gach uair a bhios tu a’ pinadh-gu-zoom air mapa didseatach, a’ faighneachd do thaighean-bìdh faisg air làimh, no a’ coimhead air rianadair cabhlach fìor-ùine ag ùrachadh dusanan de dh’ ìomhaighean carbaid gun do bhrobhsair a ’bleith gu stad, tha deagh chothrom ann gu bheil quadtree a’ dèanamh an togail trom air cùl na seallaidhean. Tha Quadtrees mar aon de na structaran dàta eireachdail sin nach cluinn a’ mhòr-chuid de dhaoine mu dheidhinn, ach tha iad gu sàmhach a’ toirt cumhachd do chuid de na siostaman as deatamaiche coileanaidh ann am bathar-bog an latha an-diugh - bho lorg bualadh geama bhidio gu siostaman fiosrachaidh cruinn-eòlasach a’ giullachd milleanan de cheistean spàsail gach diog. Chan eil a bhith a’ tuigsinn mar a tha iad ag obair dìreach gad dhèanamh nad leasaiche nas fheàrr; bidh e gu bunaiteach ag atharrachadh mar a smaoinicheas tu air eagrachadh agus sgrùdadh tro dhàta spàsail. Co-dhiù a tha thu a’ togail àrd-ùrlar loidsistigs lìbhrigidh, deas-bhòrd anailis stèidhichte air àite, no dìreach a’ feuchainn ri 50,000 puing dàta a thoirt seachad air canabhas gun a bhith a’ bualadh air a’ bhrobhsair, tha quadtrees a’ tabhann fuasgladh a tha an dà chuid intuitive agus air leth èifeachdach.

Dè dìreach a th’ ann an Quadtree?

Is e structar dàta craoibhe a th’ ann an quadtree far a bheil dìreach ceathrar chloinne aig gach nód a-staigh, gach fear a’ riochdachadh aon cheathramh de rùm dà-mheudach. Smaoinich air roinn ceàrnagach a ghabhail agus a roinn ann an ceithir ceàrnagan co-ionann - iar-thuath, ear-thuath, iar-dheas agus ear-dheas. Faodar gach aon de na ceàrnagan sin a roinn ann an ceithir ceàrnagan eile, agus mar sin air adhart, a-rithist, gus an ruig thu suidheachadh stad. Tha an suidheachadh stad sin mar as trice an dàrna cuid doimhneachd as àirde no stairsneach airson cia mheud puing dàta as urrainn aon nód a chumail mus fheum e sgoltadh.

Tha bòidhchead an dòigh-obrach seo na laighe na nàdar atharrachail. Bidh sgìrean dùmhail le puingean dàta air an roinneadh ann an ceallan nas fèarr agus nas fèarr, fhad ‘s a tha raointean gann fhathast mar roinnean mòra gun roinneadh. Chruthaicheadh ​​​​ceithir-chraobh a bhiodh a’ stòradh àiteachan 10,000 bùth cofaidh air feadh dùthaich fo-roinnean domhainn, mionaideach thairis air Manhattan - far am faodadh 300 bùth a bhith taobh a-staigh beagan chilemeatairean ceàrnagach - agus aig an aon àm a’ cumail raointean mòra de Wyoming dùthchail mar aon nód gun sgaradh anns a bheil neoni no aon phuing. Is e an rùn atharrachail seo a tha a’ dèanamh ceithir-chraobhan cho cumhachdach an taca ri cliath rèidh, a chuireadh às do mhòran cuimhne air ceallan falamh.

Chaidh iomradh a thoirt air a’ bhun-bheachd an toiseach le Raphael Finkel agus J.L. Bentley ann an 1974, agus bhon uair sin tha e air a dhol a-steach do ghrunn atharrachaidhean: bidh point quadtrees a’ stòradh paidhrichean co-chomharran fa leth, tha cuad-chraobhan sgìreil a’ riochdachadh raointean spàsail (feumail airson teannachadh ìomhaighean), agus cead-chraobhan oir loidhnichean làimhseachaidh agus lùban. Bidh gach caochladair a’ dèanamh an fheum as fheàrr airson diofar chùisean cleachdaidh, ach tha am prìomh phrionnsapal fo-roinneadh ath-chuairteach fhathast mar a tha e thairis orra uile.

Mar a dh’obraicheas cuir a-steach agus ceasnachadh

Gus puing a chuir a-steach do cheithir-chraobh, tòisichidh tu aig a’ bhun-nòd agus obraich a-mach cò dhe na ceithir quadrant anns a bheil a’ phuing. Bidh thu an uairsin a’ dol air ais a-steach don nód leanaibh aig a’ cheathramh sin agus ag ath-aithris a’ phròiseas. Ma ruigeas tu nód duille nach eil air a dhol thairis air a chomas (mar as trice air a shuidheachadh gu 1 no 4 puingean), bidh thu dìreach a’ stòradh a’ phuing an sin. Ma tha an duilleag mar-thà aig làn chomas, bidh e air a roinn ann an ceathrar chloinne, ag ath-riarachadh na puingean a th 'ann mar-thà nam measg, agus an uairsin a' cur a 'phuing ùr a-steach don leanabh iomchaidh. Mar as trice bidh am pròiseas seo a’ crìochnachadh ann an ùine O (log n) airson cuairteachadh cothromach, ged a dh’ fhaodadh na suidheachaidhean as miosa le dàta làn chruinneachadh coileanadh a lughdachadh.

Raoin a’ ceasnachadh – a’ lorg a h-uile puing taobh a-staigh raon ceart-cheàrnach sònraichte – ’s e sin far a bheil ceithir-chraobhan a’ deàrrsadh. An àite a bhith a’ sgrùdadh a h-uile puing anns an t-seata dàta agad (gnìomh O(n)), bidh thu a’ tòiseachadh aig an fhreumh agus a’ faighneachd ceist shìmplidh aig gach nód: a bheil crìoch an nód seo a’ trasnadh leis a’ cheart-cheàrnach sgrùdaidh agam? Mura h-eil, bidh thu a’ gearradh an fho-chraobh gu lèir - is dòcha cuir às do mhìltean de phuingean bho bheachdachadh ann an aon choimeas. Ma tha eadar-ghearradh ann, thig thu air ais a-steach don chloinn iomchaidh. Thèid puingean a lorgar ann an nodan-duilleig a tha taobh a-staigh ceart-cheàrnach an rannsachaidh a chur ris an t-seata thoraidhean.

Beachdaich air eisimpleir phractaigeach: tha stòr-dàta agad de 100,000 àite teachdaiche agus feumaidh tu a h-uile duine a lorg taobh a-staigh radius 5-cilemeatair bho fhosgladh stòr ùr. Feumaidh dòigh-obrach brùideil 100,000 àireamhachadh astar. Dh’ fhaodadh quadtree air a dheagh thogail sin a lughdachadh gu dìreach 200-500 seic le bhith a’ cur às gu sgiobalta de roinnean cruinn-eòlasach gu lèir nach eil gu soilleir a’ dol thairis air an raon sgrùdaidh agad. Tha sin na leasachadh coileanaidh de 200x no barrachd - an diofar eadar ceist a’ toirt 800 milliseconds agus a’ gabhail 4 milliseconds.

Aplacaidean fìor-shaoghal a tha a’ ruith air Quadtrees

Tha cleachdadh quadtrees a’ leudachadh fada seachad air saidheans coimpiutair acadaimigeach. Tha iad bunaiteach do shiostaman a bhios na billeanan de dhaoine a’ cleachdadh gach latha, gu tric gun a bhith gan tuigsinn.

• Mapadh is seòladh: Cleachdaidh seirbheisean leithid Google Maps agus Mapbox siostaman leacag ceithir-chraoibh gus ìomhaighean mapa a fhrithealadh. Bidh gach ìre zoom a’ roinn leacan ann an ceathrar chloinne, agus is e sin as coireach gu bheil co-chomharran leac-mhapa a’ leantainn pàtran z/x/y a tha mar sgàthan air seòladh quadtree. Nuair a ghluaiseas tu a-steach do bhloca baile-mòr, chan eil ach na leacan àrd-rèiteachaidh iomchaidh a’ luchdachadh - bidh an còrr den t-saoghal a’ fuireach aig rùn garbh.
• A’ lorg thubaistean ann an geamannan: Bidh einnseanan geam a’ cleachdadh ceithir-chraobhan (agus an co-aoisean 3D, octrees) gus faighinn a-mach gu h-èifeachdach nuair a bhuaileas nithean. An àite a bhith a’ dèanamh deuchainn air a h-uile paidhir de nithean - trom-laighe O (n²) le 1,000 aonad air an sgrion - cha bhith an einnsean a’ sgrùdadh ach nithean aig a bheil an aon chealla quadtree, a’ lughdachadh sgrùdaidhean gu àireamh a ghabhas làimhseachadh.
• Dùmhlachadh ìomhaigh: 'S urrainn dha ceithir-chraobhan sgìreil dealbhan a dhlùthadh le bhith a' ceangal piogsail faisg air làimh a bhios a' roinn dhathan coltach ri blocaichean nas motha. Tha seo mar bhunait air cuid de dh’ algoirmean teannachaidh a choileanas co-mheasan teannachaidh 10:1 fhad ‘s a chumas iad dìlseachd lèirsinneach ann an raointean le mion-fhiosrachadh.
• Riaghladh cabhlach agus logistics: Bidh companaidhean lìbhrigidh a’ cleachdadh clàr-amais spàsail gus draibhearan a mhaidseadh le òrdughan faisg air làimh ann an àm fìor. Leigidh quadtree le siostam sgaoilidh a’ cheist sa bhad “dè na 5 draibhearan as fhaisge air an àite togail seo?” thairis air cabhlach de mhìltean de charbadan ag ùrachadh an suidheachadh GPS a h-uile diog no dhà.
• Anailis geospatial: Bidh àrd-ùrlaran a bhios a’ cruinneachadh dàta gnìomhachais stèidhichte air àite - mapaichean dùmhlachd teachdaiche, optimization fearann reic, mion-sgrùdadh suidheachadh stòrais - an urra ri structaran dàta spàsail gus na ceistean sin a dhèanamh eadar-ghnìomhach seach baidse-ghiollachd.

Is e am prìomh shealladh air cùl quadtrees nach fheum a’ mhòr-chuid de cheistean spàsail a’ mhòr-chuid den dàta a sgrùdadh. Le bhith ag eagrachadh àite gu rangachd, bidh thu ag atharrachadh rannsachaidhean feachd brùideil gu slighean targaidte - a’ tionndadh diogan gu milliseconds agus a’ dèanamh eadar-ghnìomhachd fìor-ùine comasach eadhon le stòran-dàta mòr.

A’ Togail Quadtree From Scratch

Tha e iongantach furasta bruidhinn mu bhith a’ cur quadtree bunaiteach an gnìomh, eadhon dha luchd-leasachaidh eadar-mheadhanach. Feumaidh an structar bunaiteach dìreach beagan phàirtean: crìoch (an raon ceart-cheàrnach a tha an nód a’ còmhdach), comas (na puingean as àirde mus tèid a sgaradh), sreath de phuingean, agus iomraidhean air ceithir nòtaichean cloinne (neo-dhligheach an toiseach). Gabhaidh an gnìomh cuir a-steach gu lèir a sgrìobhadh ann an nas lugha na 30 loidhne de chòd anns a’ mhòr-chuid de chànanan.

Cruthaichidh an obrachadh sgaraidh ceithir nodan cloinne ùra, gach fear a’ còmhdachadh aon cheathramh de chrìoch a’ phàrant. Airson pàrant le crìoch (x, y, leud, àirde), gheibh leanabh an ear-thuath (x + leud / 2, y, leud / 2, àirde / 2), gheibh an iar-thuath (x, y, leud / 2, àirde / 2), agus mar sin air adhart. An dèidh sgoltadh, tha na puingean a th 'ann mar-thà air an ath-riarachadh a-steach don chloinn iomchaidh. Is e mearachd cumanta a th’ ann a bhith a’ dìochuimhneachadh sreath phuingean a’ phàrant a ghlanadh às deidh an ath-riarachadh, a tha a’ leantainn gu toraidhean dùblaichte rè cheistean.

Airson cleachdadh cinneasachaidh, tha grunn optimizations cudromach. Mar as trice bidh a bhith a’ suidheachadh comas an nòta gu 4-8 puingean nas fheàrr na comas 1, leis gu bheil e a’ lughdachadh doimhneachd craoibhe agus os cionn nithean nod. Le bhith a’ cur crìoch doimhneachd as àirde (mar as trice ìrean 8-12) casg air cùisean pathological far a bheil mòran phuingean a’ co-roinn co-chomharran co-ionann bho bhith a’ cruthachadh chraobhan domhainn gun chrìoch. Agus airson stòran-dàta fiùghantach far am bi puingean a’ gluasad - leithid tracadh carbaid - bidh thu ag iarraidh inneal gluasaid no ro-innleachd gus a’ chraobh ath-thogail bho àm gu àm, leis nach bi quadtrees a’ cothromachadh leotha fhèin mar a bhios craobhan dubh-dubh.

Quadtrees ann an àrd-ùrlaran gnìomhachais agus anailis

Bidh àrd-ùrlaran gnìomhachais an latha an-diugh a’ dèiligeadh barrachd is barrachd ri dàta spàsail, ge bith an e àiteachan teachdaiche a th’ ann, sònaichean lìbhrigidh, sgìrean reic no tracadh maoin. Chan e an dùbhlan dìreach an dàta seo a stòradh - tha e ga dhèanamh comasach a cheasnachadh ann an àm fìor aig sgèile. Nuair a dh’ fheumas gnìomhachas a tha ag obair thairis air 50 baile-mòr dùmhlachd teachdaiche fhaicinn, draibhearan lìbhrigidh slighe, no mion-sgrùdadh a dhèanamh air coileanadh reic roinneil, bidh an ro-innleachd clàr-amais spàsail bunaiteach a’ dearbhadh a bheil an deas-bhòrd a’ luchdachadh ann an 200 milliseconds no 20 diog.

Is e seo aon adhbhar gum bi àrd-ùrlaran mar Mewayz - a tha ag aonachadh 207 modal thairis air CRM, fàirdeal, riaghladh cabhlach, glèidheadh, agus anailisean ann an aon OS gnìomhachais - a’ faighinn buannachd bho làimhseachadh dàta spàsail èifeachdach fon chochall. Nuair a dh’ fheumas modal riaghlaidh cabhlach 500 carbad gnìomhach a thaisbeanadh air mapa, no nuair a sheallas modal CRM 138,000+ àite luchd-cleachdaidh airson dealbhadh fearainn, chan eil dòighean-obrach naive dìreach a’ sgèile. Tha structaran clàr-amais spàsail leithid quadtrees (no an stòr-dàta co-ionann, leithid PostGIS R-trees agus clàran-amais spàsail MySQL) ga dhèanamh comasach na feartan sin a thabhann gun a bhith feumach air bathar-cruaidh ìre iomairt.

Do ghnìomhachasan a tha a’ luachadh àrd-ùrlaran, tha an takeaway pragtaigeach: chan eil innealan a làimhsicheas dàta àite agus àite gu math dìreach a’ cleachdadh algoirmean sùbailte air a shon. Tha iad a’ dèanamh an eadar-dhealachaidh eadar siostam glèidhidh a sheallas sa bhad solaraichean seirbheis a tha rim faighinn taobh a-staigh 10 cilemeatair agus siostam a bheir 8 diogan airson na h-aon toraidhean a luchdachadh. Tha coileanadh aig an ìre seo gu dìreach ag eadar-theangachadh gu eòlas luchd-cleachdaidh agus, aig a’ cheann thall, teachd-a-steach.

Quadtrees vs. Structaran Dàta Spàsail eile

Chan e Quadtrees an aon roghainn airson clàr-amais spàsail, agus le bhith a’ tuigsinn nan roghainnean eile cuidichidh e thu gus an inneal cheart a thaghadh. R-craobhan, air a chleachdadh gu farsaing ann an stòran-dàta mar PostGIS agus modal R* Tree aig SQLite, cuir dàta air dòigh gu ceart-cheàrnaich as ìsle agus làimhsich ceistean raon agus rannsachaidhean nàbaidh gu h-èifeachdach. Mar as trice bidh iad a’ coileanadh nas fheàrr na ceithir-chraobhan airson stòradh stèidhichte air diosc leis gu bheil iad a’ lughdachadh gnìomhachd I/O, agus is e sin as coireach gu bheil a’ mhòr-chuid de stòran-dàta spàsail a’ cleachdadh caochlaidhean R-tree air an taobh a-staigh seach quadtrees.

Craobhan K-d àite dealachaidh a’ cleachdadh sgaraidhean co-thaobhadh axis eile (an toiseach le x, an uairsin le y, an uairsin le x a-rithist) agus tha iad air leth math airson rannsachaidhean nàbaidh as fhaisge ann am meudan meadhanach. Tha iad buailteach a bhith nas fheàrr na ceithir-chraobhan nuair a tha an tomhasachd ìosal agus an dàta statach, ach tha iad nas duilghe ùrachadh gu dinamach. Bidh Geohashes a’ cleachdadh dòigh-obrach eadar-dhealaichte gu tur, a’ còdachadh leud is domhan-leud ann an aon shreang far a bheil ro-leasanan co-roinnte a’ comharrachadh cho faisg air farsaingeachd - gan dèanamh air leth freagarrach airson clàr-amais is tasgadan stòr-dàta ach nach eil cho sùbailte airson ceistean raon neo-riaghailteach.

Bidh Quadtrees a’ cumail an cuid fhèin ann an suidheachaidhean a bhios a’ cluich a rèir an neartan: clàr-amais spàsail ann an cuimhne, stòran-dàta fiùghantach le cuir a-steach agus cuir às gu tric, tagraidhean fradharc far a bheil structar clèithe rangachd a’ mapadh gu nàdarra gus ìrean a shìneadh, agus suidheachaidhean far a bheil sìmplidheachd buileachaidh cudromach. Airson tagradh aghaidh aghaidh a bheir seachad 10,000 puing dàta air canabhas le pan-and-zoom, nì quadtree a chaidh a chuir an gnìomh ann an 100 loidhne de JavaScript nas fheàrr na fuasgladh sam bith le taic stòr-dàta dìreach le bhith a’ cur às do latency lìonra.

Tòiseachadh: Na h-Ath Cheumannan Practaigeach

Ma tha thu airson do thuigse air quadtrees a dhoimhneachadh nas fhaide na bhith a’ leughadh mun deidhinn, ’s e an dòigh as èifeachdaiche fear a thogail gu fradharcach. Cruthaich tagradh canabhas sìmplidh far am bi cliogadh a’ cur puingean ris, agus coimhead air a’ chraobh a’ fo-roinneadh ann an àm fìor. Cuir ceart-cheàrnach ceist-raoin ris as urrainn dhut a shlaodadh timcheall agus comharraich na puingean a lorg e. Bidh an eadar-obrachadh làimhseachail seo a’ togail tuigse nach urrainn meud leughaidh sam bith a mhaidseadh - chì thu sa bhad carson a tha dàta cruinnichte a’ cruthachadh chraobhan nas doimhne agus mar a bhios giùlan pruning tro cheistean a’ cur às do raointean mòra de dh’ àite.

Airson tagraidhean cinneasachaidh, beachdaich air an stiùireadh seo: ma tha an dàta agad a’ fuireach ann an stòr-dàta, cleachd an clàr-amais spàsail a tha an stòr-dàta agad a’ toirt seachad (PostGIS, MySQL Spatial, clàran-amais MongoDB 2dsphere) seach a bhith a’ cur an gnìomh quadtrees ann an còd an tagraidh. Ma tha thu a’ dèanamh fradharc taobh teachdaiche no giollachd cuimhneachaidh, bheir leabharlannan leithid d3-quadtree airson JavaScript no pyquadtree airson Python buileachadh blàir dhut. Agus ma tha thu a’ togail àrd-ùrlar a làimhsicheas seòrsa sam bith de dhàta àite - bho sheòlaidhean teachdaiche gu slighe lìbhrigidh gu riaghladh fearainn - cuir an ùine gus clàr-amais spàsail a thuigsinn, oir bheir e cumadh bunaiteach air na nì an tagradh agad aig sgèile.

Tha Quadtrees a’ riochdachadh prionnsapal nas fharsainge ann an saidheans coimpiutaireachd: gum bi an structar a thaghas tu airson an dàta agad a’ dearbhadh nan ceistean as urrainn dhut a fhreagairt gu h-èifeachdach. Faodaidh liosta rèidh de cho-chomharran freagairt “thoir dhomh a h-uile puing,” ach faodaidh quadtree freagairt “thoir dhomh na puingean gu lèir faisg air an seo” - agus faodaidh e a dhèanamh luath gu leòr airson a bhith a’ faireachdainn sa bhad. Ann an saoghal far a bheil pàirt spàsail aig 73% de dhàta gnìomhachais a rèir tuairmsean gnìomhachais, chan eil an comas sin dìreach acadaimigeach. 'S e buannachd fharpaiseach a th' ann.

Ceistean Bitheanta

Dè a th’ ann an quadtree agus ciamar a tha e ag obair?

Is e structar dàta stèidhichte air craobhan a th’ ann an quadtree a bhios gu ath-chùrsach a’ roinn àite dà-mheudach ann an ceithir quadrant co-ionann. Faodaidh gach nód àireamh chuingealaichte de phuingean dàta a chumail mus tèid a roinn ann an ceithir nodan cloinne. Bidh an sgaradh rangachd seo a’ dèanamh cheistean spàsail - mar a bhith a’ lorg a h-uile puing taobh a-staigh raon sònraichte - gu math luath, a’ lughdachadh ùine sgrùdaidh bho shreathach gu logarithmach anns a’ mhòr-chuid de shuidheachaidhean practaigeach.

Càit a bheil ceithir-chraobhan gu tric air an cleachdadh ann am prògraman san t-saoghal fhìor?

Tha cumhachd aig Quadtrees air raon farsaing de shiostaman a’ gabhail a-steach mapaichean didseatach le comas-gnìomh pinch-to-zoom, clàran-amais tracadh cabhlach fìor-ùine, einnseanan lorg tubaist geama bhidio, agus siostaman fiosrachaidh cruinn-eòlasach a’ giullachd milleanan de cheistean spàsail gach diog. Faodaidh tagradh sam bith a dh’ fheumas a bhith a’ lorg, a’ cuir a-steach no a’ riaghladh nithean air an sgaoileadh thairis air àite dà-mheudach gu h-èifeachdach bho chlàr-amais quadtree.

Ciamar a tha ceithir-chraobhan an coimeas ri structaran dàta spàsail eile?

Eu-coltach ri cliathan còmhnard, bidh quadtrees ag atharrachadh an rùn a rèir dùmhlachd dàta - bidh raointean gann a’ fuireach garbh fhad ‘s a bhios roinnean làn sluaigh a’ fo-roinneadh tuilleadh. An coimeas ri craobhan k-d, tha quadtrees nas sìmplidh a chur an gnìomh agus nas freagarraiche airson dàta 2D a tha air a chuairteachadh gu co-ionnan. Bidh craobhan R a’ làimhseachadh roinnean a tha a’ dol thairis air nas gràsmhoire, ach bidh ceithir-chraobhan a’ buannachadh air astar cuir a-steach agus tha iad nas fhasa a bhith co-shìnte airson eallach obrach fìor-ùine.

An cuidich quadtrees an coileanadh as fheàrr ann am bathar-bog gnìomhachais?

Gu dearbh. Tha inneal gnìomhachais sam bith a bhios a’ làimhseachadh dàta àite, mion-sgrùdadh spàsail, no clàran-dannsa eadar-ghnìomhach a’ faighinn buannachd bho optimization quadtree. Bidh àrd-ùrlaran mar Mewayz, OS gnìomhachais 207-modal a’ tòiseachadh aig $19/mo, a’ luathachadh structaran dàta èifeachdach air cùl na seallaidhean gus eòlasan luath, freagairteach a lìbhrigeadh - bho mhapaichean locator stòr gu mion-sgrùdaidhean fìor-ùine thar mìltean de phuingean dàta.