Інтэрактыўнае ўвядзенне ў квадратныя дрэвы

Чаму Quadtrees важныя больш, чым вы думаеце

Кожны раз, калі вы павялічваеце пальцамі на лічбавай карце, запытваеце бліжэйшыя рэстараны або назіраеце, як трэкер аўтапарка ў рэжыме рэальнага часу абнаўляе дзясяткі значкоў транспартных сродкаў, і ваш браўзер не спыняецца, вялікая верагоднасць таго, што квадратрэе выконвае цяжкую працу за кулісамі. Quadtrees - гэта адна з тых элегантных структур даных, пра якія большасць людзей ніколі не чула, але яны спакойна працуюць у некаторых з найбольш важных для прадукцыйнасці сістэм сучаснага праграмнага забеспячэння - ад выяўлення сутыкненняў відэагульняў да геаінфармацыйных сістэм, якія апрацоўваюць мільёны прасторавых запытаў у секунду. Разуменне таго, як яны працуюць, не толькі робіць вас лепшым распрацоўшчыкам; гэта карэнным чынам змяняе ваша стаўленне да арганізацыі і пошуку прасторавых даных. Незалежна ад таго, ствараеце вы лагістычную платформу дастаўкі, прыборную панэль аналітыкі на аснове месцазнаходжання або проста спрабуеце візуалізаваць 50 000 кропак даных на палатне без збояў у браўзеры, quadtrees прапануюць рашэнне, якое з'яўляецца адначасова інтуітыўным і надзвычай эфектыўным.

Што такое квадратрэе?

Квадратнае дрэва - гэта дрэвавая структура дадзеных, у якой кожны ўнутраны вузел мае роўна чатыры даччыных вузла, кожны з якіх прадстаўляе адзін квадрант двухмернай прасторы. Уявіце, што вы ўзялі квадратную вобласць і падзялілі яе на чатыры роўныя квадраты — паўночны захад, паўночны ўсход, паўднёвы захад і паўднёвы ўсход. Кожны з гэтых квадратаў можа быць падзелены яшчэ на чатыры квадраты, і гэтак далей, рэкурсіўна, пакуль вы не дасягнеце нейкай умовы прыпынку. Умовай спынення звычайна з'яўляецца альбо максімальная глыбіня, альбо парогавае значэнне колькасці кропак даных, якія можа ўтрымліваць адзін вузел, перш чым яму трэба будзе падзяліцца.

Прыгажосць гэтага падыходу заключаецца ў яго адаптыўнай прыродзе. Вобласці з вялікай колькасцю кропак даных дзеляцца на ўсё больш дробныя ячэйкі, у той час як рэдкія вобласці застаюцца вялікімі непадзеленымі рэгіёнамі. Квадратнае дрэва, якое захоўвае размяшчэнне 10 000 кавярняў па ўсёй краіне, створыць глыбокія, падрабязныя падраздзяленні на Манхэтэне, дзе можа быць 300 крам у межах некалькіх квадратных кіламетраў, захоўваючы пры гэтым велізарныя ўчасткі сельскай мясцовасці Ваёмінга як адзіны непадзелены вузел, які змяшчае нуль або адну кропку. Гэта адаптыўная раздзяляльнасць - гэта тое, што робіць квадратныя дрэвы такімі магутнымі ў параўнанні з плоскай сеткай, якая марнавала б велізарную колькасць памяці на пустыя ячэйкі.

Канцэпцыя была ўпершыню апісана Рафаэлем Фінкелем і Дж. Л. Бэнтлі ў 1974 годзе, і з тых часоў яна падзялілася на некалькі варыянтаў: кропкавыя квадратныя дрэвы захоўваюць асобныя пары каардынат, рэгіённыя квадратныя дрэвы прадстаўляюць прасторавыя вобласці (карысныя для сціску выявы), а краёвыя квадратныя дрэвы апрацоўваюць лініі і крывыя. Кожны варыянт аптымізуецца для розных выпадкаў выкарыстання, але асноўны прынцып рэкурсіўнага падраздзялення застаецца аднолькавым ва ўсіх.

Як працуюць устаўка і запыт

