Globals sind Schwerter zur Speicherung von Daten. Sparse-Arrays. Teil 3

    In den vorangegangenen Abschnitten ( 1 , 2 ) haben wir über Globale als Bäume gesprochen. In diesem Abschnitt werden wir Globale als spärliche Arrays betrachten.

    Ein Array mit geringer Dichte ist ein Arraytyp, in dem die meisten Werte denselben Wert annehmen.

    In der Praxis werden häufig so große, spärliche Arrays gefunden, dass es keinen Sinn macht, den Speicher mit denselben Elementen zu belegen. Daher ist es sinnvoll, spärliche Arrays zu implementieren, damit der Speicher nicht zum Speichern derselben Werte verwendet wird.
    In einigen Programmiersprachen sind spärliche Arrays in der Sprache selbst enthalten, z. B. in J , MATLAB . Andere Programmiersprachen verfügen über spezielle Bibliotheken, mit denen sie implementiert werden können. Für C ++ -Eigen et al.

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

    1. Sie speichern nur die Werte bestimmter Knoten und nicht die Werte von undefined.
    2. Die Schnittstelle für den Zugriff auf den Wert des Knotens ähnelt stark der Anzahl der Programmiersprachen, die auf das Element eines mehrdimensionalen Arrays zugreifen.

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

    3. Global ist eine eher untergeordnete Struktur zum Speichern von Daten und weist daher hervorragende Geschwindigkeitsmerkmale auf (von Hunderttausenden bis zu zehn Millionen Transaktionen pro Sekunde, abhängig von der Hardware, siehe 1 ).

    Da es sich bei der globalen Struktur um eine persistente Struktur handelt, ist es sinnvoll, spärliche Arrays zu erstellen, wenn im Voraus bekannt ist, dass die Größe des Arbeitsspeichers nicht ausreicht.

    Eine der Eigenschaften von Sparse Arrays Implementierungen ist ein Standardwert , wenn die Behandlung führt zu undefinierten Zelle zurückzukehren.

    Dies kann mit der Funktion $ GET in COS implementiert werden . In diesem Beispiel wird ein dreidimensionales Array betrachtet.

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

    In welchem ​​erfordert die Aufgabe Sparse-Arrays und wie Globals helfen kann?

    Adjacency Matrix (Konnektivität)


    Solche Matrizen werden verwendet Graphen darzustellen:



    Es ist offensichtlich, dass , je größer die Zahl, desto mehr Nullen in der Matrix sein. Wenn zum Beispiel die grafische Darstellung des sozialen Netzwerks nehmen und sie in Form einer solchen Matrix zu präsentieren, ist es fast alle Nullen bestehen wird, das heißt, 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 die Konnektivitätsmatrix im globalen ^ m sowie die Anzahl der Kanten an jedem Knoten (wer ist mit wem befreundet und die Anzahl der Freunde).

    Beträgt die Anzahl der Elemente im Graphen nicht mehr als 29 Millionen (diese Anzahl wird als das Produkt der 8-fachen maximalen Zeilengröße angenommen ), so gibt es eine noch wirtschaftlichere Möglichkeit, solche Matrizen - Bitfolgen - zu speichern, da in ihrer Implementierung große Lücken auf besondere Weise optimiert werden.

    Bitstring-Manipulationen werden von der $ BIT- Funktion durchgeführt .

    ; установка бита
    SET $BIT(rowID, positionID) = 1
    ; получение бита
    Write $BIT(rowID, positionID)
    

    Übergangstabelle der Zustandsmaschine


    Da der Übergangsgraph einer Finite-State-Maschine ein gewöhnlicher Graph ist, ist die Übergangstabelle einer Finite-State-Maschine dieselbe Adjazenzmatrix, die oben erwähnt wurde.

    Zelluläre Automaten




    Der berühmteste zellulare Automat ist das Spiel Leben , das aufgrund seiner Regeln (wenn eine Zelle viele Nachbarn hat, stirbt es) eine spärliche Anordnung ist.

    Stephen Wolfram glaubt, dass zellulare Automaten ein neues Gebiet der Wissenschaft sind . Im Jahr 2002 veröffentlichte er das 1280-seitige Buch „Eine neue Art von Wissenschaft“, in dem er ausführlich argumentiert, dass Fortschritte in zellulären Automaten nicht isoliert, sondern sehr stabil und von großer Bedeutung für alle Bereiche der Wissenschaft sind.

    Es ist bewiesen, dass jeder auf einem Computer ausführbare Algorithmus unter Verwendung eines Zellularautomaten 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 wir müssen alle Zwischenzustände eines zellulären Automaten aufzunehmen, dann ist es sinnvoll Globals zu verwenden.

    Kartographie


    Das erste , was in den Sinn kommt , wenn es um die Verwendung von Sparse - Arrays zu sprechen - eine Zuordnung Aufgaben.

    Normalerweise haben Karten viel leeren Raum. Wenn die Karte in Form von großen Pixeln dargestellt wird, dann 71% der Pixel der Erde wird durch den Ozean besetzt werden. Sparse - Array. Und angewandt , wenn funktioniert nur von menschlichen Händen, der leere Raum ist mehr als 95%.

    Natürlich hält niemand die Karte in der Form von Rasterfeldern, eine Vektordarstellung verwendet wird .
    Aber was sind Vektorkarten? Es ist ein bestimmte Rahmen und bestand aus Linien und Flächen Punkten.
    In der Tat eine Datenbank von Punkten und Verbindungen zwischen ihnen.

    Eine der ehrgeizigsten Kartierungsaufgaben ist die Kartierung unserer Galaxie mit dem Gaia-Teleskop. Im übertragenen Sinne ist unsere Galaxie wie das gesamte Universum ein zusammenhängendes, spärliches Massiv: riesige Hohlräume, in denen es seltene kleine Punkte gibt - Sterne. Leerraum 99.999999 .......%. Um eine Karte unserer Galaxie zu speichern, wurde eine Datenbank auf den Globalen - Caché - ausgewählt.

    Ich kenne die genaue Struktur der Globals in diesem Projekt nicht, ich kann davon ausgehen, dass dies etwas ähnliches ist wie:

    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
    ...
    

    Wobei b, l, d die galaktischen Koordinaten von Breite, Länge und Entfernung zur Sonne sind.

    Die flexible Struktur der Globalen ermöglicht es Ihnen, beliebige Eigenschaften von Sternen und Planeten zu speichern, da die Basen auf den Globalen ohne Diagramme sind (ohne Schema).

    Für die Speicherung der Karte unseres Universums wurde Caché nicht nur aufgrund seiner Flexibilität ausgewählt, sondern auch aufgrund seiner Fähigkeit, den Datenfluss sehr schnell zu speichern und gleichzeitig Indexglobale für die schnelle Suche zu erstellen.

    Wenn wir zur Erde zurückkehren, wurden OpenStreetMap XAPI- Mapping-Projekte und der OpenStreetMap- Zweig FOSM auf den Globals erstellt .

    Aktuell auf dem Caché Hackathon implementiert wurden geospatial Indizes Geospatial. Wir warten auf die Autoren des Artikels mit Implementierungsdetails.

    Die Umsetzung der räumlichen Indizes in der globalen OpenStreetMap XAPI


    Bilder aus dieser Präsentation .

    Der gesamte Globus ist in Quadrate unterteilt, dann in Unterquadrate und Unterquadrate in Unterquadrate und so weiter. Im Allgemeinen erhalten wir eine hierarchische Struktur, für deren Speicherung die Globalen erstellt werden.



    Wir können das gewünschte Quadrat jederzeit sofort anfordern oder löschen, während alle Teilquadrate ebenfalls zurückgegeben oder gelöscht werden.

    Ein ähnliches Schema für Globals kann auf verschiedene Arten implementiert 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) = 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 für COS / M nicht schwierig, Punkte anzufordern, die auf einer beliebigen Ebene quadriert sind. In der ersten Ausführungsform wird es etwas einfacher sein, quadratische Teile eines beliebigen Niveaus freizugeben, dies ist jedoch selten notwendig.

    Ein Beispiel für eines der Quadrate der unteren Ebene:



    Und hier sind einige des Projektes Globals die XAPI: Globals Ansicht Index:



    Globale ^ Art und Weise zu speichern Punkte verwendet wird Polylinien (Straßen, kleine Flüsse, etc.) und Polygone (geschlossene Bereiche: Gebäude, Wald, usw. .d.).

    Eine grobe Klassifizierung der Verwendung von spärlichen Arrays auf Globals.


    1. Wir speichern die Koordinaten einiger Objekte und deren Status (Mapping, zelluläre Automaten)
    2. Wir speichern spärliche Matrizen.

    Fall 2), wenn eine bestimmte Stelle anfordert, wo das Element nicht gesetzt ist, müssen wir den Standardwert einer spärlichen Array erhalten.

    Boni, die wir erhalten, wenn gespeichert in mehrdimensionale Matrizen Globals


    Schnelles Löschen und / oder Auswählen von Teilen des Raums, bei denen es sich um mehrere Linien, Ebenen, Würfel usw. handelt. In Fällen, in denen Ganzzahlindizes verwendet werden, kann es nützlich sein, Teile des Raums, die mehrere Linien, Ebenen, Würfel usw. umfassen, schnell zu entfernen und / oder auszuwählen.

    Mit dem Kill- Befehl können wir sowohl ein einzelnes Element, eine Zeile als auch eine gesamte Ebene löschen. Aufgrund der Eigenschaften von Globals geschieht dies sehr schnell - tausende Male schneller als das Löschen von Elementen.

    Die Figur zeigt eine dreidimensionale Anordnung in den globalen ^ a und verschiedenen Arten von Deletionen.



    Mit dem Befehl Zusammenführen können Sie Speicherbereiche nach bekannten Indizes abrufen .

    Abrufen einer Matrixspalte in eine Spaltenvariable:

    ; Зададим трёхмерный разреженный массив 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
    

    Interessanterweise haben wir in der Column-Variablen auch ein spärliches Array, auf das auch über $ GET zugegriffen werden muss , da die Standardwerte nicht darin gespeichert sind.

    Die Auswahl von Raumstücken kann auch über ein kleines Programm mit der Funktion $ Order erfolgen . Dies ist besonders praktisch für Räume, deren Indizes nicht quantisiert sind (Kartografie).

    Fazit


    Die heutige Zeit stellt uns vor neue ehrgeizige Herausforderungen. Graphen können aus Milliarden von Eckpunkten, Karten von Milliarden von Punkten bestehen, und jemand möchte vielleicht sogar sein eigenes Universum mit zellularen Automaten betreiben ( 1 , 2 ).

    Wenn die Datenmenge von spärlichen Arrays nicht mehr im RAM gespeichert werden kann, Sie jedoch mit ihnen arbeiten müssen, sollten Sie die Möglichkeit in Betracht ziehen, ähnliche Projekte auf globaler und COS-Ebene zu implementieren.

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

    Haftungsausschluss : Dieser Artikel und meine Kommentare dazu entsprechen meiner Meinung nach nicht der offiziellen Position der InterSystems Corporation.

    Jetzt auch beliebt: