Cyflwyniad rhyngweithiol i quadtrees

Pam Mae Ced-coed yn Bwysig Mwy Nar Eich Barn

Bob tro y byddwch chi'n pinsio i chwyddo ar fap digidol, yn holi bwytai cyfagos, neu'n gwylio traciwr fflyd amser real yn diweddaru dwsinau o eiconau cerbydau heb i'ch porwr dorri i stop, mae siawns dda bod quadtree yn gwneud y gwaith codi trwm y tu ôl i'r llenni. Mae Quadtrees yn un o'r strwythurau data cain hynny nad yw'r rhan fwyaf o bobl byth yn clywed amdanynt, ac eto maent yn dawel yn pweru rhai o'r systemau mwyaf hanfodol o ran perfformiad mewn meddalwedd modern - o ganfod gwrthdrawiadau gêm fideo i systemau gwybodaeth ddaearyddol sy'n prosesu miliynau o ymholiadau gofodol yr eiliad. Nid yw deall sut maen nhw'n gweithio yn eich gwneud chi'n ddatblygwr gwell yn unig; mae'n newid yn sylfaenol sut rydych chi'n meddwl am drefnu a chwilio trwy ddata gofodol. P'un a ydych chi'n adeiladu llwyfan logisteg dosbarthu, dangosfwrdd dadansoddeg seiliedig ar leoliad, neu'n ceisio rhoi 50,000 o bwyntiau data ar gynfas heb chwalu'r porwr, mae quadtrees yn cynnig datrysiad sy'n reddfol ac yn hynod o effeithlon.

Beth Yn union Yw Coeden Bedydd?

Adeiledd data coeden yw cwadrant lle mae gan bob nod mewnol bedwar plentyn yn union, pob un yn cynrychioli un cwadrant o ofod dau ddimensiwn. Dychmygwch gymryd rhanbarth sgwâr a'i rannu'n bedwar sgwâr cyfartal - gogledd-orllewin, gogledd-ddwyrain, de-orllewin a de-ddwyrain. Gellir rhannu pob un o'r sgwariau hynny ymhellach yn bedwar sgwâr arall, ac yn y blaen, dro ar ôl tro, nes i chi gyrraedd rhywfaint o gyflwr stopio. Mae'r amod atal hwnnw fel arfer naill ai'n ddyfnder uchaf neu'n drothwy ar gyfer faint o bwyntiau data y gall un nod eu dal cyn bod angen iddo hollti.

Mae harddwch y dull hwn yn gorwedd yn ei natur ymaddasol. Mae ardaloedd trwchus gyda phwyntiau data yn cael eu hisrannu'n gelloedd manach a manach, tra bod ardaloedd gwasgaredig yn parhau i fod yn rhanbarthau mawr, heb eu rhannu. Byddai quadtree sy'n storio lleoliadau 10,000 o siopau coffi ledled gwlad yn creu israniadau dwfn, manwl dros Manhattan - lle gallai fod 300 o siopau o fewn ychydig gilometrau sgwâr - wrth gadw darnau helaeth o Wyoming wledig fel nod sengl, heb ei hollti sy'n cynnwys sero neu un pwynt. Y cydraniad addasol hwn sy'n gwneud pedair coeden mor bwerus o gymharu â grid gwastad, a fyddai'n gwastraffu llawer iawn o gof ar gelloedd gwag.

Disgrifiwyd y cysyniad am y tro cyntaf gan Raphael Finkel a J.L. Bentley ym 1974, ac ers hynny mae wedi canghennu i sawl amrywiad: mae pedtrees pwynt yn storio parau cyfesurynnau unigol, mae pedadreoedd rhanbarth yn cynrychioli ardaloedd gofodol (defnyddiol ar gyfer cywasgu delweddau), ac pedtrees ymyl llinellau handlen a chromliniau. Mae pob amrywiad yn optimeiddio ar gyfer achosion defnydd gwahanol, ond mae'r egwyddor isrannu cylchol graidd yn aros yr un fath ar draws pob un ohonynt.

Sut mae Mewnosod a Chwestiynu'n Gweithio