Каб уставіць кропку ў квадрант, вы пачынаеце з каранёвага вузла і вызначаеце, у які з чатырох квадрантаў кропка трапляе. Затым вы вяртаецеся да даччынага вузла гэтага квадранта і паўтараеце працэс. Калі вы дасягаеце ліставога вузла, які не перавышае сваю ёмістасць (звычайна ўсталёўваецца ў 1 або 4 пункты), вы проста захоўваеце пункт там. Калі ліст ужо загружаны, ён раздзяляецца на чатырох даччыных элементаў, пераразмяркоўвае існуючыя кропкі паміж імі, а затым устаўляе новую кропку ў адпаведны даччыны элемент. Гэты працэс звычайна завяршаецца за час O(log n) для збалансаванага размеркавання, хоць горшыя сцэнарыі з моцна кластэрызаванымі данымі могуць пагоршыць прадукцыйнасць.

Запыт дыяпазону — знаходжанне ўсіх кропак у межах дадзенай прамавугольнай вобласці — гэта тое, дзе квадратныя дрэвы сапраўды ззяюць. Замест праверкі кожнага асобнага пункта ў вашым наборы даных (аперацыя O(n)), вы пачынаеце з кораня і задаеце простае пытанне ў кожным вузле: ці перасякаецца мяжа гэтага вузла з маім прамавугольнікам пошуку? У адваротным выпадку вы абразаеце ўсё паддрэва - патэнцыйна выключаючы тысячы пунктаў з разгляду ў адным параўнанні. Калі ёсць скрыжаванне, вы вяртаецеся да адпаведных дзяцей. Кропкі, знойдзеныя ў ліставых вузлах, якія трапляюць у прамавугольнік пошуку, дадаюцца да набору вынікаў.

Разгледзім практычны прыклад: у вас ёсць набор даных са 100 000 кліентаў, і вам трэба знайсці ўсіх у радыусе 5 кіламетраў ад адкрыцця новай крамы. Падыход грубай сілы патрабуе 100 000 разлікаў адлегласці. Добра пабудаванае квадратнае дрэва можа скараціць гэта ўсяго да 200-500 праверак шляхам хуткага выдалення цэлых геаграфічных рэгіёнаў, якія відавочна не перасякаюцца з вашай вобласцю пошуку. Гэта павышэнне прадукцыйнасці ў 200 разоў і больш - розніца паміж тым, што запыт займае 800 мілісекунд і 4 мілісекунды.

Рэальныя праграмы, якія працуюць на Quadtrees

Сфера прымянення квадратных дрэў выходзіць далёка за межы акадэмічнай інфарматыкі. Яны з'яўляюцца асновай сістэм, якімі мільярды людзей карыстаюцца штодня, часта самі таго не падазраючы.

• Карты і навігацыя: такія сэрвісы, як Google Maps і Mapbox, выкарыстоўваюць сістэмы плітак, падобныя на квадратнае дрэва, для абслугоўвання малюнкаў карты. Кожны ўзровень маштабавання разбівае пліткі на чатыры даччыныя элементы, таму каардынаты плітак карты прытрымліваюцца шаблону z/x/y, які адлюстроўвае адрасаванне квадратнага дрэва. Калі вы павялічваеце маштаб гарадскога квартала, загружаюцца толькі адпаведныя пліткі высокай раздзяляльнасці — астатні свет застаецца ў грубай разрознасці.
• Выяўленне сутыкненняў у гульнях: гульнявыя механізмы выкарыстоўваюць квадратныя дрэвы (і іх 3D аналаг, октравы), каб эфектыўна выяўляць сутыкненні аб'ектаў. Замест таго, каб правяраць кожную пару аб'ектаў - кашмар O(n²) з 1000 аб'ектамі на экране - механізм правярае толькі аб'екты, якія падзяляюць адну і тую ж ячэйку квадратра, зводзячы праверкі да кіраванай колькасці.
• Сцісканне выявы: квадратрэі рэгіёнаў могуць сціскаць выявы шляхам аб'яднання суседніх пікселяў, якія маюць падобныя колеры, у большыя блокі. Гэта з'яўляецца асновай пэўных алгарытмаў сціску, якія дасягаюць каэфіцыента сціску 10:1, захоўваючы візуальную дакладнасць у месцах з нізкай дэталізацыяй.
• Кіраванне аўтапаркам і лагістыка: Кампаніі-дастаўшчыкі выкарыстоўваюць прасторавую індэксацыю, каб супастаўляць кіроўцаў з бліжэйшымі заказамі ў рэжыме рэальнага часу. Quadtree дазваляе дыспетчарскай сістэме імгненна адказаць на пытанне "якія 5 кіроўцаў знаходзяцца бліжэй за ўсё да гэтага месца прыняцця?" у парку з тысяч аўтамабіляў, якія кожныя некалькі секунд абнаўляюць свае пазіцыі GPS.
• Геапрасторавая аналітыка: платформы, якія аб'ядноўваюць бізнес-даныя на аснове месцазнаходжання — карты шчыльнасці кліентаў, аптымізацыя гандлёвых тэрыторый, аналіз размяшчэння крам — абапіраюцца на структуры прасторавых даных, каб зрабіць гэтыя запыты інтэрактыўнымі, а не пакетнай апрацоўкай.

