Globaler er skattesverd for lagring av data. Sparsomme matriser. Del 3

I tidligere deler (1, 2) vi snakket om globaler som trær, i denne vil vi se på globaler som sparsomme matriser.

Sparsomt utvalg er en type array der de fleste verdiene har samme verdi.

I praksis er sparsomme matriser ofte så store at det ikke er noen vits i å okkupere minnet med identiske elementer. Derfor er det fornuftig å implementere sparsomme matriser på en slik måte at minnet ikke kastes bort på å lagre identiske verdier.
I noen programmeringsspråk er sparsomme matriser inkludert i selve språket, for eksempel i J, MATLAB. Andre programmeringsspråk har spesielle biblioteker som lar deg implementere dem. For C++ - Egen etc.

Globaler er gode kandidater for å implementere sparsomme matriser fordi:

1. De lagrer verdiene til bare visse noder og lagrer ikke verdiene til udefinerte;
2. Grensesnittet for å få tilgang til en nodes verdi er ekstremt likt hvor mange programmeringsspråk som implementerer tilgang til et flerdimensjonalt array-element.

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

3. Global er en struktur på ganske lavt nivå for lagring av data, derfor har den enestående hastighetsegenskaper (fra hundretusener til titalls millioner transaksjoner per sekund, avhengig av maskinvaren, se nedenfor). 1)

Siden det globale er en vedvarende struktur, er det fornuftig å lage sparsomme matriser på dem når det er kjent på forhånd at mengden RAM ikke vil være nok.

En av egenskapene til sparse array-implementeringer er å returnere en viss standardverdi hvis det gjøres tilgang til en udefinert celle.

Dette kan implementeres ved hjelp av funksjonen $GET i COS. Dette eksemplet tar for seg en 3-dimensjonal matrise.

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

Hvilke oppgaver krever sparsomme matriser og hvordan kan globaler hjelpe?

Adjacency (tilkoblings) matrise

Slike matriser brukes til å representere grafer:

Jo større grafen er, jo flere nuller vil det være i matrisen. Hvis vi for eksempel tar en sosial nettverksgraf og presenterer den i form av en lignende matrise, vil den nesten utelukkende bestå av nuller, dvs. vil være en sparsom rekke.

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

I dette eksemplet sparer vi globalt ^m tilkoblingsmatrise, samt antall kanter ved hver node (hvem er venn med hvem og antall venner).

Hvis antallet elementer i grafen ikke er mer enn 29 millioner (dette tallet tas som produktet av 8 * maksimal linjestørrelse), det vil si at en enda mer økonomisk måte å lagre slike matriser på er bitstrenger, siden implementeringen deres optimaliserer store gap på en spesiell måte.

Manipulasjoner med bitstrenger utføres av funksjonen $BIT.

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

Statlig maskinovergangstabell

Siden overgangsgrafen til en begrenset automat er en vanlig graf, er overgangstabellen til den endelige automaten den samme tilstøtende matrisen som er diskutert ovenfor.

Mobilautomater

Den mest kjente mobilautomaten er spillet "Life", som på grunn av reglene (når en celle har mange naboer, dør den) er en sparsom matrise.

Stephen Wolfram mener at cellulære automater er det nytt vitenskapsfelt. I 2002 ga han ut en 1280-siders bok, A New Kind of Science, der han argumenterer bredt for at fremskritt innen cellulære automater ikke er isolert, men varig og har store implikasjoner for alle områder av vitenskapen.

Det har blitt bevist at enhver kjørbar algoritme på en datamaskin kan implementeres ved hjelp av en mobilautomat. Cellulære automater brukes til å modellere dynamiske miljøer og systemer, for å løse algoritmiske problemer og til andre formål.

Hvis vi har et stort felt og vi trenger å registrere alle mellomtilstandene til en cellulær automat, så er det fornuftig å bruke globaler.

Kartografi

Det første jeg tenker på når det gjelder å bruke sparsomme matriser er kartleggingsoppgaver.

Som regel er det mye tomt på kart. Hvis kartet er representert som store piksler, vil 71 % av jordens piksler være okkupert av havet. Sparsomt utvalg. Og hvis du bare bruker verk av menneskelige hender, vil den tomme plassen være mer enn 95%.

Selvfølgelig lagrer ingen kart i form av raster-arrays en vektorrepresentasjon.
Men hva er vektorkart? Dette er en slags ramme og polylinjer og polygoner som består av punkter.
I hovedsak en database med punkter og forbindelser mellom dem.

