Globale — Speichermedien für Daten. Sparse Arrays. Teil 3

In den vorherigen Teilen (1, 2) haben wir Globals als Bäume betrachtet, in diesem Teil betrachten wir Globals als spärliche Arrays.

Spärliches Array ist eine Form von Array, bei der die meisten Werte gleich sind.

In der Praxis sind oft so große spärliche Arrays anzutreffen, dass es keinen Sinn macht, Speicher mit identischen Elementen zu belegen. Daher ist es sinnvoll, spärliche Arrays so zu realisieren, dass Speicher nicht für die Speicherung identischer Werte verwendet wird.
In einigen Programmiersprachen sind spärliche Arrays Teil der Sprache, zum Beispiel in J, MATLAB. In anderen Programmiersprachen gibt es spezielle Bibliotheken, die deren Implementierung ermöglichen. Für C++ - Eigen usw.

Globals sind gute Kandidaten für die Implementierung spärlicher Arrays, weil:

1. Sie Werte nur von bestimmten Knoten speichern und keine Werte von unbestimmten speichern;
2. Die Schnittstelle zum Zugriff auf den Wert eines Knotens ähnelt stark dem, wie in vielen Programmiersprachen der Zugriff auf ein Element eines mehrdimensionalen Arrays realisiert ist.

   Set ^a(1, 2, 3)=5
   Write ^a(1, 2, 3)

3. Globals sind eine eher niedrigschwellige Struktur zur Datenspeicherung und bieten daher hervorragende Geschwindigkeitsmerkmale (von Hunderttausenden bis zu Millionen von Transaktionen pro Sekunde, abhängig von der Hardware, siehe auch. 1)

Da Globals persistente Strukturen sind, ist es sinnvoll, spärliche Arrays nur dann zu verwenden, wenn von vornherein feststeht, dass der verfügbare Arbeitsspeicher nicht ausreicht.

Eines der Merkmale der Implementierungen spärlicher Arrays ist die Rückgabe eines Standardwerts, wenn auf eine nicht definierte Zelle zugegriffen wird.

Dies kann durch die Verwendung der Funktion $GET in COS realisiert werden. In diesem Beispiel betrachten wir ein dreidimensionales Array.

SET a = $GET(^a(x,y,z), defValue)

In welchen Situationen werden spärliche Arrays benötigt, und wie können Globals helfen?

Die Adjazenzmatrix (Verbindungsmatrix)

Solche Matrizen werden zur Darstellung von Graphen verwendet:

Es ist offensichtlich, dass je größer der Graph ist, desto mehr Nullen in der Matrix vorkommen werden. Wenn man beispielsweise ein Netzwerkgraph einer sozialen Plattform nimmt und diesen in Form einer solchen Matrix darstellt, besteht er fast vollständig aus Nullen, d.h. er wird zu einem spärlichen Array.

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 diesem Beispiel speichern wir global ^m die Nachbarmatrix sowie die Anzahl der Kanten für jeden Knoten (wer mit wem befreundet ist und die Anzahl der Freunde).

Wenn die Anzahl der Elemente im Graphen nicht mehr als 29 Millionen beträgt (diese Zahl ergibt sich aus dem Produkt von 8 * maximale Zeilenlänge), gibt es einen noch wirtschaftlicheren Weg zur Speicherung solcher Matrizen – Bit-Strings, da hier große Lücken auf spezielle Weise optimiert werden.

Manipulationen mit Bit-Strings werden durch die Funktion $BIT.

; Bit setzen
SET $BIT(rowID, positionID) = 1
; Bit abfragen
Write $BIT(rowID, positionID)

Übergangstabelle des endlichen Automaten

Da der Übergangsgraph eines endlichen Automaten ein gewöhnlicher Graph ist, ist auch die Übergangstabelle des endlichen Automaten dieselbe Nachbarmatrix, die oben erwähnt wurde.

Zellulare Automaten

Der bekannteste zellulare Automat ist das Spiel 'Life', das aufgrund seiner Regeln (wenn eine Zelle viele Nachbarn hat, stirbt sie) ein spärliches Array darstellt.

