Nelle parti precedenti (, ) abbiamo parlato dei globali come alberi, in questo vedremo i globali come array sparsi.
è un tipo di array in cui la maggior parte dei valori assume lo stesso valore.
In pratica, gli array sparsi sono spesso così grandi che non ha senso occupare la memoria con elementi identici. Pertanto, ha senso implementare array sparsi in modo tale che la memoria non venga sprecata memorizzando valori identici.
In alcuni linguaggi di programmazione, gli array sparsi sono inclusi nel linguaggio stesso, , . Altri linguaggi di programmazione dispongono di librerie speciali che consentono di implementarli. Per C++- др и.
I globali sono buoni candidati per l'implementazione di array sparsi perché:
- Memorizzano i valori solo di determinati nodi e non memorizzano i valori di quelli indefiniti;
- L'interfaccia per accedere al valore di un nodo è estremamente simile a quanti linguaggi di programmazione implementano l'accesso ad un elemento di array multidimensionale.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global è una struttura di archiviazione dei dati di livello piuttosto basso, quindi ha caratteristiche di velocità eccezionali (da centinaia di migliaia a decine di milioni di transazioni al secondo, a seconda dell'hardware, vedi sotto). )
Poiché la struttura globale è persistente, ha senso creare array sparsi su di essi quando si sa in anticipo che la quantità di RAM non sarà sufficiente.
Una delle proprietà delle implementazioni di array sparsi è quella di restituire un valore predefinito se viene effettuato un accesso a una cella non definita.
Questo può essere implementato utilizzando la funzione nel COS. Questo esempio considera un array tridimensionale.
SET a = $GET(^a(x,y,z), defValue)Quali attività richiedono array sparsi e in che modo i globali possono essere d'aiuto?
Matrice di adiacenza (connettività).
utilizzato per rappresentare i grafici:
Ovviamente più grande è il grafico, più zeri ci saranno nella matrice. Se, ad esempio, prendiamo il grafico di un social network e lo presentiamo sotto forma di una matrice simile, sarà quasi interamente costituito da zeri, ad es. 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, risparmiamo a livello globale ^m matrice di connettività, nonché il numero di archi in ciascun nodo (chi è amico di chi e il numero di amici).
Se il numero di elementi nel grafico non è superiore a 29 milioni (questo numero è considerato il prodotto di 8 * ), cioè un modo ancora più economico per memorizzare tali matrici sono le stringhe di bit, poiché la loro implementazione ottimizza in modo speciale grandi lacune.
Le manipolazioni con stringhe di bit vengono eseguite dalla funzione .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabella di transizione della macchina a stati
Poiché il grafo di transizione di un automa finito è un grafo ordinario, la tabella di transizione dell'automa finito è la stessa matrice di adiacenza discussa sopra.
Automi cellulari
L'automa cellulare più famoso è , che, a causa delle sue regole (quando una cella ha molti vicini, muore) è un array sparso.
Stephen Wolfram ritiene che gli automi cellulari lo siano . Nel 2002 ha pubblicato un libro di 1280 pagine, A New Kind of Science, in cui sostiene ampiamente che i progressi negli automi cellulari non sono isolati, ma sono duraturi e hanno grandi implicazioni per tutte le aree della scienza.
È stato dimostrato che qualsiasi algoritmo eseguibile su un computer può essere implementato utilizzando 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 di un automa cellulare, allora ha senso utilizzare i globali.
Cartografia
La prima cosa che mi viene in mente quando si tratta di utilizzare array sparsi è la mappatura delle attività.
Di norma, c'è molto spazio vuoto sulle mappe. Se la mappa viene rappresentata come pixel di grandi dimensioni, il 71% dei pixel della Terra sarà occupato dall'oceano. Matrice sparsa. E se applichi solo opere di mani umane, lo spazio vuoto sarà superiore al 95%.
Naturalmente nessuno memorizza le mappe sotto forma di array raster; viene utilizzata una rappresentazione vettoriale.
Ma cosa sono le mappe vettoriali? Questa è una sorta di cornice e polilinee e poligoni costituiti da punti.
Essenzialmente un database di punti e connessioni tra loro.
Una delle missioni di mappatura più ambiziose è la missione del Gaia Telescope per mappare la nostra galassia. In senso figurato, la nostra galassia, come l'intero universo, è una schiera continua e sparsa: enormi spazi vuoti in cui ci sono rari piccoli punti: le stelle. Lo spazio vuoto è 99,999999…….%. Per archiviare la mappa della nostra galassia è stato scelto un database globale: Caché.
Non conosco l'esatta struttura dei globali in questo progetto, posso supporre che sia qualcosa di simile a:
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
...
Dove sono b, l, d e la distanza dal sole.
La struttura flessibile delle globali ti consente di salvare tutte le caratteristiche necessarie di stelle e pianeti, poiché le basi delle globali sono prive di schema.
Per archiviare la mappa del nostro universo, Caché è stato scelto non solo per la sua flessibilità, ma anche per la sua capacità di archiviare un flusso di dati molto rapidamente, creando contemporaneamente indici globali per ricerche veloci.
Se torniamo sulla Terra, i progetti cartografici sono stati creati sui globali e un fork di OpenStreetMap - .
Di recente in onda sono stati implementati gli indici geospaziali . Stiamo aspettando un articolo dagli autori con i dettagli di implementazione.
Implementazione degli indici spaziali su scala globale in OpenStreetMap XAPI
Immagini tratte da .
L'intero globo è diviso in quadrati, poi sottoquadrati, i sottoquadrati in sottosottoquadrati e così via. In generale, otteniamo una struttura gerarchica per memorizzare quali globali vengono creati.
In qualsiasi momento, possiamo richiedere quasi istantaneamente la casella desiderata o cancellarla, e anche tutti i sottoquadrati verranno restituiti o cancellati.
Uno schema simile sui globali può essere implementato 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) = 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 entrambi i casi non è difficile utilizzare COS/M per richiedere punti situati in una piazza di qualsiasi livello. Nella prima opzione sarà un po' più semplice pulire pezzi quadrati di spazio a qualsiasi livello, ma questo è raramente necessario.
Un esempio di uno dei quadrati di livello inferiore:
Ed ecco diversi globali del progetto XAPI: rappresentazione di un indice sui globali:
globale ^modo utilizzato per memorizzare punti (strade, piccoli fiumi, ecc.) e poligoni (aree chiuse: edifici, foreste, ecc.).
Classificazione approssimativa dell'uso di array sparsi su globali.
- Memorizziamo le coordinate di determinati oggetti e i loro stati (mappatura, automi cellulari)
- Memorizziamo matrici sparse.
Per il caso 2) quando si richiede una coordinata specifica in cui all'elemento non viene assegnato un valore, dobbiamo ottenere il valore dell'elemento predefinito dell'array sparso.
Bonus che riceviamo quando memorizziamo matrici multidimensionali in globali
Rimuovi e/o seleziona rapidamente pezzi di spazio che sono multipli di righe, piani, cubi, ecc. Per i casi in cui vengono utilizzati indici interi, può essere utile la possibilità di rimuovere e/o recuperare rapidamente porzioni di spazio che sono multipli di righe, piani, cubi, ecc.
squadra possiamo eliminare un singolo elemento, una riga o addirittura un intero piano. Grazie alle proprietà dei globali, ciò avviene molto rapidamente, migliaia di volte più velocemente della rimozione elemento per elemento.
La figura mostra un array tridimensionale in un globale ^a e diversi tipi di eliminazioni.
Per selezionare porzioni di spazio utilizzando indici conosciuti, è possibile utilizzare il comando .
Selezionando una colonna della matrice nella variabile 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
Conclusione:
Column(0)=1
Column(2)=1
La cosa interessante della variabile Column è che abbiamo anche un array sparso, a cui è necessario accedere , poiché i valori predefiniti non sono memorizzati al suo interno.
La selezione degli spazi può essere effettuata anche tramite un piccolo programma utilizzando la funzione . Ciò è particolarmente conveniente per gli spazi i cui indici non sono quantizzati (cartografia).
conclusione
I tempi attuali pongono nuovi compiti ambiziosi. I grafici possono essere costituiti da miliardi di vertici, le mappe costituite da miliardi di punti e alcuni potrebbero persino voler gestire il proprio universo su automi cellulari (, ).
Quando il volume dei dati provenienti da array sparsi non può più rientrare nella RAM, ma è necessario lavorare con essi, vale la pena considerare la possibilità di implementare progetti simili su globali e COS.
Grazie per l'attenzione! Aspettiamo le vostre domande e desideri nei commenti.
Negazione di responsabilità: Questo articolo e i miei commenti rappresentano la mia opinione e non hanno alcuna relazione con la posizione ufficiale di InterSystems Corporation.
Fonte: habr.com