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, ci si imbatte spesso in array sparsi così vasti 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 integrante del linguaggio, , . In altri linguaggi di programmazione ci sono librerie speciali che permettono di implementarli. Per C++ — e altro.
I globali sono buoni candidati per l'implementazione di array sparsi, perché:
- Conservano solo i valori di nodi specifici e non memorizzano i valori non definiti;
- L'interfaccia di accesso ai valori dei nodi è estremamente simile a come molti linguaggi di programmazione implementano l'accesso agli elementi di un array multidimensionale.
Set ^a(1, 2, 3)=5 Scrivi ^a(1, 2, 3) - Global è una struttura di basso livello per la memorizzazione dei dati, quindi presenta prestazioni straordinarie (da centinaia di migliaia a decine di milioni di transazioni al secondo a seconda dell'hardware). )
Poiché Global è una struttura persistente, ha senso utilizzare array sparsi solo quando si sa in anticipo che la memoria RAM sarà insufficiente.
Una delle caratteristiche delle implementazioni degli array sparsi è il ritorno di un valore predefinito se si accede a una cella non definita.
Questo può essere realizzato 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 aiutare i Global?
Matrice di adiacenza (di connettività)
vengono utilizzate per rappresentare grafi:
È evidente che quanto più grande è il grafo, tanto più zeri ci saranno nella matrice. Se, ad esempio, si prende un grafo di una rete sociale e lo si rappresenta sotto forma di tale matrice, sarà per lo più composto da zeri, cioè sarà un array sparso.
Imposta ^m(id1, id2) = 1
Imposta ^m(id1, id3) = 1
Imposta ^m(id1, id4) = 1
Imposta ^m(id1) = 3
Imposta ^m(id2, id4) = 1
Imposta ^m(id2, id5) = 1
Imposta ^m(id2) = 2
....
In questo esempio salviamo in globale ^m la matrice di adiacenza, così come il numero di collegamenti per ciascun nodo (chi è amico di chi e quanti amici ha).
Se il numero di elementi nel grafo non supera i 29 milioni (questo numero è considerato come il prodotto di 8 * ), c'è un modo ancora più economico per memorizzare tali matrici — le stringhe di bit, poiché nella loro implementazione vengono ottimizzati in modo speciale i grandi intervalli vuoti.
Le operazioni con le stringhe di bit vengono effettuate dalla funzione .
; imposta il bit
SET $BIT(rowID, positionID) = 1
; ottieni il bit
Scrivi $BIT(rowID, positionID)
Tabella di transizione dell'automa finito
Poiché il grafo delle transizioni dell'automa finito è un grafo ordinario, la tabella di transizione dell'automa finito è la stessa matrice di adiacenza di cui si è parlato sopra.
Automi cellulari
Il più noto automa cellulare è , che a causa delle sue regole (quando una cellula ha molti vicini — essa muore) rappresenta un array sparso.
Stephen Wolfram, ritiene che gli automi cellulari siano una . Nel 2002 pubblica un libro di 1280 pagine intitolato «A New Kind of Science», in cui argomenta ampiamente che i progressi nel campo degli automi cellulari non sono isolati, ma molto robusti e di grande importanza per tutti i settori della scienza.
È stato dimostrato che qualsiasi algoritmo eseguibile su un computer può essere realizzato attraverso un automa cellulare. Gli automi cellulari sono utilizzati per modellare ambienti dinamici e sistemi, per risolvere problemi algoritmici e per altri scopi.
Se abbiamo un campo enorme e dobbiamo registrare tutti gli stati intermedi di un automa cellulare, ha senso utilizzare delle variabili globali.
Cartografia
La prima cosa che mi viene in mente quando si parla di utilizzare array sparsi sono i problemi di cartografia.
In genere, le mappe contengono molto spazio vuoto. Se si rappresenta la mappa come grandi pixel, il 71% dei pixel della Terra sarà occupato dall'oceano. Un array sparso. E se si segnano solo le opere dell'uomo, lo spazio vuoto sarà superiore al 95%.
Certo, nessuno memorizza le carte come matrici raster; si utilizza una rappresentazione vettoriale.
Ma cosa sono le carte vettoriali? Sono una sorta di cornice composta da punti, polilinee e poligoni.
In realtà, è un database di punti e delle connessioni tra di essi.
Una delle sfide più ambiziose della mappatura è la missione di mappare la nostra galassia con il telescopio Gaia. In senso figurato, la nostra galassia, così come l'intera università, è un vasto e rarefatto array: enormi spazi vuoti in cui ci sono rare piccole punti – stelle. Lo spazio vuoto rappresenta il 99,999999…….%. Per memorizzare la mappa della nostra galassia è stato scelto un database su globals – Caché.
Non conosco la struttura esatta dei globals in questo progetto; posso supporre che sia qualcosa di simile a:
Set ^galaxy(b, l, d) = 1; Numero della stella nel catalogo, se presente
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 consente di mantenere qualsiasi caratteristica necessaria delle stelle e dei pianeti, dato che le basi sui globali sono senza schema (scheme-less).
La scelta di Caché per memorizzare la mappa del nostro universo si basa non solo sulla flessibilità, ma anche sulla capacità di memorizzare rapidamente il flusso di dati, creando al contempo globali indicizzati per una ricerca veloce.
Tornando alla Terra, sono stati creati progetti cartografici sui globali e un fork di OpenStreetMap — .
Di recente, durante sono stati realizzati indici geospaziali . Attendiamo dettagli sull'implementazione dagli autori dell'articolo.
Implementazione degli indici spaziali nel globale di OpenStreetMap XAPI
Le immagini sono tratte da .
L'intero globo terrestre è suddiviso in quadrati, poi in sottoquadrati, e i sottoquadrati in sotto-sottoquadrati, 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 necessario o eliminarlo, e tutti i sottoquadrati verranno restituiti o eliminati.
Tale schema sui globali può essere realizzato in diversi modi.
Opzione 1:
Imposta ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idPrimoPunto
Imposta ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idSecondoPunto
...Opzione 2:
Imposta ^m('abacdabcdabacdabcda', 1) = idPrimoPunto
Imposta ^m('abacdabcdabacdabcda', 2) = idSecondoPunto
...In entrambi i casi, non è difficile su COS/M richiedere punti situati all'interno di un quadrato di qualsiasi livello. Sarà leggermente più semplice pulire pezzi quadrati di spazio di qualsiasi livello nella prima opzione, ma è raro che ciò sia necessario.
Ecco un esempio di uno dei quadratini di livello inferiore:
Ecco alcuni globali del progetto XAPI: presentazione dell'indice sui globali:
Globale ^way è utilizzato per memorizzare punti (strade, fiumi minori, ecc.) e poligoni (aree delimitate: edifici, boschi, ecc.).
Una classificazione grossolana dell'uso di array sparsi sui globali.
- Memorizziamo le coordinate di alcuni oggetti e i loro stati (mappatura, automi cellulari)
- Memorizziamo matrici sparse.
Nel caso 2), quando si richiede una certa coordinata, dove all'elemento non è stato assegnato un valore, dobbiamo ottenere il valore dell'elemento dell'array sparso per impostazione predefinita.
I bonus che otteniamo memorizzando matrici multidimensionali sui globali
Eliminazione rapida e/o estrazione di pezzi di spazio, multipli di righe, piani, cubi, ecc. Nei casi in cui si utilizzano indici interi, può risultare utile la possibilità di eliminazione rapida e/o estrazione di pezzi di spazio, multipli di righe, piani, cubi, ecc.
Con il comando Possiamo eliminare sia un singolo elemento che una riga, e persino un'intera faccia. Grazie alle proprietà globali, questo avviene molto rapidamente — migliaia di volte più veloce dell'eliminazione elemento per elemento.
L'immagine mostra un array tridimensionale nella globale ^a e diversi tipi di eliminazione.
Per estrarre pezzi di spazio in base a indici noti, è possibile utilizzare il comando .
Estrazione di una colonna della matrice nella variabile Column:
; Definiamo un array sparso 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
Risultato:
Column(0)=1
Column(2)=1
È interessante notare che nella variabile Column abbiamo anche ottenuto un array sparso, a cui dobbiamo accedere anch'esso tramite , poiché i valori predefiniti non sono memorizzati in esso.
L'estrazione di pezzi di spazio può avvenire anche attraverso un piccolo programma utilizzando la funzione . È particolarmente utile in spazi i cui indici non sono quantizzati (cartografia).
Conclusione
I tempi attuali pongono nuove sfide ambiziose. I grafi possono consistere in miliardi di nodi, le mappe in miliardi di punti, e qualcuno potrebbe addirittura 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 deve comunque essere elaborato, è opportuno considerare l'implementazione di progetti simili su globali e COS.
Grazie per l'attenzione! Attendiamo le vostre domande e commenti.
Avvertenza: Questo articolo e i miei commenti sono solo il mio punto di vista e non rappresentano la posizione ufficiale della corporation InterSystems.
Fonte: habr.com