I fewnosod pwynt i mewn i bedren, rydych chi'n dechrau wrth y nod gwraidd ac yn penderfynu i ba un o'r pedwar cwadrant y mae'r pwynt yn syrthio. Yna byddwch yn mynd yn ôl i mewn i nod plentyn y cwadrant hwnnw ac yn ailadrodd y broses. Os byddwch chi'n cyrraedd nod dail nad yw wedi mynd y tu hwnt i'w gapasiti (fel arfer wedi'i osod i 1 neu 4 pwynt), yn syml iawn rydych chi'n storio'r pwynt yno. Os yw'r ddeilen eisoes yn llawn, mae'n rhannu'n bedwar o blant, yn ailddosbarthu ei phwyntiau presennol yn eu plith, ac yna'n mewnosod y pwynt newydd yn y plentyn priodol. Mae'r broses hon fel arfer yn cwblhau mewn amser O(log n) ar gyfer dosbarthiad cytbwys, er y gall senarios gwaethaf gyda data clystyrog iawn ddiraddio perfformiad.

Cwestiynu ystod — dod o hyd i'r holl bwyntiau o fewn ardal betryal benodol — yw lle mae pedair coeden yn disgleirio mewn gwirionedd. Yn hytrach na gwirio pob pwynt yn eich set ddata (gweithrediad O(n)), rydych chi'n dechrau wrth y gwraidd ac yn gofyn cwestiwn syml ym mhob nod: a yw ffin y nod hwn yn croestorri â'm petryal chwilio? Os na, rydych chi'n tocio'r is-goeden gyfan - gan ddileu miloedd o bwyntiau o ystyriaeth mewn un gymhariaeth o bosibl. Os oes croestoriad, byddwch yn dychwelyd i'r plant perthnasol. Mae pwyntiau a ganfuwyd mewn nodau dail sydd o fewn y petryal chwilio yn cael eu hychwanegu at y set canlyniadau.

Ystyriwch enghraifft ymarferol: mae gennych set ddata o 100,000 o leoliadau cwsmeriaid ac mae angen i chi ddod o hyd i bawb o fewn radiws o 5 cilomedr i agor siop newydd. Mae angen 100,000 o gyfrifiadau pellter ar gyfer dull 'n Ysgrublaidd. Gallai cwadtree wedi'i hadeiladu'n dda leihau hynny i ddim ond 200-500 o wiriadau trwy ddileu rhanbarthau daearyddol cyfan yn gyflym nad ydynt yn amlwg yn gorgyffwrdd â'ch ardal chwilio. Mae hynny'n welliant perfformiad o 200x neu fwy - y gwahaniaeth rhwng ymholiad sy'n cymryd 800 milieiliad a chymryd 4 milieiliad.

Ceisiadau Byd Go Iawn sy'n Rhedeg ar Quadtrees

Mae cymwysiadau quadtrees yn ymestyn ymhell y tu hwnt i wyddoniaeth gyfrifiadurol academaidd. Maent yn sylfaenol i systemau y mae biliynau o bobl yn eu defnyddio bob dydd, yn aml heb sylweddoli hynny.

• Mapio a llywio: Mae gwasanaethau fel Google Maps a Mapbox yn defnyddio systemau teils tebyg i bedtree i wasanaethu delweddau mapiau. Mae pob lefel chwyddo yn isrannu teils yn bedwar plentyn, a dyna pam mae cyfesurynnau teils map yn dilyn patrwm z/x/y sy'n adlewyrchu cyfeiriad pedair coeden. Pan fyddwch chi'n chwyddo i mewn i floc dinas, dim ond y teils cydraniad uchel perthnasol sy'n llwytho - mae gweddill y byd yn aros ar gydraniad bras.
• Canfod gwrthdrawiadau mewn gemau: Mae peiriannau gêm yn defnyddio pedair coeden (a'u cymar 3D, wythfedau) i ganfod yn effeithlon pan fydd gwrthrychau'n gwrthdaro. Yn lle profi pob pâr o wrthrychau - hunllef O(n²) gyda 1,000 o endidau ar y sgrin - dim ond gwrthrychau sy'n rhannu'r un cell quadtree y mae'r injan yn eu gwirio, gan leihau sieciau i rif hylaw.
• Cywasgu delwedd: Gall pedair coeden rhanbarth gywasgu delweddau drwy gyfuno picsel cyfagos sy'n rhannu lliwiau tebyg i flociau mwy. Dyma sail rhai algorithmau cywasgu sy'n cyflawni cymarebau cywasgu 10:1 tra'n cynnal ffyddlondeb gweledol mewn ardaloedd o fanylder isel.
• Rheoli fflyd a logisteg: Mae cwmnïau dosbarthu yn defnyddio mynegeio gofodol i baru gyrwyr ag archebion cyfagos mewn amser real. Mae quadtree yn gadael i system anfon ateb y cwestiwn "pa 5 gyrrwr sydd agosaf at y lleoliad codi hwn?" ar draws fflyd o filoedd o gerbydau yn diweddaru eu safleoedd GPS bob ychydig eiliadau.
• Dadansoddeg geo-ofodol: Mae llwyfannau sy'n cydgrynhoi data busnes sy'n seiliedig ar leoliad - mapiau dwysedd cwsmeriaid, optimeiddio tiriogaeth gwerthu, dadansoddiad o leoliadau siopau - yn dibynnu ar strwythurau data gofodol i wneud yr ymholiadau hyn yn rhyngweithiol yn hytrach na'u swp-brosesu.

Y mewnwelediad allweddol y tu ôl i quadtrees yw nad oes angen i'r rhan fwyaf o ymholiadau gofodol archwilio'r rhan fwyaf o'r data. Trwy drefnu gofod yn hierarchaidd, rydych chi'n trawsnewid chwiliadau 'n ysgrublaidd yn fannau croesi wedi'u targedu - gan droi eiliadau yn filieiliadau a gwneud rhyngweithedd amser real yn bosibl hyd yn oed gyda setiau data enfawr.

Adeiladu Cwadren o'r Scratch

Mae'n rhyfeddol o hawdd mynd at y gwaith o weithredu quadtree sylfaenol, hyd yn oed i ddatblygwyr canolradd. Dim ond ychydig o gydrannau sydd eu hangen ar y strwythur craidd: a ffin (yr ardal hirsgwar y mae'r nod yn ei gorchuddio), cynhwysedd (uchafswm o bwyntiau cyn hollti), arae pwyntiau, a chyfeiriadau at bedwar nôd plentyn (nwl i ddechrau). Gellir ysgrifennu'r swyddogaeth fewnosod gyfan mewn llai na 30 llinell o god yn y rhan fwyaf o ieithoedd.