Stephen Wolfram ist der Meinung, dass zellulare Automaten ein neues Wissenschaftsgebiet darstellen.. Im Jahr 2002 veröffentlicht er das 1280-seitige Buch „A New Kind of Science“, in dem er umfassend argumentiert, dass Fortschritte im Bereich der zellulären Automaten nicht isoliert sind, sondern sehr stabil und von großer Bedeutung für alle wissenschaftlichen Disziplinen.

Es hat sich gezeigt, dass jeder auf einem Computer ausführbare Algorithmus durch einen zellulären Automaten realisiert werden kann. Zelluläre Automaten werden verwendet, um dynamische Umgebungen und Systeme zu modellieren, algorithmische Probleme zu lösen und andere Zwecke zu verfolgen.

Wenn wir ein riesiges Feld haben und alle Zwischenzustände des zellulären Automaten aufzeichnen müssen, ist es durchaus sinnvoll, globale Variablen zu verwenden.

Kartographie

Das Erste, was mir in den Sinn kommt, wenn es um die Verwendung von spärlichen Arrays geht, sind kartographische Aufgaben.

Auf Karten gibt es normalerweise sehr viel leeren Raum. Wenn man eine Karte als große Pixel darstellt, wären 71 % der Pixel der Erde vom Ozean belegt. Ein spärliches Array. Und wenn man nur von menschlicher Hand geschaffene Werke einträgt, bleibt mehr als 95 % leerer Raum.

Natürlich werden Karten nicht als Rasterdaten gespeichert, sondern in einer vektoriellen Darstellung.
Aber was sind vektorbasierte Karten? Sie bestehen aus Linienzügen und Polygonen, die aus Punkten bestehen.
Im Grunde genommen handelt es sich um eine Datenbank von Punkten und den Verbindungen zwischen ihnen.

Eine der ehrgeizigsten Kartierungsaufgaben ist die Kartierung unserer Galaxie mit dem Gaia-Teleskop. Bildlich gesprochen ist unsere Galaxie, wie das gesamte Universum, ein durchgehendes, dünn besiedeltes Array: riesige Leere mit seltenen kleinen Punkten – Sterne. Der leere Raum macht 99,999999……. % aus. Für die Speicherung der Karte unserer Galaxie wurde eine globale Datenbank – Caché – gewählt.

Ich kenne die genaue Struktur der Globals in diesem Projekt nicht, ich kann mir aber vorstellen, dass sie ähnlich wie folgt aussieht:

Set ^galaxy(b, l, d) = 1; Sternnummer im Katalog, falls vorhanden
Set ^galaxy(b, l, d, "name") = "Sonne"
Set ^galaxy(b, l, d, "type") = "normal"; Optionen: blackhole, quazar, red_dwarf usw.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Merkur"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...

Wo b, l, d - das sind galaktische Koordinaten: Breite, Länge und der Abstand zur Sonne.

Die flexible Struktur der Globals ermöglicht es, alle benötigten Eigenschaften von Sternen und Planeten zu speichern, da die Datenbanken auf den Globals schemalos sind.

Für die Speicherung der Karte unseres Universums wurde Caché nicht nur wegen ihrer Flexibilität ausgewählt, sondern auch wegen der Fähigkeit, Datenströme sehr schnell zu speichern, während gleichzeitig indexierte Globals für eine schnelle Suche erstellt werden.

Wenn wir zur Erde zurückkehren, wurden auf den Globals kartografische Projekte erstellt. OpenStreetMap XAPI und ein Fork von OpenStreetMap — FOSM.

Kürzlich beim Hackathon Caché wurden geospatial Indizes umgesetzt. Geospatial. Wir erwarten von den Autoren des Artikels Details zur Implementierung.

Die Implementierung von räumlichen Indizes auf dem Global in OpenStreetMap XAPI

Die Bilder stammen von dieser Präsentation.

Der gesamte Erdball wird in Quadrate unterteilt, dann in Unterquadrate, und die Unterquadrate in weitere Unterquadrate usw. Insgesamt erhalten wir eine hierarchische Struktur, für deren Speicherung Globals geschaffen wurden.

Zu jedem Zeitpunkt können wir fast sofort das benötigte Quadrat anfordern oder es löschen, wobei alle Unterquadrate ebenfalls zurückgegeben oder gelöscht werden.

