Nelle parti precedenti (, ) abbiamo parlato dei globali come alberi; in questa parte esamineremo i globali come array sparsi.
è un tipo di array in cui la maggior parte dei valori assume lo stesso valore.
Nella pratica, si trovano spesso array sparsi così enormi che non ha senso occupare memoria con elementi identici. Pertanto, ha senso implementare gli array sparsi in modo tale che la memoria non venga spesa per memorizzare valori identici.
In alcuni linguaggi di programmazione, gli array sparsi sono parte del linguaggio stesso, , . In altri linguaggi di programmazione, ci sono librerie speciali che consentono la loro implementazione. Per C++ — e altri.
I globali sono buoni candidati per l'implementazione di array sparsi perché:
- Memorizzano solo i valori di nodi specifici e non memorizzano i valori non definiti;
- L'interfaccia di accesso al valore di un nodo è estremamente simile a come in molti linguaggi di programmazione è implementato l'accesso a un elemento di un array multidimensionale.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Il global è una struttura di dati abbastanza a basso livello per memorizzare informazioni, quindi ha prestazioni eccellenti (da centinaia di migliaia a decine di milioni di transazioni al secondo, a seconda dell'hardware; vedi )
Poiché il global è una struttura persistente, ha senso utilizzare array sparsi quando si sa in anticipo che la quantità di memoria RAM sarà insufficiente.
Una delle proprietà delle implementazioni di array sparsi è il ritorno di un certo valore predefinito quando si accede a una cella non definita.
Questo può essere implementato utilizzando la funzione in COS. In questo esempio, è considerato un array tridimensionale.
SET a = $GET(^a(x,y,z), defValue)In quali compiti sono necessari gli array sparsi e come possono i globali essere utili?
Matrice di adiacenza (connettività)
vengono utilizzate per rappresentare grafi:
È evidente che più grande è il grafo, più zeri ci saranno nella matrice. Se, ad esempio, prendiamo un grafo di una rete sociale e lo rappresentiamo sotto forma di tale matrice, sarà quasi interamente composto da zeri, cioè sarà un array sparso.
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 questo esempio memorizziamo nel global ^m la matrice di adiacenza, così come il numero di spigoli per ciascun nodo (chi è amico di chi e il numero di amici).
Se il numero di elementi nel grafo non è superiore a 29 milioni (questo numero è preso come prodotto di 8 * ), esiste un modo ancora più economico per memorizzare tali matrici: le stringhe di bit, poiché la loro implementazione ottimizza in modo speciale i grandi intervalli vuoti.
Le operazioni sulle stringhe di bit vengono eseguite dalla funzione .
; impostazione del bit
SET $BIT(rowID, positionID) = 1
; ottenimento del bit
Write $BIT(rowID, positionID)
Tabella delle transizioni di un automa finito
Poiché il grafo delle transizioni di un automa finito è un normale grafo, anche la tabella delle transizioni è la stessa matrice di adiacenza di cui si è parlato sopra.
Automati cellulari
Il più noto automa cellulare è , che a causa delle sue regole (quando una cellula ha molti vicini, muore) rappresenta una matrice sparsa.
Stephen Wolfram ritiene che gli automi cellulari rappresentino . Nel 2002 pubblica un libro di 1280 pagine intitolato "A New Kind of Science", in cui argomenta ampiamente che le scoperte nel campo degli automi cellulari non sono isolate, ma piuttosto robuste e hanno grande importanza in tutti i campi della scienza.
È stato dimostrato che qualsiasi algoritmo eseguibile su un computer può essere realizzato tramite un automa cellulare. Gli automi cellulari vengono utilizzati per modellare ambienti e sistemi dinamici, per risolvere problemi algoritmici e per altri scopi.
Se abbiamo un campo enorme e dobbiamo registrare tutti gli stati intermedi dell'automa cellulare, è senz'altro ragionevole utilizzare variabili globali.
Cartografia
La prima cosa che mi viene in mente quando si parla di utilizzare matrici sparse è il problema della cartografia.
Di solito, sulle mappe c'è molto spazio vuoto. Se si rappresenta la mappa come grandi pixel, il 71% dei pixel della Terra sarà occupato dall'oceano. Matrice sparsa. E se si raffigurano solo le opere create dall'uomo, lo spazio vuoto sarà superiore al 95%.
Certo, nessuno conserva le mappe sotto forma di matrici raster, si utilizza una rappresentazione vettoriale.
Ma cosa rappresentano le mappe vettoriali? Sono una sorta di contorno e consistono in punti, linee poligonali e poligoni.
In effetti, il database dei punti e delle loro connessioni.
Una delle sfide più ambiziose della mappatura è la missione di mappare la nostra galassia con il telescopio Gaia. Figurativamente, la nostra galassia, come l'intero universo, è un vasto ed uniforme vuoto: enormi spazi di nulla, in cui si trovano piccole e rare stelle. Lo spazio vuoto rappresenta il 99,999999…….%. Per memorizzare la mappa della nostra galassia è stato scelto un database globale — Caché.
Non conosco la struttura esatta dei globali in questo progetto, ma posso supporre che sia qualcosa di simile a:
Set ^galaxy(b, l, d) = 1; Numero della stella nel catalogo, se esistente
Set ^galaxy(b, l, d, "name") = "Sole"
Set ^galaxy(b, l, d, "type") = "normale"; varianti blackhole, quasar, red_dwarf, ecc.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercurio"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Dove b, l, d sono e distanza dal Sole.
La struttura flessibile dei globali permette di mantenere tutte le caratteristiche necessarie delle stelle e dei pianeti, poiché i database globali sono senza schema (scheme-less).
La scelta di Caché per memorizzare la mappa del nostro universo è stata motivata non solo dalla sua flessibilità, ma anche dalla sua capacità di salvare molto rapidamente i flussi di dati, creando nel contempo globali indicizzati per una rapida ricerca.
Tornando sulla Terra, sono stati creati progetti cartografici sui globali e il fork di OpenStreetMap — .
Recentemente al sono stati implementati indici geospaziali Aspettiamo dai autori dell'articolo ulteriori dettagli sull'implementazione.
Implementazione degli indici spaziali nel globale di OpenStreetMap XAPI
Le immagini sono state prese da .
L'intero pianeta Terra viene suddiviso in quadrati, poi in sottopartizioni, e le sottopartizioni in sotto-sottopartizioni, e così via. In generale, otteniamo una struttura gerarchica per la quale sono stati creati i globali.
In qualsiasi momento possiamo richiedere praticamente istantaneamente il quadrato desiderato o pulirlo, e tutte le sottopartizioni saranno restituite o rimosse.
Una simile struttura sui globali può essere implementata in diversi modi.
Opzione 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idPrimoPunto
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idSecondoPunto
...Opzione 2:
Set ^m('abacdabcdabacdabcda', 1) = idPrimoPunto
Set ^m('abacdabcdabacdabcda', 2) = idSecondoPunto
...In entrambi i casi, non è difficile richiedere i punti che si trovano all'interno di un quadrato di qualsiasi livello su COS/M. Sarà un po' più facile pulire aree quadrate di qualsiasi livello nel primo caso, ma questo è raramente necessario.
Esempio di uno dei quadrati di basso livello:
Ecco alcuni globali dal progetto XAPI: visualizzazione dell'indice sui globali:
Globale ^way utilizzato per memorizzare i punti (strade, piccoli fiumi ecc.) e poligoni (aree chiuse: edifici, foreste ecc.).
Una classificazione grossolana dell'uso di matrici sparse nei globali.
- Memorizziamo le coordinate di determinati oggetti e i loro stati (mappatura, cellular automata)
- Memorizziamo matrici sparse.
Per il caso 2) quando si richiede una coordinata specifica, dove all'elemento non è stato assegnato un valore, dobbiamo ottenere il valore dell'elemento della matrice sparsa per impostazione predefinita.
I vantaggi che otteniamo dalla memorizzazione di matrici multidimensionali nei globali
Cancellazione rapida e/o estrazioni di aree dello spazio, multiple di righe, piani, cubi ecc. Nei casi in cui vengono utilizzati indici interi, può risultare utile la possibilità di cancellazione rapida e/o estrazione di aree dello spazio, multiple di righe, piani, cubi ecc.
Con il comando possiamo eliminare sia un singolo elemento che una riga, e persino un intero piano. Grazie alle proprietà dei globali, questo avviene molto rapidamente — migliaia di volte più veloce rispetto alla cancellazione elemento per elemento.
In figura è mostrato un array tridimensionale nel globale ^a e diversi tipi di cancellazioni.
Per estrarre aree dello spazio in base a indici noti, è possibile utilizzare il comando .
Estrazione di una colonna della matrice nella variabile Column:
; Definiamo una matrice sparsa tridimensionale 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
Unisci Column = ^a(2,2)
; Visualizziamo la variabile Column
Zwrite Column
Conclusione:
Column(0)=1
Column(2)=1
È interessante notare che nella variabile Column abbiamo anch'essa ottenuto una matrice sparsa, alla quale bisogna accedere attraverso , poiché i valori predefiniti non sono memorizzati in essa.
L'estrazione di aree dello spazio può anche essere effettuata tramite un piccolo programma che utilizza la funzione . Questo è particolarmente utile in spazi i cui indici non sono quantizzati (cartografia).
Conclusione
I tempi attuali pongono nuove sfide ambiziose. I grafi possono contenere miliardi di vertici, le mappe miliardi di punti, e qualcuno potrebbe anche voler avviare il proprio universo su automi cellulari (, ).
Quando il volume dei dati di array sparsi non può più essere contenuto nella memoria RAM e bisogna comunque lavorarci, è opportuno considerare la possibilità di realizzare progetti simili su globali e COS.
Grazie per la vostra attenzione! Aspettiamo le vostre domande e commenti.
Avviso: Questo articolo e i miei commenti sono la mia opinione e non riflettono la posizione ufficiale della società InterSystems.
Fonte: habr.com