Mae'r gweithrediad hollt yn creu pedwar nod plentyn newydd, pob un yn gorchuddio un cwadrant o ffin y rhiant. Ar gyfer rhiant â ffin (x, y, lled, uchder), mae plentyn y gogledd-ddwyrain yn cael (x + lled / 2, y, lled / 2, uchder / 2), mae'r gogledd-orllewin yn cael (x, y, lled / 2, uchder / 2), ac yn y blaen. Ar ôl hollti, mae'r pwyntiau presennol yn cael eu hailddosbarthu i'r plant priodol. Camgymeriad cyffredin yw anghofio clirio arae pwyntiau'r rhiant ar ôl ailddosbarthu, sy'n arwain at ganlyniadau dyblyg yn ystod ymholiadau.

Ar gyfer defnydd cynhyrchu, mae sawl optimeiddiad yn bwysig. Mae gosod cynhwysedd y nod i 4-8 pwynt fel arfer yn perfformio'n well na chynhwysedd o 1, oherwydd ei fod yn lleihau dyfnder coed a gorbenion gwrthrychau nod. Mae ychwanegu terfyn dyfnder mwyaf (8-12 lefel fel arfer) yn atal achosion patholegol lle mae llawer o bwyntiau'n rhannu cyfesurynnau union yr un fath rhag creu coed anfeidrol ddwfn. Ac ar gyfer setiau data deinamig lle mae pwyntiau'n symud - fel tracio cerbydau - byddwch chi eisiau mecanwaith tynnu neu strategaeth i ailadeiladu'r goeden o bryd i'w gilydd, gan nad yw pedair coeden yn cydbwyso eu hunain fel coed coch-du.

Cedren mewn Llwyfannau Busnes a Dadansoddeg

Mae llwyfannau busnes modern yn delio fwyfwy â data gofodol, boed yn leoliadau cwsmeriaid, parthau dosbarthu, tiriogaethau gwerthu, neu dracio asedau. Nid storio'r data hwn yn unig yw'r her - mae'n golygu ei bod yn bosibl ymholi mewn amser real ar raddfa fawr. Pan fydd angen i fusnes sy'n gweithredu ar draws 50 o ddinasoedd ddelweddu dwysedd cwsmeriaid, gyrwyr dosbarthu llwybrau, neu ddadansoddi perfformiad gwerthiant rhanbarthol, mae'r strategaeth mynegeio gofodol sylfaenol yn pennu a yw'r dangosfwrdd yn llwytho mewn 200 milieiliad neu 20 eiliad.

