In den vorherigen Teilen (, ) haben wir über Globals als Bäume gesprochen, in diesem Fall werden wir Globals als spärliche Arrays betrachten.
ist ein Array-Typ, in dem die meisten Werte denselben Wert annehmen.
In der Praxis sind Sparse-Arrays oft so groß, dass es keinen Sinn macht, den Speicher mit identischen Elementen zu belegen. Daher ist es sinnvoll, Sparse-Arrays so zu implementieren, dass kein Speicher für die Speicherung identischer Werte verschwendet wird.
In einigen Programmiersprachen sind Sparse-Arrays in der Sprache selbst enthalten. , . Andere Programmiersprachen verfügen über spezielle Bibliotheken, mit denen Sie sie implementieren können. Für C++ - usw.
Globale sind aus folgenden Gründen gute Kandidaten für die Implementierung von Sparse-Arrays:
- Sie speichern nur die Werte bestimmter Knoten und nicht die Werte undefinierter Knoten.
- Die Schnittstelle für den Zugriff auf den Wert eines Knotens ist der Art und Weise, wie viele Programmiersprachen den Zugriff auf ein mehrdimensionales Array-Element implementieren, sehr ähnlich.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global ist eine Struktur auf relativ niedriger Ebene zum Speichern von Daten und weist daher hervorragende Geschwindigkeitseigenschaften auf (von Hunderttausenden bis zu mehreren zehn Millionen Transaktionen pro Sekunde, abhängig von der Hardware, siehe unten). )
Da es sich bei Global um eine persistente Struktur handelt, ist es sinnvoll, darauf Sparse-Arrays zu erstellen, wenn im Voraus bekannt ist, dass die Menge an RAM nicht ausreicht.
Eine der Eigenschaften von Sparse-Array-Implementierungen besteht darin, einen Standardwert zurückzugeben, wenn auf eine undefinierte Zelle zugegriffen wird.
Dies kann über die Funktion umgesetzt werden in COS. In diesem Beispiel wird ein dreidimensionales Array betrachtet.
SET a = $GET(^a(x,y,z), defValue)Für welche Aufgaben sind spärliche Arrays erforderlich und wie können Globals hilfreich sein?
Adjazenzmatrix (Konnektivitätsmatrix).
Wird zur Darstellung von Diagrammen verwendet:
Je größer der Graph ist, desto mehr Nullen enthält die Matrix. Wenn wir zum Beispiel ein Diagramm eines sozialen Netzwerks nehmen und es in Form einer ähnlichen Matrix darstellen, dann wird es fast ausschließlich aus Nullen bestehen, d. h. wird ein spärliches Array sein.
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 Konnektivitätsmatrix sowie die Anzahl der Kanten an jedem Knoten (wer ist mit wem befreundet und wie viele Freunde).
Wenn die Anzahl der Elemente im Diagramm nicht mehr als 29 Millionen beträgt (diese Zahl wird als Produkt von 8 * angenommen) ), das heißt, eine noch wirtschaftlichere Möglichkeit, solche Matrizen zu speichern, sind Bitfolgen, da deren Implementierung große Lücken auf besondere Weise optimiert.
Manipulationen mit Bitfolgen werden von der Funktion durchgeführt .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Zustandsautomaten-Übergangstabelle
Da der Übergangsgraph eines endlichen Automaten ein gewöhnlicher Graph ist, ist die Übergangstabelle des endlichen Automaten dieselbe Adjazenzmatrix, die oben diskutiert wurde.
Zellulare Automaten
Der bekannteste zelluläre Automat ist , das aufgrund seiner Regeln (wenn eine Zelle viele Nachbarn hat, stirbt sie) ein spärliches Array ist.
Stephen Wolfram glaubt, dass es zelluläre Automaten gibt . Im Jahr 2002 veröffentlichte er ein 1280 Seiten umfassendes Buch mit dem Titel „A New Kind of Science“, in dem er allgemein argumentiert, dass Fortschritte bei zellulären Automaten nicht isoliert, sondern dauerhaft sind und große Auswirkungen auf alle Bereiche der Wissenschaft haben.
Es ist erwiesen, dass jeder auf einem Computer ausführbare Algorithmus mithilfe eines zellularen Automaten implementiert werden kann. Zellulare Automaten werden zur Modellierung dynamischer Umgebungen und Systeme, zur Lösung algorithmischer Probleme und für andere Zwecke verwendet.
Wenn wir ein riesiges Feld haben und alle Zwischenzustände eines zellularen Automaten aufzeichnen müssen, dann ist es sinnvoll, Globale zu verwenden.
Kartographie
Das erste, was mir bei der Verwendung von Arrays mit geringer Dichte in den Sinn kommt, sind Mapping-Aufgaben.
In der Regel gibt es auf Karten viel Leerraum. Wenn die Karte als große Pixel dargestellt wird, werden 71 % der Pixel der Erde vom Ozean eingenommen. Sparse-Array. Und wenn Sie nur Werke von Menschenhand verwenden, beträgt der Leerraum mehr als 95 %.
Natürlich speichert niemand Karten in Form von Rasterarrays, es wird eine Vektordarstellung verwendet.
Aber was sind Vektorkarten? Dies ist eine Art Rahmen sowie Polylinien und Polygone, die aus Punkten bestehen.
Im Wesentlichen eine Datenbank mit Punkten und Verbindungen zwischen ihnen.
Eine der ehrgeizigsten Kartierungsmissionen ist die Gaia-Teleskop-Mission zur Kartierung unserer Galaxie. Im übertragenen Sinne ist unsere Galaxie, wie das gesamte Universum, eine kontinuierliche, spärliche Ansammlung: riesige Räume der Leere, in denen es seltene kleine Punkte gibt – Sterne. Der Leerraum beträgt 99,999999…….%. Um die Karte unserer Galaxie zu speichern, wurde eine globale Datenbank gewählt – Caché.
Ich kenne die genaue Struktur der Globals in diesem Projekt nicht, ich kann jedoch davon ausgehen, dass es sich um etwas Ähnliches handelt:
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
...
Wo b, l, d sind und Entfernung zur Sonne.
Die flexible Struktur von Globals ermöglicht es Ihnen, alle notwendigen Eigenschaften von Sternen und Planeten zu speichern, da die Grundlagen von Globals schemalos sind.
Um die Karte unseres Universums zu speichern, wurde Caché nicht nur wegen seiner Flexibilität ausgewählt, sondern auch wegen seiner Fähigkeit, einen Datenstrom sehr schnell zu speichern und gleichzeitig globale Indexe für schnelle Suchvorgänge zu erstellen.
Wenn wir zur Erde zurückkehren, dann wurden kartografische Projekte auf Globals erstellt und ein Fork von OpenStreetMap - .
Kürzlich auf Geoindizes wurden implementiert . Wir warten auf einen Artikel der Autoren mit Details zur Implementierung.
Implementierung räumlicher Indizes auf einem globalen in OpenStreetMap XAPI
Bilder aufgenommen von .
Der gesamte Globus ist in Quadrate unterteilt, dann in Unterquadrate, und Unterquadrate in Unterunterquadrate und so weiter. Im Allgemeinen erhalten wir eine hierarchische Struktur zum Speichern der erstellten Globals.
Wir können das gewünschte Quadrat jederzeit fast sofort anfordern oder räumen, und alle Unterquadrate werden ebenfalls zurückgegeben oder geräumt.
Ein ähnliches Schema für 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) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...Option 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...In beiden Fällen ist es nicht schwierig, mit COS/M Punkte anzufordern, die sich in einem Quadrat beliebiger Ebene befinden. Mit der ersten Option ist es etwas einfacher, quadratische Flächen auf jeder Ebene zu reinigen, dies ist jedoch selten erforderlich.
Ein Beispiel für eines der Quadrate der unteren Ebene:
Und hier sind einige Globals aus dem XAPI-Projekt: Darstellung eines Indexes zu Globals:
global ^Weg Wird zum Speichern von Punkten verwendet (Straßen, kleine Flüsse usw.) und Polygone (geschlossene Gebiete: Gebäude, Wälder usw.).
Grobe Klassifizierung der Verwendung von Sparse-Arrays auf Globals.
- Wir speichern die Koordinaten bestimmter Objekte und deren Zustände (Mapping, zellulare Automaten)
- Wir speichern dünn besetzte Matrizen.
Für Fall 2) müssen wir bei der Anforderung einer bestimmten Koordinate, bei der dem Element kein Wert zugewiesen ist, den Wert des standardmäßigen Sparse-Array-Elements abrufen.
Boni, die wir erhalten, wenn wir mehrdimensionale Matrizen in Globals speichern
Entfernen und/oder wählen Sie schnell Raumstücke aus, die aus mehreren Reihen, Ebenen, Würfeln usw. bestehen. In Fällen, in denen ganzzahlige Indizes verwendet werden, kann die Möglichkeit nützlich sein, schnell Raumblöcke zu entfernen und/oder abzurufen, die ein Vielfaches von Zeilen, Ebenen, Würfeln usw. sind.
Team Wir können entweder ein einzelnes Element oder eine Reihe oder sogar eine ganze Ebene löschen. Dank der Eigenschaften von Globals geschieht dies sehr schnell – tausende Male schneller als die Element-für-Element-Entfernung.
Die Abbildung zeigt ein dreidimensionales Array in einem globalen ^a und verschiedene Arten von Löschungen.
Um mithilfe bekannter Indizes Bereiche auszuwählen, können Sie den Befehl verwenden .
Auswählen einer Matrixspalte in der Spaltenvariablen:
; Зададим трёхмерный разреженный массив 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
Fazit:
Column(0)=1
Column(2)=1
Das Interessante an der Column-Variablen ist, dass wir auch ein Sparse-Array haben, auf das ebenfalls zugegriffen werden muss , da darin keine Standardwerte gespeichert sind.
Die Auswahl von Raumstücken kann mit der Funktion auch über ein kleines Programm erfolgen . Dies ist besonders praktisch bei Räumen, deren Indizes nicht quantisiert sind (Kartographie).
Abschluss
Die aktuelle Zeit stellt uns vor neue anspruchsvolle Aufgaben. Graphen können aus Milliarden von Eckpunkten bestehen, Karten aus Milliarden von Punkten, und manche möchten vielleicht sogar ihr eigenes Universum auf zellularen Automaten betreiben (, ).
Wenn die Datenmenge aus Sparse-Arrays nicht mehr in den RAM passt, Sie aber damit arbeiten müssen, lohnt es sich, über die Möglichkeit nachzudenken, ähnliche Projekte auf Globals und COS umzusetzen.
Vielen Dank für Ihre Aufmerksamkeit! Wir warten auf Ihre Fragen und Wünsche in den Kommentaren.
Haftungsausschluss: Dieser Artikel und meine Kommentare dazu stellen meine Meinung dar und stehen in keinem Zusammenhang mit der offiziellen Position der InterSystems Corporation.
Source: habr.com