Globala — mappade lagringslösningar för data. Sparse-arrayer. Del 3

I tidigare delar (1, 2) har vi pratat om globaler som träd, i denna kommer vi att betrakta globaler som sparse-arrayer.

Sparse-array är en typ av array där de flesta värdena har samma värde.

I praktiken finns det ofta så stora sparse-arrayer att det inte finns något syfte att använda minne för att lagra identiska element. Därför är det meningsfullt att implementera sparse-arrayer så att minnet inte gastar för att lagra samma värden.
I vissa programmeringsspråk är sparse-arrayer en del av språket, till exempel i J, MATLAB. I andra programmeringsspråk finns det speciella bibliotek som tillåter deras implementering. För C++ — Eigen och andra.

Globala är bra kandidater för implementering av sparse-arrayer, eftersom:

1. De lagrar värden endast för specifika noder och lagrar inga värden för icke-definierade;
2. Gränssnittet för att få tillgång till värdet av en nod liknar mycket det sätt som tillgång till ett element i en flerdimensionell array implementeras i många programmeringsspråk.

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

3. Global är en tillräckligt låg nivå struktur för datalagring, vilket ger utmärkta hastighetskarakteristik (från hundratusentals till tiotals miljoner transaktioner per sekund beroende på hårdvara, se. 1)

Eftersom globalen är en beständig struktur, har det mening att göra sparse-arrayer på dem när det på förhand är känt att mängden RAM kommer att vara otillräcklig.

En av egenskaperna hos implementationerna av sparse-arrayer är att de returnerar ett visst standardvärde om en begäran görs till en icke-definierad cell.

Detta kan implementeras med hjälp av funktionen $GET i COS. I detta exempel presenteras en 3-dimensionell array.

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

Vilka uppgifter kräver då sparse-arrayer och hur kan globaler hjälpa?

Adjacensmatris (koppling)

Sådana matriser används för att representera grafer:

Det är uppenbart att ju större grafen är, desto fler nollor kommer att finnas i matrisen. Om till exempel en social nätverksgraf presenteras som en sådan matris, kommer den att nästan helt bestå av nollor, dvs. den kommer att vara en sparse-array.

Ställ ^m(id1, id2) = 1 
Ställ ^m(id1, id3) = 1 
Ställ ^m(id1, id4) = 1 
Ställ ^m(id1) = 3 
Ställ ^m(id2, id4) = 1 
Ställ ^m(id2, id5) = 1 
Ställ ^m(id2) = 2
....

I detta exempel sparar vi i globala ^m kopplingsmatrisen samt antalet kontakter för varje nod (vem som är vänner med vem och antalet vänner).

Om antalet element i grafen inte överstiger 29 miljoner (detta tal beräknas som produkten av 8 * det maximala storleken på strängen), finns det en ännu mer ekonomisk metod för att lagra sådana matriser - bitsträngar, eftersom stora luckor optimeras på ett särskilt sätt i deras implementation.

Manipulationer med bitsträngar utförs med funktionen $BIT.

; ställ bit
SET $BIT(rowID, positionID) = 1
; hämta bit
Skriv $BIT(rowID, positionID)

Övergångstabell för en automat

Eftersom övergångsgrafen för en automat är en vanlig graf, är övergångstabellen för en automat också samma typ av kopplingsmatris som nämnts ovan.

Cell-automer

Den mest kända cellautomaten är spelet 'Liv', vilket på grund av sina regler (när en cell har många grannar - dör den) utgör en gles matris.

Stephen Wolfram anser att cellautomer är en nytt forskningsområde. År 2002 publicerade han en 1280 sidor lång bok 'A New Kind of Science', där han brett argumenterar för att prestationer inom cellautomer inte är isolerade, utan mycket stabila och har stor betydelse för alla vetenskapsområden.

Det har bevisats att varje algoritm som kan utföras på en dator kan realiseras med hjälp av en cellautomat. Cellautomer används för att modellera dynamiska miljöer och system, för att lösa algoritmiska problem och för andra syften.

Om vi har ett stort fält och behöver registrera alla mellanliggande tillstånd för cellautomaten, är det helt rimligt att använda globala variabler.

Kartografi

Det första som kommer i åtanke när det handlar om att använda glesa matriser är kartografiska uppgifter.

Som regel finns det mycket tomt utrymme på kartor. Om man föreställer sig en karta som stora pixlar, skulle 71 % av pixlarna på jorden upptas av oceaner. En gles matris. Och om man bara markerade mänskliga skapelser skulle mer än 95 % vara tomt utrymme.

Självklart lagrar ingen kartor som rastermatriser, istället används vektorrepresentation.
Men vad är vektorkartor? Det är en viss ram som består av punkter, polylinjer och polygoner.
Det är i praktiken en databas med punkter och relationer mellan dem.