Dyma un rheswm mae platfformau fel Mewayz - sy'n integreiddio 207 o fodiwlau sy'n rhychwantu CRM, anfonebu, rheoli fflyd, archebu, a dadansoddeg i mewn i un OS busnes - yn elwa o drin data gofodol effeithlon o dan y cwfl. Pan fydd angen i fodiwl rheoli fflyd arddangos 500 o gerbydau gweithredol ar fap, neu pan fydd modiwl CRM yn delweddu 138,000+ o leoliadau defnyddwyr ar gyfer cynllunio tiriogaeth, nid yw dulliau naïf yn graddio. Mae strwythurau mynegeio gofodol fel quadtrees (neu eu cronfeydd data cyfatebol, megis PostGIS R-trees a mynegeion gofodol MySQL) yn ei gwneud hi'n ymarferol cynnig y nodweddion hyn heb fod angen caledwedd gradd menter.

Ar gyfer busnesau sy'n gwerthuso llwyfannau, mae'r tecawê yn ymarferol: nid dim ond defnyddio algorithmau ffansi er ei fwyn yw offer sy'n trin data lleoliad a gofodol yn dda. Maen nhw'n gwneud y gwahaniaeth rhwng system archebu sy'n gallu dangos yn syth i'r darparwyr gwasanaeth sydd ar gael o fewn 10 cilomedr ac un sy'n cymryd 8 eiliad i lwytho'r un canlyniadau. Mae perfformiad ar y lefel hon yn trosi'n uniongyrchol i brofiad y defnyddiwr ac, yn y pen draw, refeniw.

Quadtrees vs. Strwythurau Data Gofodol Eraill

Nid Quadtrees yw'r unig opsiwn ar gyfer mynegeio gofodol, ac mae deall y dewisiadau eraill yn eich helpu i ddewis yr offeryn cywir. R-coed, a ddefnyddir yn helaeth mewn cronfeydd data fel PostGIS a modiwl R* Tree SQLite, yn trefnu data yn betryalau terfyn isaf ac yn trin ymholiadau amrediad a chwiliadau cymdogion agosaf yn effeithlon. Yn gyffredinol, maent yn perfformio'n well na phedair coeden ar gyfer storio disg oherwydd eu bod yn lleihau gweithrediadau I/O, a dyna pam y mae'r rhan fwyaf o gronfeydd data gofodol yn defnyddio amrywiadau R-tree yn fewnol yn hytrach na quadtrees.

Coed K-d gofod rhaniad gan ddefnyddio holltau echelin bob yn ail (yn gyntaf gan x, yna gan y, yna gan x eto) ac maent yn wych ar gyfer chwiliadau cymdogion agosaf mewn dimensiynau cymedrol. Maent yn tueddu i berfformio'n well na phedair coed pan fo'r dimensiwnoldeb yn isel a'r set ddata yn statig, ond mae'n anoddach eu diweddaru'n ddeinamig. Mae Geohashes yn cymryd agwedd wahanol yn gyfan gwbl, gan amgodio lledred a hydred yn llinyn sengl lle mae rhagddodiaid a rennir yn dynodi agosrwydd gofodol - gan eu gwneud yn ddelfrydol ar gyfer mynegeio cronfa ddata a caching ond yn llai hyblyg ar gyfer ymholiadau ystod mympwyol.

Mae Quadtrees yn dal eu hunain mewn senarios sy'n chwarae i'w cryfderau: mynegeio gofodol yn y cof, setiau data deinamig sy'n cael eu mewnosod a'u dileu'n aml, cymwysiadau delweddu lle mae strwythur y grid hierarchaidd yn mapio'n naturiol i chwyddo lefelau, a sefyllfaoedd lle mae symlrwydd y gweithredu yn bwysig. Ar gyfer cymhwysiad pen blaen sy'n gwneud 10,000 o bwyntiau data ar gynfas gyda phan-a-chwyddo, bydd cwadrant a weithredir mewn 100 llinell o JavaScript yn perfformio'n well nag unrhyw ddatrysiad a gefnogir gan gronfa ddata dim ond trwy ddileu cuddni rhwydwaith.

Cychwyn Arni: Y Camau Nesaf Ymarferol

Os ydych chi eisiau dyfnhau eich dealltwriaeth o bedair coed y tu hwnt i ddarllen amdanyn nhw, y dull mwyaf effeithiol yw adeiladu un yn weledol. Creu cymhwysiad cynfas syml lle mae clicio yn ychwanegu pwyntiau, a gwyliwch y goeden yn isrannu mewn amser real. Ychwanegwch betryal ymholiad amrediad y gallwch ei lusgo o gwmpas ac amlygu'r pwyntiau y mae'n dod o hyd iddynt. Mae'r rhyngweithio ymarferol hwn yn adeiladu greddf na all unrhyw faint o ddarllen ei gyfateb - fe welwch ar unwaith pam mae data clystyrog yn creu coed dyfnach a sut mae ymddygiad tocio yn ystod ymholiadau yn dileu darnau mawr o le.

