În calcul și informatică , o curbă Morton , secvența Z , ordinul Z , curba Lebesgue , ordinea Morton sau codul Morton este o funcție care mapează date multidimensionale cu date unidimensionale, păstrând în același timp localitatea punctelor de date. Funcția a fost introdusă în 1966 de Guy MacDonald Morton [1] . Valoarea Z a unui punct din spațiul multidimensional este ușor de calculat prin alternarea cifrelor binare ale valorilor coordonatelor sale. Atunci când datele sunt stocate în această ordine, pot fi folosite orice structuri unidimensionale, cum ar fi arbori de căutare binari , arbori B , liste de omitere sau tabele hash (cu biți mici eliminați). Ordinea astfel creată poate fi descrisă în mod echivalent ca ordinea care poate fi obținută printr-o parcurgere în adâncime a unui quadtree .
Figura de mai jos arată valorile Z pentru cazul 2D cu coordonate întregi 0 ⩽ x ⩽ 7, 0 ⩽ y ⩽ 7 (sunt afișate atât valorile zecimale, cât și cele binare). Alternarea cifrelor binare ale coordonatelor produce valori binare z , așa cum se arată în figură. Conectând valorile z în ordinea lor numerică obișnuită, obținem o curbă Z recursivă. Valorile Z bidimensionale sunt numite și chei de cadran.
Valorile Z de-a lungul axei x sunt descrise ca numere binare din secvența Moser-de Bruijn , având biți non-zero numai în pozițiile lor pare:
x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}Suma și diferența a două valori în raport cu coordonatele x se calculează folosind operații pe biți :
x[i+j] = ((x[i] | 0b10101010) + x[j]) și 0b01010101 x[ij] = ((x[i] și 0b01010101) - x[j]) și 0b01010101 dacă i >= jOrdinea Z poate fi folosită pentru a construi eficient un quadtree pentru un set de puncte [2] . Ideea de bază este de a sorta setul de puncte de intrare în funcție de ordinea Z. Odată sortate, punctele pot fi stocate ca un arbore de căutare binar și utilizate direct, care se numește un arbore cu patru linii liniar [3] , sau pot fi folosite pentru a construi un arbore patru bazat pe pointeri.
Punctele de intrare sunt de obicei scalate de-a lungul fiecărei dimensiuni pentru a produce numere întregi pozitive, fie ca numere cu punct fix în intervalul [0, 1], fie în intervalul corespunzător cuvântului mașină. Ambele reprezentări sunt echivalente și vă permit să găsiți cel mai semnificativ bit diferit de zero în timp constant. Orice pătrat din arborele patru are o lungime a laturii care este o putere de doi, iar coordonatele colțului sunt multipli ai lungimii laturii. Dacă sunt date două puncte, pătratul derivat pentru acele două puncte este cel mai mic pătrat care acoperă ambele puncte. Alternarea biților din coordonatele x și y ale fiecărui punct se numește amestecare x și y și poate fi extinsă la dimensiuni mai mari [2] .
Punctele pot fi sortate în funcție de amestecarea lor fără rotație explicită a biților. Pentru a face acest lucru, pentru fiecare măsurătoare, este verificat bitul XOR de ordin înalt al coordonatelor celor două puncte din măsurarea respectivă. Dimensiunea pentru care bitul cel mai semnificativ este mai mare este apoi utilizată pentru a compara cele două puncte pentru a determina ordinea lor amestecată.
Operația XOR elimină aceiași biți înalți care sunt aceiași pentru ambele coordonate. Găsirea coordonatei cu bitul cel mai semnificativ determină primul bit care diferă în ordinea amestecării, iar această coordonată poate fi folosită pentru a compara două puncte [4] . Acest lucru este afișat în următorul cod Python:
def cmp_zorder ( a , b ): j = 0 k = 0 x = 0 for k in range ( dim ): y = a [ k ] ^ b [ k ] if less_msb ( x , y ): j = k x = y returnează a [ j ] - b [ j ]O modalitate de a determina dacă bitul cel mai semnificativ este mai mic este de a compara logaritmul binar rotunjit în jos al fiecărui punct. Rezultă că următoarea operație este echivalentă și necesită doar operația XOR [4] :
def less_msb ( x , y ): return x < y și x < ( x ^ y )Este posibil să comparați numerele în virgulă mobilă folosind aceeași tehnică. Funcția less_msb este modificată pentru a compara mai întâi exponenții. Doar dacă se potrivesc, funcția standard less_msb este executată pe mantise [5] .
Odată ce punctele sunt sortate, două proprietăți facilitează construirea unui quadtree. Prima proprietate este că punctele conținute într-un pătrat quadtree formează un interval contiguu în sortare. A doua proprietate este că, dacă mai mult de un copil pătrat conține un punct de intrare, pătratul este pătratul derivat pentru cele două puncte adiacente din sortare.
Pentru fiecare pereche de puncte adiacentă, se calculează pătratul derivat și lungimea laturii sale. Pentru fiecare pătrat derivat, intervalul care îl conține este mărginit de primul pătrat cel mai mare din dreapta și din stânga în sortarea [2] . Fiecare astfel de interval corespunde unui pătrat din arborele patru. Rezultatul este un quadtree comprimat în care sunt prezente doar noduri care conțin puncte de intrare sau doi sau mai mulți descendenți. Un quadtree necomprimat poate fi construit prin restaurarea nodurilor lipsă, dacă este necesar.
În loc să construiți un quadtree bazat pe puncte, punctele pot fi procesate în ordine sortată folosind structuri de date, cum ar fi un arbore binar de căutare. Acest lucru face posibilă adăugarea și eliminarea punctelor în timp O(log n). Doi quadtrees pot fi îmbinați împreună prin unirea a două seturi de puncte sortate și eliminarea duplicatelor. Poziția unui punct poate fi determinată analizând punctele care preced și urmăresc punctul din interogare în ordinea de sortare. Dacă arborele patru este comprimat, nodul găsit anterior poate fi o frunză arbitrară în nodul de interes comprimat. În acest caz, este necesar să găsiți nodul punct comun anterior din interogare și foaia găsită [6] .
O căutare eficientă a intervalului necesită un algoritm pentru a calcula următoarea valoare Z, care trebuie să se afle în intervalul de căutare multidimensională:
În acest exemplu, intervalul de căutare ( x = 2, …, 3, y = 2, …, 6) este evidențiat cu un dreptunghi punctat. Cea mai mare valoare Z (MAX) din acest interval este 45. În acest exemplu, valoarea F = 19 apare atunci când privim datele în ordine crescătoare a valorii Z, așa că trebuie să căutăm între F și MAX (zonă umbrită) . Pentru a accelera căutarea, este de dorit să se calculeze următoarea valoare Z care aparține zonei de căutare, numită BIGMIN (în exemplul nostru, 36), și apoi să se caute numai în intervalul dintre BIGMIN și MAX (indicat cu aldine), astfel eliminând cea mai mare parte a zonei umbrite. Căutarea în jos este similară, aici LITMAX este cea mai mare valoare Z din interogare pe un interval mai mic decât F. Problema de căutare BIGMIN a fost formulată mai întâi și soluția problemei a fost prezentată în lucrarea lui Tropf și Herzog [7] . Această soluție este utilizată în arbori UB ("GetNextZ-address"). Deoarece abordarea nu depinde de structura de date unidimensională aleasă, există libertatea de a o alege, astfel încât metode bine-cunoscute, cum ar fi arbori echilibrați, pot fi folosite pentru a lucra cu date mutabile (spre deosebire de, de exemplu, o arbori R). , unde sunt necesare convenții speciale ). De asemenea, această independență facilitează utilizarea metodei în bazele de date existente.
Atunci când este utilizată ierarhic (conform structurii datelor la îndemână), metoda oferă o metodă foarte eficientă de căutare a intervalului în ambele direcții (descrescător sau ascendent), ceea ce este important atât în aplicații comerciale, cât și industriale, de exemplu, sub forma unei proceduri. pe baza căruia se utilizează pentru căutarea celui mai apropiat vecin. Ordinea Z este una dintre puținele metode de accesare a datelor multidimensionale care și-a găsit drumul în bazele de date comerciale ( Oracle Database 1995 ( Gaede, Guenther 1998 ), Transbase 2000 ( Ramsak, Markl, Fenk, Zirkel, Elhardt, Bayer 2000). ). ).
În 1966, G. M. Morton a propus o ordine Z pentru ordonarea fișierelor într-o bază de date geografică statică bidimensională. Unitățile de date de suprafață sunt conținute într-una dintre mai multe casete pătrate, reprezentate de dimensiunea casetei și valoarea Z din colțul din dreapta jos. Cu un grad ridicat de probabilitate, trecerea la un cadru adiacent se realizează prin una sau mai multe căutări relativ mici.
Ca alternativă, se sugerează să se folosească curba Hilbert , deoarece are un comportament mai bun de păstrare a ordinii, dar calculele în acest caz vor fi semnificativ mai complexe, rezultând în utilizarea intensă a procesorului. Codurile sursă BIGMIN atât pentru curba de ordin Z, cât și pentru curba Hilbert sunt descrise în brevetul lui H. Tropf. [opt]
Pentru o privire de ansamblu asupra procesării datelor multivariate, inclusiv căutarea celui mai apropiat vecin, vezi Hanan Samet [9] .
Algoritmul lui Strassen pentru multiplicarea matricelor se bazează pe împărțirea matricelor în patru blocuri și apoi împărțirea recursivă a fiecăruia dintre aceste blocuri în patru blocuri mai mici până când blocul devine un element de identitate (sau, mai practic, până când matricele rezultate sunt atât de mici încât este banal că algoritmul funcționează mai repede pe ele). Organizarea elementelor unei matrice în ordinea Z îmbunătățește localitatea și are avantajul suplimentar (comparativ cu ordonarea pe rânduri sau coloane) că subrutina de înmulțire a două blocuri nu are nevoie să cunoască dimensiunea completă a matricei, este suficient să știm dimensiunea blocului și poziția acestuia în memorie. Un algoritm Strassen eficient de ordin Z este dat într-o lucrare din 2002 de Valsalam și Skjellum [10] .
Buluk și colab. au propus o structură de reprezentare a matricei rară pentru paralelizarea înmulțirii vector-matrice. În această reprezentare, elementele non-nule sunt aranjate în ordinea Z [11] .
Unele GPU -uri stochează texturi în ordinea Z pentru a crește localitatea de referință spațială rasterizării texturii . Acest lucru permite liniilor cache să reprezinte plăci pătrate, crescând probabilitatea ca interogările apropiate să ajungă în cache. Acest lucru este semnificativ deoarece randarea în spațiul 3D implică transformări arbitrare (rotația, scalarea, perspectiva și curbura suprafețelor). Pot fi utilizate și alte formate de mozaic.