Асноўнае разуменне квадрадрэваў заключаецца ў тым, што большасць прасторавых запытаў не патрабуе праверкі большасці даных. Арганізаваўшы прастору іерархічна, вы пераўтвараеце пошук грубай сілы ў мэтанакіраваны абход — пераўтвараючы секунды ў мілісекунды і робячы магчымай інтэрактыўнасць у рэальным часе нават з вялікімі наборамі даных.

Стварэнне Quadtree з нуля

Рэалізацыя асноўнага квадродрэва надзіва даступная нават для распрацоўшчыкаў сярэдняга ўзроўню. Для асноўнай структуры патрабуецца ўсяго некалькі кампанентаў: межа (прамавугольная вобласць, якую ахоплівае вузел), ёмістасць (максімальная колькасць балаў перад падзелам), масіў кропак і спасылкі на чатыры даччыныя вузлы (першапачаткова нулявыя). У большасці моў уся функцыя ўстаўкі можа быць напісана менш чым у 30 радках кода.

Аперацыя падзелу стварае чатыры новыя даччыныя вузлы, кожны з якіх ахоплівае адзін квадрант мяжы бацькоўскага вузла. Для бацькі з мяжой (x, y, шырыня, вышыня), паўночна-ўсходні даччыны элемент атрымлівае (x + шырыня/2, y, шырыня/2, вышыня/2), паўночны захад атрымлівае (x, y, шырыня/2, вышыня/2) і г.д. Пасля падзелу існуючыя балы пераразмяркоўваюцца паміж адпаведнымі даччынымі элементамі. Распаўсюджанай памылкай з'яўляецца забыванне ачысціць бацькоўскі масіў балаў пасля пераразмеркавання, што прыводзіць да дублявання вынікаў падчас запытаў.

Для вытворчага выкарыстання важныя некалькі аптымізацый. Усталяванне ёмістасці вузла ў 4-8 пунктаў звычайна пераўзыходзіць ёмістасць у 1, таму што гэта памяншае глыбіню дрэва і накладныя выдаткі аб'ектаў вузла. Даданне абмежавання максімальнай глыбіні (звычайна 8-12 узроўняў) прадухіляе стварэнне бясконца глыбокіх дрэў у паталагічных выпадках, калі шмат кропак падзяляе аднолькавыя каардынаты. А для дынамічных набораў даных, дзе кропкі рухаюцца — напрыклад, адсочванне транспартных сродкаў — вам спатрэбіцца механізм выдалення або стратэгія перыядычнага аднаўлення дрэва, бо квадратрэі не самабалансуюцца, як гэта робяць чырвона-чорныя дрэвы.

Квадратары ў бізнес-платформах і аналітыцы

Сучасныя бізнес-платформы ўсё часцей працуюць з прасторавымі данымі, няхай гэта будзе месцазнаходжанне кліентаў, зоны дастаўкі, тэрыторыі продажаў або адсочванне актываў. Праблема заключаецца не толькі ў захаванні гэтых даных, але і ў тым, каб іх можна было запытваць у рэальным маштабе часу. Калі кампаніі, якая працуе ў 50 гарадах, неабходна візуалізаваць шчыльнасць кліентаў, маршруты дастаўкі або прааналізаваць рэгіянальныя паказчыкі продажаў, асноўная стратэгія прасторавага індэксавання вызначае, загружаецца прыборная панэль за 200 мілісекунд або за 20 секунд.

Гэта адна з прычын, па якой такія платформы, як Mewayz — якая аб'ядноўвае 207 модуляў, якія ахопліваюць CRM, выстаўленне рахункаў, кіраванне аўтапаркам, браніраванне і аналітыку ў адзіную бізнес-АС — атрымліваюць выгаду ад эфектыўнай апрацоўкі прасторавых даных пад капотам. Калі модулю кіравання аўтапаркам неабходна адлюстраваць 500 актыўных транспартных сродкаў на карце або калі модуль CRM візуалізуе больш за 138 000 месцазнаходжанняў карыстальнікаў для планавання тэрыторыі, наіўныя падыходы проста не падыходзяць. Структуры прасторавага індэксавання, такія як квадратры (або іх эквіваленты баз дадзеных, такія як PostGIS R-дрэвы і прасторавыя індэксы MySQL), робяць магчымым прапанаваць гэтыя функцыі без неабходнасці апаратнага забеспячэння карпаратыўнага ўзроўню.

