In den vorherigen Teilen (, ) haben wir über globale Variablen als Bäume gesprochen, in diesem Teil betrachten wir globale Variablen als spärliche Arrays.
ist eine Art von Array, bei dem die meisten Werte denselben Wert annehmen.
In der Praxis treffen wir oft auf so massive spärliche Arrays, dass es keinen Sinn macht, den Speicher mit identischen Elementen zu belegen. Daher ist es sinnvoll, spärliche Arrays so zu implementieren, dass kein Speicher für die Speicherung identischer Werte verschwendet wird.
In einigen Programmiersprachen sind spärliche Arrays Teil der Sprache, , . In anderen Programmiersprachen gibt es spezielle Bibliotheken, die es ermöglichen, sie zu implementieren. Für C++ — usw.
Globale Variablen sind gute Kandidaten für die Implementierung spärlicher Arrays, weil:
- Sie speichern Werte nur für bestimmte Knoten und speichern keine Werte für undefinierte;
- Die Schnittstelle zum Zugriff auf den Wert eines Knotens ähnelt stark der Art und Weise, wie in vielen Programmiersprachen der Zugriff auf ein Element eines mehrdimensionalen Arrays implementiert ist.
Setze ^a(1, 2, 3)=5 Schreibe ^a(1, 2, 3) - Global ist eine ausreichend low-level Struktur zur Speicherung von Daten, daher hat sie bemerkenswerte Geschwindigkeitsmerkmale (von Hunderttausenden bis zu Millionen von Transaktionen pro Sekunde, abhängig von der Hardware, siehe. )
Da eine globale Variable eine persistente Struktur ist, ist es sinnvoll, spärliche Arrays auf ihnen zu machen, wenn im Voraus bekannt ist, dass der Speicher nicht ausreichen wird.
Eine der Eigenschaften der Implementierungen spärlicher Arrays ist die Rückgabe eines bestimmten Standardwertes, wenn auf eine undefinierte Zelle zugegriffen wird.
Dies kann durch die Verwendung der Funktion in COS realisiert werden. In diesem Beispiel wird ein dreidimensionales Array betrachtet.
SET a = $GET(^a(x,y,z), defValue)In welchen Aufgaben sind spärliche Arrays erforderlich und wie können globale Variablen helfen?
Nachbarschaftsmatrix (Konnektivität)
werden verwendet, um Graphen darzustellen:
Offensichtlich gilt, je größer der Graph, desto mehr Nullen werden in der Matrix vorhanden sein. Wenn man zum Beispiel ein Netzwerk-Graf und ihn in einer solchen Matrix darstellt, wird er fast ausschließlich aus Nullen bestehen, d.h. er ist ein spärliches Array.
Setze ^m(id1, id2) = 1
Setze ^m(id1, id3) = 1
Setze ^m(id1, id4) = 1
Setze ^m(id1) = 3
Setze ^m(id2, id4) = 1
Setze ^m(id2, id5) = 1
Setze ^m(id2) = 2
....
In diesem Beispiel speichern wir im Globalen ^m die Verbindungs Matrix sowie die Anzahl der Kanten für jeden Knoten (wer mit wem befreundet ist und wie viele Freunde er hat).
Falls jedoch die Anzahl der Elemente im Graphen 29 Millionen nicht überschreitet (diese Zahl ergibt sich als Produkt von 8 * ), gibt es eine noch wirtschaftlichere Methode zur Speicherung solcher Matrizen — Bit-Strings, da bei ihrer Implementierung große Lücken speziell optimiert werden.
Manipulationen mit Bit-Strings erfolgen durch die Funktion .
; Bit setzen
SET $BIT(rowID, positionID) = 1
; Bit abrufen
Write $BIT(rowID, positionID)
Übergangstabelle des endlichen Automaten
Da der Übergangsgraph des endlichen Automaten ein gewöhnlicher Graph ist, ist die Übergangstabelle des endlichen Automaten dieselbe Adjazenzmatrix, die oben erwähnt wurde.
Zelluläre Automaten
Der bekannteste zelluläre Automat ist , das aufgrund seiner Regeln (wenn eine Zelle viele Nachbarn hat, stirbt sie) ein spärliches Array darstellt.
Stephen Wolfram ist der Ansicht, dass zelluläre Automaten eine sind. Im Jahr 2002 veröffentlicht er das 1280-seitige Buch 'A New Kind of Science', in dem er ausführlich argumentiert, dass Errungenschaften im Bereich der zellulären Automaten nicht isoliert sind, sondern sehr stabil und von großer Bedeutung für alle wissenschaftlichen Bereiche.
Es wurde bewiesen, dass jeder auf einem Computer ausführbare Algorithmus durch einen zellulären Automaten realisiert werden kann. Zelluläre Automaten werden zur Modellierung dynamischer Umgebungen und Systeme, zur Lösung algorithmischer Probleme und für andere Zwecke eingesetzt.
Wenn wir ein riesiges Feld haben und alle Zwischenzustände des zellulären Automaten aufzeichnen müssen, ist es durchaus sinnvoll, Globals zu verwenden.
Kartographie
Das erste, was mir in den Sinn kommt, wenn es um die Verwendung spärlicher Arrays geht, sind kartografische Aufgaben.
In der Regel gibt es auf Karten sehr viel leeren Raum. Wenn man eine Karte als große Pixel darstellt, werden 71 % der Pixel der Erde vom Ozean bedeckt. Daher ein spärliches Array. Wenn man nur die menschlichen Eingriffe darstellt, liegt der Anteil des leeren Raums sogar bei über 95 %.
Natürlich speichert niemand Karten in Form von Rasterarrays; es wird eine VektDarstellung verwendet.
Aber was sind Vektorkarten? Es handelt sich um einen Rahmen, der aus Punkten, Polylinien und Polygonen besteht.
Tatsächlich eine Datenbank von Punkten und den Beziehungen zwischen ihnen.
Eine der ehrgeizigsten Aufgaben der Kartierung ist die Mission, unsere Galaxie mit dem Gaia-Teleskop zu kartieren. Bildlich gesprochen ist unsere Galaxie, wie das gesamte Universum, ein kontinuierliches, spärliches Array: riesige Räume der Leere, in denen kleine, seltene Punkte – Sterne – existieren. Der leere Raum beträgt 99,999999…….%. Für die Speicherung der Karte unserer Galaxie wurde eine Datenbank auf Globals gewählt – Caché.
Ich kenne die genaue Struktur der Globals in diesem Projekt nicht, kann mir aber vorstellen, dass sie ähnlich ist wie:
Set ^galaxy(b, l, d) = 1; Sternnummer aus dem Katalog, falls vorhanden
Set ^galaxy(b, l, d, "name") = "Sonne"
Set ^galaxy(b, l, d, "type") = "normal" ; Varianten sind Schwarzes Loch, Quasar, Roter Zwerg 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 und Entfernung zur Sonne.
Die flexible Struktur der Globals ermöglicht es, alle erforderlichen Eigenschaften von Sternen und Planeten zu speichern, da die Datenbanken auf Globals schemalos sind.
Für die Speicherung der Karte unseres Universums wurde Caché nicht nur wegen der Flexibilität gewählt, sondern auch wegen der Fähigkeit, Datenströme sehr schnell zu speichern und dabei gleichzeitig Index-Globals für eine schnelle Suche zu erstellen.
Wenn wir zur Erde zurückkehren, wurden auf Globals Kartierungsprojekte erstellt und ein Fork von OpenStreetMap – .
Vor kurzem wurden auf einem geowissenschaftliche Indizes umgesetzt . Wir erwarten vom Autor des Artikels Details zur Umsetzung.
Implementierung räumlicher Indizes auf Globals in OpenStreetMap XAPI
Bilder stammen von .
Der gesamte Erdball wird in Quadrate unterteilt, dann in Unterquadrate, und die Unterquadrate in Unterunterquadrate und so weiter. Insgesamt erhalten wir eine hierarchische Struktur, für die Globals geschaffen wurden.
Jederzeit 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 Globals kann auf verschiedene Arten implementiert werden.
Option 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idDerErstenPunkt
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idDerZweitenPunkt
...Option 2:
Set ^m('abacdabcdabacdabcda', 1) = idErsterPunkt
Set ^m('abacdabcdabacdabcda', 2) = idZweiterPunkt
...In beiden Fällen ist es einfach, in COS/M Punkte zu fordern, die sich in einem Quadrat beliebiger Stufen befinden. Es wird etwas einfacher sein, quadratische Stücke des Raums beliebiger Stufen im ersten Fall zu reinigen, aber das ist selten nötig.
Ein Beispiel für eines der unteren Quadrat:
Hier sind einige Globals aus dem XAPI-Projekt: die Darstellung des Index in den Globals:
Global ^way wird zur Speicherung von Punkten (Straßen, kleine Flüsse usw.) und Polygonen (geschlossene Bereiche: Gebäude, Wälder usw.).
Rauhe Klassifizierung der Nutzung sporadischer Arrays in Globals.
- Wir speichern die Koordinaten bestimmter Objekte und deren Zustände (Kartierung, Zellular-Automaten)
- Wir speichern spärliche Matrizen.
Für den Fall 2) bei der Anfrage einer bestimmten Koordinate, wo dem Element kein Wert zugewiesen wurde, müssen wir den Wert des Elements des spärlichen Arrays standardmäßig erhalten.
Die Vorteile, die wir erhalten, wenn wir mehrdimensionale Matrizen in den Globals speichern
Schnelles Löschen und/oder Abrufen von Raumstücken, die Vielfache von Zeilen, Ebenen, Würfeln usw. sind. Für Fälle, in denen ganzzahlige Indizes verwendet werden, kann die Möglichkeit des schnellen Löschens und/oder Abrufens von Raumstücken, die Vielfache von Zeilen, Ebenen, Würfeln usw. sind, nützlich sein.
Befehl können wir sowohl ein einzelnes Element als auch eine Zeile und sogar eine ganze Ebene löschen. Aufgrund der Eigenschaften von Globals geschieht dies sehr schnell – Tausende Male schneller als das elementweise Löschen.
Das Bild zeigt ein dreidimensionales Array im Global ^a und verschiedene Arten des Löschens.
Um Raumstücke anhand bekannter Indizes abzufragen, kann der Befehl .
Verwendung finden. Abruf einer Spalte der Matrix in die Variable Column:
; Lasst uns ein dreidimensionales spärliches Array 3x3x3 festlegen
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)
; Geben wir die Variable Column aus
Zwrite Column
Ausgabe:
Column(0)=1
Column(2)=1
Interessanterweise haben wir in der Variable Column auch ein spärliches Array erhalten, auf das ebenfalls über , zugegriffen werden muss, da die Standardwerte darin nicht gespeichert sind.
Das Abrufen von Raumstücken kann auch über ein kleines Programm unter Verwendung der Funktion erfolgen. Dies ist besonders bequem in Räumen, deren Indizes nicht quantisiert sind (Kartografie).
Fazit
Die gegenwärtige Zeit stellt neue, ehrgeizige Aufgaben. Grafen können aus Milliarden von Knoten bestehen, Karten aus Milliarden von Punkten, und vielleicht möchte jemand sogar sein eigenes Universum auf zellulären Automaten starten (, ).
Wenn das Volumen der Daten sparsamer Arrays nicht mehr in den Arbeitsspeicher passt und man damit arbeiten muss, sollte man die Möglichkeit der Umsetzung solcher Projekte auf Globals und COS in Betracht ziehen.
Danke für Ihre Aufmerksamkeit! Wir freuen uns auf Ihre Fragen und Wünsche in den Kommentaren.
Haftungsausschluss: Dieser Artikel und meine Kommentare dazu sind meine persönliche Meinung und stehen nicht im Zusammenhang mit der offiziellen Position der InterSystems Corporation.
Quelle: habr.com
