In parti precedenti (, ) avemu parlatu di i globals cum'è l'arbureti, in questu avemu da guardà i globals cum'è arrays sparse.
hè un tipu di array in quale a maiò parte di i valori piglianu u listessu valore.
In a pratica, l'arrays sparse sò spessu cusì enormi chì ùn ci hè micca un puntu di occupà a memoria cù elementi idèntici. Per quessa, hè sensu di implementà array sparse in tale manera chì a memoria ùn hè micca persa per almacenà valori identici.
In certi linguaggi di prugrammazione, array sparse sò inclusi in a lingua stessa, , . L'altri linguaggi di prugrammazione anu biblioteche speciali chì permettenu di implementà. Per C++ - è altri.
I Globali sò boni candidati per l'implementazione di matrici sparse perchè:
- Guardanu i valori di solu certi nodi è ùn guardanu micca i valori di quelli indefiniti;
- L'interfaccia per accede à u valore di un node hè assai simile à quanti linguaggi di prugrammazione implementanu l'accessu à un elementu di array multidimensionale.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global hè una struttura abbastanza bassu per almacenà e dati, per quessa hà caratteristiche di velocità eccezziunale (da centinaie di millaie à decine di milioni di transazzione per seconda, secondu u hardware, vede quì sottu). )
Siccomu u glubale hè una struttura persistente, hè sensu di creà arrays sparse nantu à elli quandu si cunnosce in anticipu chì a quantità di RAM ùn serà micca abbastanza.
Una di e pruprietà di l'implementazioni di array sparse hè di rinvià un valore predeterminatu se un accessu hè fattu à una cellula indefinita.
Questu pò esse implementatu cù a funzione in COS. Questu esempiu cunsidereghja un array tridimensionale.
SET a = $GET(^a(x,y,z), defValue)Chì travaglii necessitanu array sparse è cumu ponu aiutà i globals?
Matrice di adiacenza (connettività).
usati per rapprisintà i grafici:
Ovviamente, u più grande u graficu, più zeri ci saranu in a matrice. Se, per esempiu, pigliemu un gràficu di a rete suciale è u prisintà in a forma di una matrice simili, allora sarà quasi cumplettamente custituitu di zeri, i.e. serà un array sparse.
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
....
In questu esempiu, salvemu in u mondu ^m matrice di cunnessione, è ancu u nùmeru di bordi à ogni node (quale hè amici cù quale è u numeru di amici).
Se u numeru di elementi in u graficu ùn hè micca più di 29 milioni (stu numeru hè pigliatu cum'è u pruduttu di 8 * ), vale à dì, un modu ancu più ecunomicu per almacenà tali matrici hè strings bit, postu chì a so implementazione ottimisà i grandi spazii in una manera speciale.
Manipulazioni cù strings di bit sò realizati da a funzione .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tavola di transizione di a macchina di u statu
Siccomu u gràficu di transizione di un automatu finitu hè un gràficu ordinariu, allora a tavola di transizione di l'automatu finitu hè a listessa matrice di adiacenza discututa sopra.
Automatis cellulari
L'automatu cellulare più famosu hè , chì, per via di e so regule (quandu una cellula hà assai vicini, mori) hè un array sparse.
Stephen Wolfram crede chì l'automati cellulari sò . In u 2002, hà publicatu un libru di 1280 pagine, A New Kind of Science, in u quale sustene in generale chì l'avanzati in l'automati cellulari ùn sò micca isolati, ma sò duraturi è anu grandi implicazioni per tutti i campi di a scienza.
Hè statu pruvatu chì qualsiasi algoritmu eseguibile in un computer pò esse implementatu cù un automatu cellulare. L'automati cellulari sò usati per mudificà ambienti è sistemi dinamichi, per risolve i prublemi algoritmichi è per altri scopi.
Se avemu un campu enormu è avemu bisognu di registrà tutti i stati intermedii di un automatu cellulare, allora hè sensu di utilizà globals.
Cartugrafia
A prima cosa chì mi vene in mente quandu si tratta d'utilizà array sparse hè i travaglii di mappatura.
In regula, ci hè assai spaziu viotu nantu à e carte. Se a mappa hè rapprisintata cum'è pixel grande, allora u 71% di i pixel di a Terra seranu occupati da l'oceanu. Array sparse. È s'è vo applicà solu opere di mani umane, allura u spaziu viotu serà più di 95%.
Di sicuru, nimu guarda carte in forma di matrici raster; una rapprisintazioni vettoriali hè aduprata.
Ma chì sò e carte vettoriali? Questu hè un tipu di quadru è polilinei è poligoni custituiti da punti.
Essenzialmente una basa di dati di punti è cunnessione trà elli.
Una di e missioni cartografiche più ambiziose hè a missione di u Telescopiu Gaia per cartografia a nostra galassia. Figurativamente parlante, a nostra galassia, cum'è l'universu sanu, hè un cuntinuu sparse array: enormi spazii di vacuità in quale ci sò rari picculi punti - stelle. U spaziu viotu hè 99,999999…….%. Per almacenà a mappa di a nostra galaxia, hè stata scelta una basa di dati glubale - Caché.
Ùn cunnosci micca a struttura esatta di globals in stu prughjettu, possu suppone chì hè qualcosa simili à:
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
...
Induve sò b, l, d è distanza à u sole.
A struttura flexibule di globals permette di salvà tutte e caratteristiche necessarie di stelle è pianeti, postu chì e basa nantu à i globals sò senza schema.
Per almacenà a mappa di u nostru universu, Caché hè statu sceltu micca solu per a so flessibilità, ma ancu per a so capacità di almacenà un flussu di dati assai rapidamente, mentre chì simultaneamente creanu index globals per ricerche veloci.
Se vultemu à a Terra, i prughjetti cartografichi sò stati creati nantu à i globals è una furchetta di OpenStreetMap - .
Recentemente nantu Indici geospaziali sò stati implementati . Aspittemu un articulu di l'autori cù dettagli di implementazione.
Implementazione di indici spaziali nantu à un globale in OpenStreetMap XAPI
Ritratti pigliati da .
U globu sanu hè divisu in quadrati, dopu sottu-squares, è sub-squares in sub-squares, è cusì. In generale, avemu una struttura gerarchica per almacenà quali globals sò creati.
In ogni mumentu, pudemu quasi istantaneamente dumandà u quadru desideratu o sguassate, è tutti i sub-squares seranu ancu tornati o sbulicati.
Un schema simile nantu à i globals pò esse implementatu in parechje manere.
Opzione 1:
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ВторойТочки
...Opzione 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...In i dui casi, ùn hè micca difficiule di utilizà COS / M per dumandà punti situati in una piazza di ogni livellu. Serà un pocu più faciule per pulizziari pezzi quadrati di spaziu à ogni livellu in a prima opzione, ma questu hè raramente necessariu.
Un esempiu di unu di i quadrati di livellu più bassu:
È quì sò parechji globals da u prughjettu XAPI: rapprisintazioni di un indice nantu à globals:
glubale ^ modu usatu per almacenà punti (strade, fiumi chjuchi, etc.) è poligoni (zoni chjusi : palazzi, fureste, etc.).
Classificazione approssimativa di l'usu di array sparse in globals.
- Almacenemu e coordenate di certi ogetti è i so stati (cartografia, autumati cellulari)
- Guardemu matrici sparse.
Per u casu 2) quandu dumandate una coordenada specifica induve l'elementu ùn hè micca assignatu un valore, avemu da ottene u valore di l'elementu sparse array predeterminatu.
Bonus chì ricevemu quandu almacenà matrici multidimensionali in globals
Eliminate rapidamente è / o selezziunate pezzi di spaziu chì sò multiplici di fila, piani, cubi, etc. Per i casi induve l'indici interi sò utilizati, a capacità di sguassà rapidamente è / o piglià pezzi di spaziu chì sò multiplici di fila, piani, cubi, etc.
squadra pudemu sguassà sia un elementu unicu o una fila, o ancu un pianu sanu. Grazie à e proprietà di globals, questu succede assai rapidamente - millaie di volte più veloce di a rimozione di l'elementu per l'elementu.
A figura mostra un array tridimensionale in un globale ^a è diversi tipi di eliminazioni.
Per selezziunà pezzi di spaziu cù indici cunnisciuti, pudete aduprà u cumandamentu .
Selezzione di una colonna di matrice in a variàbile di Colonna:
; Зададим трёхмерный разреженный массив 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
Cunsigliu:
Column(0)=1
Column(2)=1
Ciò chì hè interessante nantu à a variabile Colonna hè chì avemu ancu un array sparse, chì deve ancu accede à traversu , postu chì i valori predeterminati ùn sò micca almacenati in questu.
Selezziunà pezzi di spaziu pò ancu esse fattu attraversu un picculu prugramma cù a funzione . Questu hè soprattuttu cunvene nantu à spazii chì l'indici ùn sò micca quantizzati (cartografia).
cunchiusioni
I tempi attuali ponenu novi compiti ambiziosi. I grafici ponu esse cumposti da miliardi di vertici, mape cumposti da miliardi di punti, è alcuni puderanu ancu vulete gestisce u so propiu universu nantu à l'automatizazione cellulare (, ).
Quandu u voluminu di dati da sparse arrays ùn ponu più intruduce in RAM, ma avete bisognu di travaglià cun elli, allora vale a pena cunsiderà a pussibilità di implementà prughjetti simili nantu à globals è COS.
Grazie per a vostra attenzione! Aspittemu e vostre dumande è desideri in i cumenti.
Légales: Questu articulu è i mo cumenti sò a mo opinione è ùn anu micca relazione cù a pusizione ufficiale di InterSystems Corporation.
Source: www.habr.com