Для прадпрыемстваў, якія ацэньваюць платформы, вынік практычны: інструменты, якія добра апрацоўваюць геалакацыю і прасторавыя даныя, не проста выкарыстоўваюць мудрагелістыя алгарытмы дзеля гэтага. Яны робяць розніцу паміж сістэмай браніравання, якая можа імгненна паказваць даступных пастаўшчыкоў паслуг у радыусе 10 кіламетраў, і сістэмай, якой патрабуецца 8 секунд, каб загрузіць тыя ж вынікі. Прадукцыйнасць на гэтым узроўні непасрэдна ператвараецца ў карыстацкі досвед і, у канчатковым выніку, даход.

Квадратары ў параўнанні з іншымі структурамі прасторавых даных

Квадратары - не адзіны варыянт прасторавай індэксацыі, і разуменне альтэрнатыў дапаможа вам выбраць правільны інструмент. R-дрэвы, якія шырока выкарыстоўваюцца ў такіх базах дадзеных, як PostGIS і модуль R*Tree ад SQLite, арганізуюць даныя ў мінімальныя абмежавальныя прастакутнікі і эфектыўна апрацоўваюць запыты дыяпазону і пошук бліжэйшых суседзяў. Як правіла, яны пераўзыходзяць квадратныя дрэвы для дыскавага сховішча, таму што мінімізуюць аперацыі ўводу/вываду, таму большасць прасторавых баз даных унутрана выкарыстоўваюць варыянты R-дрэва, а не квадратныя дрэвы.

Дрэвы K-d разбіваюць прастору з дапамогай чаргавання падзелаў, выраўнаваных па восях (спачатку па x, потым па y, потым зноў па x) і выдатна падыходзяць для пошуку бліжэйшых суседзяў ва ўмераных памерах. Яны, як правіла, пераўзыходзяць квадратныя дрэвы, калі памернасць нізкая і набор даных статычны, але іх цяжэй абнаўляць дынамічна. Геахэшы выкарыстоўваюць цалкам іншы падыход, кадуючы шырыню і даўгату ў адзін радок, дзе агульныя прэфіксы паказваюць прасторавую блізкасць — што робіць іх ідэальнымі для індэксацыі базы дадзеных і кэшавання, але менш гнуткімі для запытаў адвольнага дыяпазону.

Квадратрэвы захоўваюць свае перавагі ў сцэнарыях, якія адыгрываюць іх моцныя бакі: прасторавая індэксацыя ў памяці, дынамічныя наборы даных з частымі ўстаўкамі і выдаленнямі, прыкладанні для візуалізацыі, дзе іерархічная структура сеткі натуральным чынам адлюстроўваецца на ўзроўнях маштабавання, і сітуацыі, калі прастата рэалізацыі мае значэнне. Для інтэрфейснага прыкладання, якое адлюстроўвае 10 000 кропак даных на палатне з панарамаваннем і маштабаваннем, квадратнае дрэва, рэалізаванае ў 100 радках JavaScript, пераўзыходзіць любое рашэнне, якое падтрымліваецца базай дадзеных, проста выключаючы затрымку сеткі.

Пачатак працы: наступныя практычныя крокі

Калі вы жадаеце паглыбіць сваё разуменне квадратных дрэў, акрамя чытання пра іх, найбольш эфектыўным падыходам з'яўляецца пабудова аднаго візуальнага дрэва. Стварыце простае палатно-прыкладанне, у якім пстрычка дадае балы, і назірайце, як дрэва разбіваецца ў рэжыме рэальнага часу. Дадайце прастакутнік дыяпазону запытаў, які можна перацягваць і выдзяляць знойдзеныя кропкі. Гэта практычнае ўзаемадзеянне стварае інтуіцыю, з якой не можа параўнацца ніякая колькасць чытанняў — вы адразу зразумееце, чаму кластарныя даныя ствараюць больш глыбокія дрэвы і як паводзіны абразання падчас запытаў ліквідуе вялікія ўчасткі прасторы.

