În părțile anterioare (, ) am discutat despre globale ca fiind arbori, iar în aceasta vom analiza globale ca măsuri sparse.
— este un tip de masă în care majoritatea valorilor iau aceeași valoare.
În practică, întâlnim adesea măsuri sparse atât de mari încât nu are sens să ocupăm memoria cu aceleași elemente. De aceea, este logic să implementăm măsurile sparse astfel încât memoria să nu fie consumată pentru stocarea valorilor identice.
În unele limbaje de programare, măsurile sparse sunt incluse direct în limbaj, , . În alte limbaje de programare, există biblioteci speciale care facilitează implementarea lor. Pentru C++ — și altele.
Globale — candidați buni pentru implementarea măsurilor sparse, deoarece:
- Stochează valorile doar pentru nodurile specifice și nu stochează valorile nedefinite;
- Interfața de acces la valoarea unui nod este extrem de similară cu modul în care, în multe limbaje de programare, se implementează accesul la un element dintr-o masă multidimensională.
Set ^a(1, 2, 3)=5 Scrie ^a(1, 2, 3) - Globalul este o structură destul de de bază pentru stocarea datelor, având astfel caracteristici de viteză remarcabile (de la sute de mii până la zeci de milioane de tranzacții pe secundă, în funcție de hardware, vezi. )
Deoarece globalul este o structură persistentă, are sens să realizăm măsuri sparse pe acestea atunci când știm din timp că volumul de memorie RAM va fi insuficient.
Una dintre proprietățile implementărilor măsurilor sparse este returnarea unei valori implicite, dacă se face referire la o celulă nedefinită.
Acest lucru poate fi realizat folosind funcția în COS. În acest exemplu este prezentată o masă tridimensională.
SET a = $GET(^a(x,y,z), defValue)În ce tipuri de sarcini sunt necesare măsurile sparse și cum pot ajuta globale?
Matricea de adiacență (conexitate)
sunt utilizate pentru reprezentarea graficelor:
Este evident că cu cât graficul este mai mare, cu atât mai multe zerouri vor apărea în matrice. Dacă, de exemplu, luăm un grafic al unei rețele sociale și îl reprezentăm sub formă de matrice similară, acesta va fi aproape complet format din zerouri, adică va fi o măsură rară.
Set ^m(id1, id2) = 1
Set ^m(id1, id3) = 1
Set ^m(id1, id4) = 1
Set ^m(id1) = 3
Set ^m(id2, id4) = 1
Set ^m(id2, id5) = 1
Set ^m(id2) = 2
....
În acest exemplu, salvăm în globală ^m matricea de conectivitate, precum și numărul de legături pentru fiecare nod (cine este prieten cu cine și numărul de prieteni).
Dacă numărul de elemente din graf nu depășește 29 de milioane (acest număr este obținut prin înmulțire 8 * ), atunci există o metodă și mai economică de stocare a acestor matrice — șiruri de biți, deoarece implementarea lor optimizează în mod special golurile mari.
Manipulările cu șirurile de biți se realizează prin funcția .
; setarea bitului
SET $BIT(rowID, positionID) = 1
; obținerea bitului
Write $BIT(rowID, positionID)
Tabelul de tranziții al automatelor finite
Deoarece graficul de tranziții al automatului finit este un grafic obișnuit, și tabelul de tranziții al automatului finit este aceeași matrice de adiacență despre care s-a vorbit mai sus.
Automatele celulare
Cel mai cunoscut automat celular este , care, din cauza regulilor sale (când o celulă are mulți vecini — moare) reprezintă un vector rar.
Stephen Wolfram consideră că automatele celulare sunt În 2002, a publicat o carte de 1280 de pagini intitulată „A New Kind of Science”, în care argumentează pe larg că realizările în domeniul automatelor celulare nu sunt izolate, ci foarte robuste și au o mare importanță pentru toate domeniile științei.
S-a demonstrat că orice algoritm realizabil pe un computer poate fi implementat prin intermediul unui automat celular. Automatele celulare sunt utilizate pentru modelarea mediilor și sistemelor dinamice, pentru soluționarea problemelor algoritmice și pentru alte scopuri.
Dacă avem un câmp imens și trebuie să înregistrăm toate stările intermediare ale automatului celular, atunci este complet rezonabil să folosim globale.
Cartografie
Primul lucru care îmi vine în minte când se vorbește despre utilizarea vectorilor rari este sarcinile cartografice.
În general, pe hărți există foarte mult spațiu gol. Dacă harta este reprezentată prin pixeli mari, atunci 71% din pixeli pe Pământ vor fi ocupați de ocean. Vector rar. Iar dacă ar fi reprezentate doar creațiile omului, atunci spațiul gol ar depăși 95%.
Desigur, nimeni nu stochează hărțile sub formă de matrice raster, se folosește reprezentarea vectorială.
Dar ce sunt hărțile vectoriale? Ele reprezintă un cadru format din puncte, polilinii și poligoane.
Practic, este o bază de date a punctelor și a legăturilor dintre ele.
Una dintre cele mai ambițioase sarcini de cartografiere este misiunea de cartografiere a galaxiei noastre cu telescopul Gaia. Vorbind figurat, galaxia noastră, ca și întreaga univers, este o masă rară continuă: spații imense de vid, în care există puncte rare mici – stele. Spațiul gol reprezintă 99,999999…….%. Pentru a stoca harta galaxiei noastre, a fost aleasă o bază de date pe globale – Caché.
Nu știu structura exactă a globalelor în acest proiect, pot presupune că este ceva similar cu:
Set ^galaxy(b, l, d) = 1; Numărul stelei conform catalogului, dacă există
Set ^galaxy(b, l, d, "name") = "Soare"
Set ^galaxy(b, l, d, "type") = "normal"; opțiuni blackhole, quasar, red_dwarf etc.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercur"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Unde b, l, d — sunt și distanța până la Soare.
Structura flexibilă a globalelor permite stocarea oricăror caracteristici necesare ale stelelor și planetelor, deoarece bazele pe globale sunt fără schemă (scheme-less).
Pentru stocarea hărții universului nostru, Caché a fost aleasă nu doar pentru flexibilitate, ci și pentru capacitatea sa de a salva foarte rapid fluxurile de date, creând în același timp globale indexate pentru căutări rapide.
Dacă ne întoarcem la Pământ, au fost create proiecte cartografice pe globale și fork-ul OpenStreetMap — .
Recent, la au fost implementate indicii geospațiali . Așteptăm de la autorii articolului detalii despre implementare.
Implementarea indicilor spațiali pe globale în OpenStreetMap XAPI
Imaginile sunt preluate din .
Întreaga globă terestră este împărțită în pătrate, apoi în subpătrate și subpătratele în sub-subpătrate și așa mai departe. În general, obținem o structură ierarhică pentru stocarea cărora au fost create globale.
În orice moment, putem solicita practic instantaneu pătratul necesar sau să-l eliminăm, iar toate subpătratele vor fi de asemenea returnate sau șterse.
O schemă similară pe globale poate fi realizată în mai multe moduri.
Variantă 1:
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 1) = idPrimaPunctului
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 2) = idA douaPunctului
...Variantă 2:
Set ^m('abacdabcdabacdabcda', 1) = idPrimaPunctului
Set ^m('abacdabcdabacdabcda', 2) = idA douaPunctului
...În ambele cazuri, este simplu să cerem punctele aflate în cadrul oricărui nivel pe COS/M. Va fi ceva mai ușor să curățăm bucățile pătrate de spațiu de orice nivel în prima variantă, dar rareori este necesar.
Un exemplu al uneia dintre pătrățile de nivel inferior:
Iată câteva globale din proiectul XAPI: reprezentarea indexului pe globale:
Global ^way este folosit pentru stocarea punctelor (drumuri, râuri mici etc.) și poligoane (zone închise: clădiri, păduri etc.).
O clasificare generală a utilizării matricilor sparse pe globale.
- Stocăm coordonatele anumitor obiecte și stările acestora (cartografiere, automate celulare)
- Stocăm matrice sparse.
Pentru cazul 2) la interogarea unei coordonate specifice, unde elementul nu are o valoare atribuită, trebuie să obținem valoarea implicită a elementului din matricea rară.
Beneficiile pe care le obținem prin stocarea matricilor multidimensionale pe globale
Ștergere rapidă și/sau extragerea bucăților de spațiu, care sunt multiplu de linii, plane, cuburi etc. În cazurile în care sunt folosite indecși întregi, poate fi utilă posibilitatea de a șterge rapid și/sau de a extrage bucăți de spațiu, care sunt multiplu de linii, plane, cuburi etc.
Comanda putem șterge atât un element individual, cât și o linie, și chiar un întreg plan. Datorită proprietăților globelor, acest lucru se întâmplă foarte repede — de mii de ori mai repede decât ștergerea pe elemente.
În imagine este prezentată o matrice tridimensională în global ^a și diferite tipuri de ștergeri.
Pentru extragerea bucăților de spațiu după indecși cunoscuți, putem folosi comanda .
Extragerea unei coloane a matricei într-o variabilă Column:
; Să definim o matrice rară tridimensională 3x3x3
Set ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Merge Column = ^a(2,2)
; Să afișăm variabila Column
Zwrite Column
Concluzie:
Column(0)=1
Column(2)=1
Ce este interesant este că în variabila Column am obținut de asemenea o matrice rară, la care trebuie să ne referim și prin , deoarece valorile implicite nu sunt stocate în ea.
Extragerea bucăților de spațiu poate fi realizată și printr-un mic program folosind funcția . Aceasta este în special convenabilă în spațiile ale căror indecși nu sunt cuantizați (cartografie).
Concluzie
Timpurile actuale impun noi sarcini ambițioase. Grafurile pot consta din miliarde de vârfuri, hărțile din miliarde de puncte, iar cineva poate chiar dori să-și lanseze propria univers pe automate celulare (, ).
Când volumul de date al array-urilor sparse nu mai poate fi stocat în memoria operațională și trebuie să lucrăm cu ele, ar trebui să considerăm posibilitatea implementării unor astfel de proiecte pe globale și COS.
Vă mulțumim pentru atenție! Așteptăm întrebările și sugestiile dumneavoastră în comentarii.
Declinarea: Această articolă și comentariile mele la aceasta reprezintă opinia mea și nu au legătură cu poziția oficială a corporației InterSystems.
Sursa: habr.com