Ein ähnliches Schema auf den Globals kann auf verschiedene Weise umgesetzt werden.

Variante 1:

Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idErsterPunkt
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idZweiterPunkt
...

Variante 2:

Set ^m('abacdabcdabacdabcda', 1) = idErsterPunkt
Set ^m('abacdabcdabacdabcda', 2) = idZweiterPunkt
...

In beiden Fällen ist es einfach, auf COS/M Punkte zu fordern, die sich in einem Quadrat beliebigen Niveaus befinden. Es wird etwas einfacher sein, quadratische Raumstücke beliebigen Niveaus im ersten Fall zu bereinigen, aber das ist selten notwendig.

Beispiel eines der kleineren Quadrate:

Hier sind einige Globals aus dem Projekt XAPI: Darstellung des Indexes in Globals:

Global ^way wird zur Speicherung von Punkten verwendet Polyline (Straßen, kleine Flüsse usw.) und Polygonen (geschlossene Bereiche: Gebäude, Wälder usw.).

Grobe Klassifizierung der Nutzung von spärlichen Arrays in Globals.

1. Wir speichern die Koordinaten bestimmter Objekte und deren Zustand (Mapping, zellulare Automaten)
2. Wir speichern spärliche Matrizen.

Für den Fall 2) bei der Abfrage einer bestimmten Koordinate, wo dem Element kein Wert zugewiesen ist, müssen wir den Standardwert des Elements des spärlichen Arrays erhalten.

Vorteile, die wir erhalten, wenn wir mehrdimensionale Matrizen in Globals speichern.

Schnelles Entfernen und/oder Abfragen von Raumabschnitten, die Vielfache von Zeilen, Ebenen, Würfeln usw. sind. Für Fälle, in denen Ganzzahlindizes verwendet werden, kann es nützlich sein, die Möglichkeit des schnellen Entfernens und/oder Abfragens von Raumabschnitten, die Vielfache von Zeilen, Ebenen, Würfeln usw. sind, zu haben.

Mit dem Befehl Beenden Wir können sowohl ein einzelnes Element als auch eine Zeile und sogar eine ganze Ebene entfernen. Dank der Eigenschaften der Globalen geschieht dies sehr schnell – Tausende Male schneller als elementweises Entfernen.

Die Abbildung zeigt ein dreidimensionales Array in einer Globalen ^a und verschiedene Arten des Entfernens.

Für das Abfragen von Raumabschnitten anhand bekannter Indizes kann der Befehl verwendet werden Zusammenführen.

Abfrage einer Spalte der Matrix in die Variable Column:

; Wir definieren ein dreidimensionales spärliches Array 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)
; Lassen Sie uns die Variable Column ausgeben
Zwrite Column

Fazit:

Column(0)=1
Column(2)=1

Interessanterweise ist die Variable Column ebenfalls ein spärliches Array, auf das ebenfalls über zugreifen werden muss $GET, da die Standardwerte nicht darin gespeichert sind.

Das Abfragen von Raumabschnitten kann auch durch ein kleines Programm unter Verwendung der Funktion erfolgen $Order. Dies ist insbesondere praktisch in Bereichen, deren Indizes nicht quantifiziert sind (Kartografie).

Fazit

Die heutigen Zeiten stellen neue, ehrgeizige Herausforderungen. Graphen können aus Milliarden von Knoten bestehen, Karten aus Milliarden von Punkten, und es gibt sogar Personen, die ihre eigene Universum auf zellulären Automaten starten möchten (1, 2).

Wenn das Volumen von sparse Arrays nicht mehr im Arbeitsspeicher untergebracht werden kann und dennoch damit gearbeitet werden muss, lohnt es sich, die Möglichkeit zu prüfen, solche Projekte auf Globals und COS zu realisieren.

Vielen Dank für Ihre Aufmerksamkeit! Wir freuen uns auf Ihre Fragen und Anregungen in den Kommentaren.

Haftungsausschluss: Dieser Artikel und meine Kommentare dazu spiegeln meine persönliche Meinung wider und stehen nicht im Zusammenhang mit der offiziellen Position der InterSystems Corporation.

Quelle: habr.com