Для прадукцыйных прыкладанняў прытрымлівайцеся наступных рэкамендацый: калі вашы даныя захоўваюцца ў базе даных, выкарыстоўвайце прасторавую індэксацыю, якую забяспечвае ваша база дадзеных (індэксы PostGIS, MySQL Spatial, MongoDB 2dsphere), а не ўкараненне квадрадрэваў у код прыкладання. Калі вы робіце кліенцкую візуалізацыю або апрацоўку ў памяці, такія бібліятэкі, як d3-quadtree для JavaScript або pyquadtree для Python, даюць вам правераныя ў баях рэалізацыі. І калі вы ствараеце платформу, якая апрацоўвае любыя даныя аб месцазнаходжанні - ад адрасоў кліентаў да маршруту дастаўкі і кіравання тэрыторыяй - укладзіце час, каб зразумець прасторавую індэксацыю, таму што гэта фундаментальна сфармулюе тое, што ваша прыкладанне можа зрабіць у маштабе.

Квадратрэвы прадстаўляюць больш шырокі прынцып інфарматыкі: структура, якую вы выбіраеце для вашых даных, вызначае пытанні, на якія вы можаце эфектыўна адказаць. Плоскі спіс каардынатаў можа адказаць «дайце мне ўсе кропкі», але квадратнае дрэва можа адказаць «дайце мне ўсе кропкі побач тут» — і яно можа зрабіць гэта дастаткова хутка, каб адчуць сябе імгненна. У свеце, дзе, паводле галіновых ацэнак, 73% бізнес-дадзеных маюць прасторавы кампанент, гэта магчымасць не толькі акадэмічнай. Гэта канкурэнтная перавага.

Часта задаюць пытанні

Што такое квадратнае дрэва і як яно працуе?

Квадрарэва - гэта дрэвавая структура дадзеных, якая рэкурсіўна дзеліць двухмерную прастору на чатыры роўныя квадранты. Кожны вузел можа змяшчаць абмежаваную колькасць кропак даных перад падзелам на чатыры даччыныя вузлы. Такое іерархічнае раздзяленне робіць прасторавыя запыты — напрыклад, пошук усіх кропак у дадзенай вобласці — надзвычай хуткімі, скарачаючы час пошуку з лінейнага на лагарыфмічны ў большасці практычных сцэнарыяў.

Дзе квадратры звычайна выкарыстоўваюцца ў рэальных праграмах?

Quadtrees сілкуюць шырокі спектр сістэм, уключаючы лічбавыя карты з функцыяй павелічэння пальцам, панэлі кіравання аўтапаркам у рэжыме рэальнага часу, механізмы выяўлення сутыкненняў у відэагульнях і сістэмы геаграфічнай інфармацыі, якія апрацоўваюць мільёны прасторавых запытаў у секунду. Любое прыкладанне, якое мае патрэбу ў эфектыўным пошуку, устаўцы або кіраванні аб'ектамі, размеркаванымі ў двухмернай прасторы, можа атрымаць выгаду з індэксацыі чатырохмернага дрэва.

Як квадратры ў параўнанні з іншымі структурамі прасторавых даных?

У адрозненне ад плоскіх сетак, квадратныя дрэвы прыстасоўваюць сваю раздзяляльнасць да шчыльнасці даных — разрэджаныя вобласці застаюцца грубымі, у той час як перапоўненыя вобласці разбіваюцца далей. У параўнанні з k-d дрэвамі, квадратныя дрэвы прасцей у рэалізацыі і лепш падыходзяць для раўнамерна размеркаваных 2D даных. R-дрэвы больш вытанчана апрацоўваюць вобласці, якія перакрываюцца, але квадратрэі выйграюць у хуткасці ўстаўкі і іх лягчэй паралелізаваць для працоўных нагрузак у рэальным часе.

Ці могуць квадратныя дрэвы дапамагчы аптымізаваць прадукцыйнасць праграмнага забеспячэння для бізнесу?

Абавязкова. Любы бізнес-інструмент, які апрацоўвае даныя аб месцазнаходжанні, прасторавую аналітыку або інтэрактыўныя панэлі, атрымлівае выгаду ад аптымізацыі квадратра. Такія платформы, як Mewayz, 207-модульная бізнес-АС па кошце ад 19 долараў ЗША ў месяц, выкарыстоўваюць эфектыўныя структуры даных за кулісамі для забеспячэння хуткага і хуткага рэагавання — ад карт лакатара крам да аналітыкі ў рэальным часе па тысячах кропак даных.