Ar gyfer cymwysiadau cynhyrchu, ystyriwch y canllawiau hyn: os yw eich data yn byw mewn cronfa ddata, defnyddiwch y mynegeio gofodol y mae eich cronfa ddata yn ei ddarparu (mynegai PostGIS, MySQL Spatial, MongoDB 2dsphere) yn hytrach na gweithredu quadtrees yn y cod cymhwysiad. Os ydych chi'n gwneud delweddu ochr cleient neu brosesu cof, mae llyfrgelloedd fel d3-quadtree ar gyfer JavaScript neu pyquadtree ar gyfer Python yn rhoi gweithrediadau prawf brwydr i chi. Ac os ydych chi'n adeiladu platfform sy'n trin unrhyw fath o ddata lleoliad - o gyfeiriadau cwsmeriaid i lwybr dosbarthu i reoli tiriogaeth - buddsoddwch yr amser i ddeall mynegeio gofodol, oherwydd bydd yn siapio'r hyn y gall eich cais ei wneud ar raddfa fawr yn sylfaenol.

Mae Quadtrees yn cynrychioli egwyddor ehangach mewn cyfrifiadureg: bod y strwythur a ddewiswch ar gyfer eich data yn pennu'r cwestiynau y gallwch eu hateb yn effeithlon. Gall rhestr wastad o gyfesurynnau ateb "rhowch yr holl bwyntiau i mi," ond gall quadtree ateb "rhowch yr holl bwyntiau i mi yn agos i yma" - a gall ei wneud yn ddigon cyflym i deimlo'n syth. Mewn byd lle mae gan 73% o ddata busnes elfen ofodol yn ôl amcangyfrifon y diwydiant, nid dim ond academaidd yw'r gallu hwnnw. Mae'n fantais gystadleuol.

Cwestiynau Cyffredin

Beth yw quadtree a sut mae'n gweithio?

Mae cwadrant yn strwythur data seiliedig ar goed sy'n rhannu gofod dau ddimensiwn yn rheolaidd yn bedwar cwadrant cyfartal. Gall pob nod ddal nifer cyfyngedig o bwyntiau data cyn rhannu'n bedwar nod plentyn. Mae'r rhaniad hierarchaidd hwn yn gwneud ymholiadau gofodol - fel dod o hyd i bob pwynt o fewn ardal benodol - yn hynod o gyflym, gan leihau amser chwilio o linellol i logarithmig yn y rhan fwyaf o senarios ymarferol.

Ble mae pedair coeden yn cael eu defnyddio'n gyffredin mewn rhaglenni byd go iawn?

Mae Quadtrees yn pweru ystod eang o systemau gan gynnwys mapiau digidol gyda swyddogaeth pinsio-i-chwyddo, dangosfyrddau olrhain fflyd amser real, peiriannau canfod gwrthdrawiadau gêm fideo, a systemau gwybodaeth ddaearyddol sy'n prosesu miliynau o ymholiadau gofodol yr eiliad. Gall unrhyw raglen sydd angen chwilio, mewnosod neu reoli gwrthrychau a ddosberthir ar draws gofod dau-ddimensiwn yn effeithlon elwa o fynegeio quadtree.

Sut mae pedair coeden yn cymharu â strwythurau data gofodol eraill?

Yn wahanol i gridiau gwastad, mae quadtrees yn addasu eu cydraniad i ddwysedd data - mae ardaloedd prin yn aros yn fras tra bod rhanbarthau gorlawn yn isrannu ymhellach. O'u cymharu â choed k-d, mae pedair coeden yn symlach i'w gweithredu ac yn fwy addas ar gyfer data 2D a ddosberthir yn unffurf. Mae coed-R yn trin rhanbarthau sy'n gorgyffwrdd yn fwy gosgeiddig, ond mae pedwar coeden yn ennill ar gyflymder mewnosod ac mae'n haws eu cyfochri ar gyfer llwythi gwaith amser real.

A all quadtrees helpu i optimeiddio perfformiad mewn meddalwedd busnes?

Yn hollol. Mae unrhyw offeryn busnes sy'n trin data lleoliad, dadansoddeg ofodol, neu ddangosfyrddau rhyngweithiol yn elwa o optimeiddio quadtree. Mae llwyfannau fel Mewayz, OS busnes 207-modiwl sy'n dechrau ar $19/mo, yn trosoledd strwythurau data effeithlon y tu ôl i'r llenni i ddarparu profiadau cyflym, ymatebol - o fapiau lleolwr siopau i ddadansoddeg amser real ar draws miloedd o bwyntiau data.