En av de mest ambitiösa kartläggningsuppgifterna är kartläggningen av vår galax med teleskopet Gaia. Bildligt talat är vår galax, liksom hela universum, ett sammanhängande glesmönster: enorma tomma rum där det finns sällsynta små punkter — stjärnor. Tomt utrymme utgör 99,999999…….%. För att lagra en karta över vår galax valdes en global databas — Caché.

Jag känner inte den exakta strukturen för globaler i det här projektet, men jag kan anta att det ungefär ser ut som:

Set ^galaxy(b, l, d) = 1; Stjärnnummer i katalogen, om det finns
Set ^galaxy(b, l, d, "name") = "Sol"
Set ^galaxy(b, l, d, "type") = "normal"; alternativ som blackhole, quasar, red_dwarf osv.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Merkurius"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...

Där b, l, d — är galaktiska koordinater latitud, longitud och avståndet till solen.

Den flexibla strukturen av globaler gör det möjligt att lagra alla nödvändiga egenskaper hos stjärnor och planeter, eftersom databaser på globaler är schemaslösa.

För lagring av kartan över vårt universum valdes Caché inte bara för sin flexibilitet utan också för sin snabbhet i dataflödeslagring, samtidigt som den genererar indexglobaler för snabb sökning.

Tillbaka till jorden, så skapades kartläggningsprojekt på globaler. OpenStreetMap XAPI och en fork av OpenStreetMap — FOSM.

Nyligen på Caché-hackathonet genomfördes geospatiala index Geospatial. Vi väntar på detaljer om implementationen från artikelförfattarna.

Implementeringen av rumsliga index på globaler i OpenStreetMap XAPI

Bilderna är hämtade från denna presentation..

Hela jordklotet delas upp i kvadrater, sedan underkvadrater och underkvadrater till underunderkvadrater och så vidare. I stort sett får vi en hierarkisk struktur för lagring, för vilken globaler har skapats.

Vid varje tillfälle kan vi nästan omedelbart begära den nödvändiga kvadraten eller rensa den, och alla underkvadrater returneras eller rensas också.

En liknande struktur kan implementeras på globaler på flera sätt.

Alternativ 1:

Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idFörstaPunkten
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idAndraPunkten
...

Alternativ 2:

Set ^m('abacdabcdabacdabcda', 1) = idFörstaPunkten
Set ^m('abacdabcdabacdabcda', 2) = idAndraPunkten
...

I båda fallen är det enkelt att begära punkterna som ligger inom en kvadrat av valfri storlek på COS/M. Det är något lättare att rensa kvadrater av valfri storlek i det första alternativet, men det behövs sällan.

Ett exempel på en av de lägre nivåernas kvadrater:

Och här är några globala från projektet XAPI: visning av index på globala:

Global ^way används för att lagra punkter polylinjer (vägar, små floder etc.) och polygoner (slutna områden: byggnader, skogar etc.).

Grov klassificering av användningen av glesa matrisar på globala.

1. Vi lagrar koordinater för vissa objekt och deras tillstånd (kartläggning, cellulära automater)
2. Vi lagrar glesa matriser.

I fall 2) vid begäran om en viss koordinat, där ett element inte har något tilldelat värde, måste vi få värdet för det glesa matrisens element som standard.

Bonusarna vi får genom att lagra flerdimensionella matriser på globala

Snabb borttagning och/eller urval av områden som är multipler av rader, plan, kuber etc. För fall där heltalsindex används, kan möjligheten till snabb borttagning och/eller urval av områden som är multipler av rader, plan, kuber etc. visa sig vara användbar.

Kommandot Kill kan vi ta bort både ett enskilt element, en rad och till och med ett helt plan. Tack vare egenskaperna hos globala sker detta mycket snabbt — tusentals gånger snabbare än elementspecifik borttagning.

Illustrationen visar en tredimensionell matris i det globala ^a och olika typer av borttagningar.

För att välja områden i rummet efter kända index kan kommandot användas Merge.

Urval av kolumnen i matrisen till variabeln Column:

; Vi definierar en tredimensionell gles matris 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)
; Vi skriver ut variabeln Column
Zwrite Column

Slutsats:

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

Intressant nog fick vi också en gles matris i variabeln Column, som också måste refereras till via $GET, eftersom standardvärdena inte lagras i den.

Urval av områden kan också göras via ett litet program med hjälp av funktionen $Order. Detta är särskilt praktiskt i rum där indexen inte är kvantifierade (kartläggning).

Slutsats

Nutidens tider ställer nya ambitiösa mål. Grafer kan bestå av miljarder noder, kartor av miljarder punkter, och någon kan till och med vilja starta sitt eget universum på cellulära automater (1, 2).

När mängden data från glesa matriser inte längre får plats i RAM-minnet och man behöver arbeta med dem, bör man överväga att implementera sådana projekt på globala system och COS.

Tack för uppmärksamheten! Vi ser fram emot era frågor och önskemål i kommentarerna.

Ansvarsfriskrivning: Denna artikel och mina kommentarer till den är min åsikt och har ingen koppling till företagets officiella ställning, InterSystems.

Källa: habr.com