În părțile anterioare (, ) am vorbit despre globals ca arbori, în acesta ne vom uita la globale ca pe matrice rare.
este un tip de matrice în care majoritatea valorilor iau aceeași valoare.
În practică, tablourile rare sunt adesea atât de mari încât nu are rost să ocupi memoria cu elemente identice. Prin urmare, este logic să implementați matrice rare în așa fel încât memoria să nu fie irosită pentru stocarea valorilor identice.
În unele limbaje de programare, matricele rare sunt incluse în limbajul în sine, , . Alte limbaje de programare au biblioteci speciale care vă permit să le implementați. Pentru C++ - etc
Globalurile sunt candidați buni pentru implementarea matricelor rare deoarece:
- Ele stochează valorile doar anumitor noduri și nu stochează valorile celor nedefinite;
- Interfața pentru accesarea valorii unui nod este extrem de similară cu câte limbaje de programare implementează accesul la un element de matrice multidimensională.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global este o structură de nivel destul de scăzut pentru stocarea datelor, prin urmare are caracteristici de viteză remarcabile (de la sute de mii la zeci de milioane de tranzacții pe secundă, în funcție de hardware, vezi mai jos). )
Deoarece globala este o structură persistentă, este logic să creați matrice rare pe ele atunci când se știe dinainte că cantitatea de RAM nu va fi suficientă.
Una dintre proprietățile implementărilor de matrice rare este de a returna o valoare implicită dacă se face acces la o celulă nedefinită.
Acest lucru poate fi implementat folosind funcția în COS. Acest exemplu ia în considerare o matrice tridimensională.
SET a = $GET(^a(x,y,z), defValue)Ce sarcini necesită matrice rare și cum pot ajuta globalurile?
Matricea de adiacență (conectivitate).
folosit pentru a reprezenta grafice:
Evident, cu cât graficul este mai mare, cu atât vor fi mai multe zerouri în matrice. Dacă, de exemplu, luăm un grafic de rețea socială și îl prezentăm sub forma unei matrice similare, atunci acesta va consta aproape în întregime din zerouri, adică. va fi o matrice 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, economisim la nivel global ^m matricea de conectivitate, precum și numărul de margini la fiecare nod (cine este prieten cu cine și numărul de prieteni).
Dacă numărul de elemente din grafic nu depășește 29 de milioane (acest număr este considerat produsul lui 8 * ), adică o modalitate și mai economică de a stoca astfel de matrice sunt șirurile de biți, deoarece implementarea lor optimizează spațiile mari într-un mod special.
Manipulările cu șiruri de biți sunt efectuate de funcție .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabelul de tranziție al mașinii de stări
Deoarece graficul de tranziție al unui automat finit este un grafic obișnuit, atunci tabelul de tranziție al automatului finit este aceeași matrice de adiacență discutată mai sus.
Automate celulare
Cel mai cunoscut automat celular este , care, datorită regulilor sale (când o celulă are mulți vecini, moare) este o matrice rară.
Stephen Wolfram crede că automatele celulare sunt . În 2002, a publicat o carte de 1280 de pagini, A New Kind of Science, în care susține în linii mari că progresele în automatele celulare nu sunt izolate, ci sunt de durată și au implicații mari pentru toate domeniile științei.
S-a dovedit că orice algoritm executabil pe un computer poate fi implementat folosind un automat celular. Automatele celulare sunt folosite pentru a modela medii și sisteme dinamice, pentru a rezolva probleme algoritmice și în alte scopuri.
Dacă avem un câmp uriaș și trebuie să înregistrăm toate stările intermediare ale unui automat celular, atunci are sens să folosim globale.
Cartografie
Primul lucru care îmi vine în minte atunci când vine vorba de utilizarea matricelor rare este maparea sarcinilor.
De regulă, pe hărți există mult spațiu liber. Dacă harta este reprezentată ca pixeli mari, atunci 71% din pixelii Pământului vor fi ocupați de ocean. Matrice rară. Și dacă aplicați numai lucrări ale mâinilor umane, atunci spațiul gol va fi mai mare de 95%.
Desigur, nimeni nu stochează hărți sub formă de matrice raster este folosită o reprezentare vectorială.
Dar ce sunt hărțile vectoriale? Acesta este un fel de cadru și polilinii și poligoane formate din puncte.
În esență, o bază de date cu puncte și conexiuni între ele.
Una dintre cele mai ambițioase misiuni de cartografiere este misiunea Telescopului Gaia de a mapa galaxia noastră. Figurat vorbind, galaxia noastră, ca și întregul univers, este o matrice rară continuă: spații uriașe de gol în care există puncte mici rare - stele. Spațiul gol este 99,999999…….%. Pentru a stoca harta galaxiei noastre, a fost aleasă o bază de date globală - Caché.
Nu cunosc structura exactă a globalelor din acest proiect, pot presupune că este ceva similar cu:
Set ^galaxy(b, l, d) = 1; Номер звезды по каталогу, если есть
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; варианты blackhole, quazar, red_dwarf и т.д.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Unde sunt b, l, d și distanța până la Soare.
Structura flexibilă a globalelor vă permite să salvați orice caracteristică necesară a stelelor și planetelor, deoarece bazele pe globale sunt fără scheme.
Pentru a stoca harta universului nostru, Caché a fost ales nu numai pentru flexibilitatea sa, ci și pentru capacitatea sa de a stoca foarte rapid un flux de date, creând simultan indexuri globale pentru căutări rapide.
Dacă ne întoarcem pe Pământ, atunci s-au creat proiecte cartografice pe globale și un furk de OpenStreetMap - .
Recent pe au fost implementați indici geospațiali . Așteptăm un articol de la autori cu detalii de implementare.
Implementarea indicilor spațiali pe un global în OpenStreetMap XAPI
Poze luate de pe .
Întregul glob este împărțit în pătrate, apoi subpătrate și subpătrate în subsubpătrate și așa mai departe. În general, obținem o structură ierarhică pentru stocarea globale care sunt create.
În orice moment, putem solicita aproape instantaneu pătratul dorit sau îl putem șterge, iar toate subpătratele vor fi, de asemenea, returnate sau șters.
O schemă similară pe global poate fi implementată în mai multe moduri.
1 opțiune:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...2 opțiune:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...În ambele cazuri, nu este dificil să utilizați COS/M pentru a solicita puncte situate într-un pătrat de orice nivel. Va fi oarecum mai ușor să curățați bucăți pătrate de spațiu la orice nivel în prima opțiune, dar acest lucru este rareori necesar.
Un exemplu de unul dintre pătratele de nivel inferior:
Și iată câteva globaluri din proiectul XAPI: reprezentarea unui index pe global:
global ^ mod folosit pentru a stoca puncte (drumuri, râuri mici etc.) și poligoane (zone închise: clădiri, păduri etc.).
Clasificarea aproximativă a utilizării tablourilor rare pe globale.
- Stocam coordonatele anumitor obiecte si starile acestora (cartare, automate celulare)
- Stocăm matrici rare.
Pentru cazul 2) când se solicită o coordonată specifică în care elementului nu i se atribuie o valoare, trebuie să obținem valoarea elementului implicit de matrice dispersată.
Bonusuri pe care le primim la stocarea matricelor multidimensionale în globale
Eliminați și/sau selectați rapid bucăți de spațiu care sunt multipli de rânduri, avioane, cuburi etc. Pentru cazurile în care sunt utilizați indici întregi, poate fi utilă capacitatea de a elimina și/sau de a prelua rapid bucăți de spațiu care sunt multipli de rânduri, planuri, cuburi etc.
echipă putem șterge fie un singur element, fie un rând, fie chiar un întreg plan. Datorită proprietăților globale, acest lucru se întâmplă foarte repede - de mii de ori mai rapid decât eliminarea element cu element.
Figura prezintă o matrice tridimensională într-o globală ^a și diferite tipuri de ștergeri.
Pentru a selecta bucăți de spațiu folosind indecși cunoscuți, puteți utiliza comanda .
Selectarea unei coloane matrice în variabila Coloană:
; Зададим трёхмерный разреженный массив 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)
; Выведем переменную Column
Zwrite Column
Concluzie:
Column(0)=1
Column(2)=1
Ceea ce este interesant la variabila Column este că avem și o matrice rară, care trebuie accesată și prin , deoarece valorile implicite nu sunt stocate în el.
Selectarea bucăților de spațiu se poate face și printr-un mic program folosind funcția . Acest lucru este convenabil mai ales pe spațiile ai căror indici nu sunt cuantificați (cartografie).
Concluzie
Timpurile actuale pun noi sarcini ambițioase. Graficele pot fi formate din miliarde de vârfuri, hărți din miliarde de puncte și unii ar putea chiar să-și dorească să-și conducă propriul univers pe automate celulare (, ).
Când volumul de date din matrice rare nu se mai poate încadra în RAM, dar trebuie să lucrați cu ele, atunci merită să luați în considerare posibilitatea de a implementa proiecte similare pe global și COS.
Vă mulțumim pentru atenție! Așteptăm întrebările și urările dumneavoastră în comentarii.
Declinare a responsabilităţii: Acest articol și comentariile mele la acesta sunt părerea mea și nu au nicio legătură cu poziția oficială a InterSystems Corporation.
Sursa: www.habr.com