Et av de mest ambisiøse kartoppdragene er Gaia Telescope-oppdraget for å kartlegge galaksen vår. Billedlig talt er galaksen vår, som hele universet, en kontinuerlig sparsom rekke: enorme rom av tomhet der det er sjeldne små punkter - stjerner. Tom plass er 99,999999…….%. For å lagre kartet over galaksen vår, ble en global database valgt - Caché.

Jeg vet ikke den nøyaktige strukturen til globaler i dette prosjektet, jeg kan anta at det er noe som ligner på:

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

Hvor b, l, d er galaktiske koordinater breddegrad, lengdegrad og avstand til sola.

Den fleksible strukturen til globaler lar deg lagre alle nødvendige egenskaper til stjerner og planeter, siden basene på globaler er skjemaløse.

For å lagre kartet over universet vårt, ble Caché valgt ikke bare for sin fleksibilitet, men også for sin evne til å lagre en strøm av data veldig raskt, samtidig som man lager indeksglobaler for raske søk.

Hvis vi kommer tilbake til jorden, ble kartografiske prosjekter skapt på globaler OpenStreetMap XAPI og en gaffel med OpenStreetMap - FOSM.

Nylig på hackathon Caché geospatiale indekser ble implementert Geospatial. Vi venter på en artikkel fra forfatterne med implementeringsdetaljer.

Implementering av romlige indekser på en global i OpenStreetMap XAPI

Bilder tatt fra denne presentasjonen.

Hele kloden er delt inn i firkanter, deretter underkvadrater, og underkvadrater i underkvadrater, og så videre. Generelt får vi en hierarkisk struktur for å lagre hvilke globaler som lages.

Når som helst kan vi nesten umiddelbart be om ønsket rute eller fjerne den, og alle delruter vil også bli returnert eller tømt.

En lignende ordning på globaler kan implementeres på flere måter.

Alternativ 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ВторойТочки
...

Alternativ 2:

Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...

I begge tilfeller er det ikke vanskelig å bruke COS/M til å be om poeng plassert i en firkant uansett nivå. Det vil være noe lettere å rengjøre firkantede stykker plass på et hvilket som helst nivå i det første alternativet, men dette er sjelden nødvendig.

Et eksempel på en av rutene på lavere nivå:

Og her er flere globaler fra XAPI-prosjektet: representasjon av en indeks på globaler:

global ^måte brukes til å lagre poeng polylinjer (veier, små elver osv.) og polygoner (lukkede områder: bygninger, skog osv.).

Grov klassifisering av bruken av sparsomme arrays på globaler.

1. Vi lagrer koordinatene til visse objekter og deres tilstander (kartlegging, mobilautomater)
2. Vi lagrer sparsomme matriser.

For tilfelle 2) når vi ber om en spesifikk koordinat der elementet ikke er tildelt en verdi, må vi få verdien til standard sparse array-elementet.

Bonuser som vi mottar når vi lagrer flerdimensjonale matriser i globaler

Fjern raskt og/eller velg deler av plass som er multipler av rader, fly, kuber osv. For tilfeller der heltallsindekser brukes, kan muligheten til raskt å fjerne og/eller hente deler av plass som er multipler av rader, plan, kuber osv. være nyttig.

Team Drepe vi kan slette enten et enkelt element eller en rad, eller til og med et helt fly. Takket være egenskapene til globaler skjer dette veldig raskt - tusenvis av ganger raskere enn element-for-element-fjerning.

Figuren viser en tredimensjonal matrise i en global ^a og ulike typer slettinger.

For å velge mellomrom ved hjelp av kjente indekser, kan du bruke kommandoen Flett.

Velge en matrisekolonne i kolonnevariabelen:

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

Konklusjon:

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

Det som er interessant med kolonnevariabelen er at vi også har en sparsom matrise, som også må nås gjennom $GET, siden standardverdier ikke er lagret i den.

Valg av plass kan også gjøres gjennom et lite program ved hjelp av funksjonen $Order. Dette er spesielt praktisk på rom hvis indekser ikke er kvantiserte (kartografi).

Konklusjon

Den nåværende tiden byr på nye ambisiøse oppgaver. Grafer kan bestå av milliarder av hjørner, kart består av milliarder av punkter, og noen vil kanskje til og med kjøre sitt eget univers på mobilautomater (1, 2).

Når volumet av data fra sparsomme arrays ikke lenger kan passe inn i RAM, men du må jobbe med dem, er det verdt å vurdere muligheten for å implementere lignende prosjekter på globaler og COS.

Takk for din oppmerksomhet! Vi venter på dine spørsmål og ønsker i kommentarene.

Ansvarsfraskrivelse: Denne artikkelen og mine kommentarer til den er min mening og har ingen relasjon til den offisielle stillingen til InterSystems Corporation.

Kilde: www.habr.com