I tidligere dele (, ) vi talte om globaler som træer, i denne vil vi se på globaler som sparsomme arrays.
er en type array, hvor de fleste værdier har samme værdi.
I praksis er sparsomme arrays ofte så store, at det ikke nytter noget at optage hukommelsen med identiske elementer. Derfor giver det mening at implementere sparse arrays på en sådan måde, at hukommelsen ikke spildes på at lagre identiske værdier.
I nogle programmeringssprog er sparsomme arrays inkluderet i selve sproget, , . Andre programmeringssprog har specielle biblioteker, der giver dig mulighed for at implementere dem. For C++ - etc.
Globaler er gode kandidater til at implementere sparsomme arrays, fordi:
- De gemmer kun værdierne af visse noder og gemmer ikke værdierne af udefinerede;
- Grænsefladen til at få adgang til en nodes værdi er ekstremt lig, hvor mange programmeringssprog der implementerer adgang til et multidimensionalt array-element.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global er en struktur på ret lavt niveau til lagring af data, derfor har den fremragende hastighedsegenskaber (fra hundredtusinder til titusinder af transaktioner pr. sekund, afhængigt af hardwaren, se nedenfor). )
Da det globale er en vedvarende struktur, giver det mening at lave sparsomme arrays på dem, når det på forhånd er kendt, at mængden af RAM ikke vil være nok.
En af egenskaberne ved sparse array-implementeringer er at returnere en eller anden standardværdi, hvis der gives adgang til en udefineret celle.
Dette kan implementeres ved hjælp af funktionen i COS. Dette eksempel betragter et 3-dimensionelt array.
SET a = $GET(^a(x,y,z), defValue)Hvilke opgaver kræver sparsomme arrays, og hvordan kan globaler hjælpe?
Adjacency (forbindelse) matrix
bruges til at repræsentere grafer:
Det er klart, at jo større grafen er, jo flere nuller vil der være i matrixen. Hvis vi for eksempel tager en social netværksgraf og præsenterer den i form af en lignende matrix, så vil den næsten udelukkende bestå af nuller, dvs. vil være en sparsom række.
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 eksempel sparer vi globalt ^m forbindelsesmatrix, samt antallet af kanter ved hver node (hvem er venner med hvem og antallet af venner).
Hvis antallet af elementer i grafen ikke er mere end 29 millioner (dette tal tages som produktet af 8 * ), det vil sige, at en endnu mere økonomisk måde at gemme sådanne matricer på er bitstrenge, da deres implementering optimerer store huller på en særlig måde.
Manipulationer med bitstrenge udføres af funktionen .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Statsmaskine overgangstabel
Da overgangsgrafen for en endelig automat er en almindelig graf, så er overgangstabellen for den endelige automat den samme tilgrænsende matrix, som er diskuteret ovenfor.
Cellulære automater
Den mest berømte cellulære automat er , som på grund af sine regler (når en celle har mange naboer, dør den) er et sparsomt array.
Stephen Wolfram mener, at cellulære automater er . I 2002 udgav han en 1280-siders bog, A New Kind of Science, hvori han argumenterer bredt for, at fremskridt inden for cellulære automater ikke er isolerede, men varige og har store implikationer for alle områder af videnskaben.
Det er blevet bevist, at enhver eksekverbar algoritme på en computer kan implementeres ved hjælp af en cellulær automat. Cellulære automater bruges til at modellere dynamiske miljøer og systemer, til at løse algoritmiske problemer og til andre formål.
Hvis vi har et enormt felt, og vi skal registrere alle de mellemliggende tilstande af en cellulær automat, så giver det mening at bruge globaler.
Kartografi
Det første, der falder mig ind, når det kommer til at bruge sparse arrays, er kortlægningsopgaver.
Som regel er der meget tomt på kort. Hvis kortet er repræsenteret som store pixels, så vil 71 % af Jordens pixels blive optaget af havet. Sparsom række. Og hvis du kun anvender værker af menneskelige hænder, vil det tomme rum være mere end 95%.
Selvfølgelig er der ingen, der gemmer kort i form af raster-arrays; der bruges en vektorrepræsentation.
Men hvad er vektorkort? Dette er en slags ramme og polylinjer og polygoner bestående af punkter.
Grundlæggende en database med punkter og forbindelser mellem dem.
En af de mest ambitiøse kortlægningsmissioner er Gaia Telescope-missionen for at kortlægge vores galakse. Billedligt talt er vores galakse, ligesom hele universet, en kontinuerlig sparsom række: enorme rum af tomhed, hvor der er sjældne små punkter - stjerner. Tomt rum er 99,999999…….%. For at gemme kortet over vores galakse blev der valgt en global database - Caché.
Jeg kender ikke den nøjagtige struktur af globaler i dette projekt, jeg kan antage, at det er noget, der ligner:
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 og afstand til solen.
Den fleksible struktur af globaler giver dig mulighed for at gemme alle nødvendige egenskaber ved stjerner og planeter, da baserne på globaler er skemaløse.
For at gemme kortet over vores univers blev Caché valgt ikke kun for dets fleksibilitet, men også for dets evne til at gemme en strøm af data meget hurtigt, samtidig med at der skabes indeksglobaler til hurtige søgninger.
Hvis vi vender tilbage til Jorden, så blev der skabt kartografiske projekter på globaler og en gaffel af OpenStreetMap - .
For nylig på geospatiale indekser blev implementeret . Vi venter på en artikel fra forfatterne med implementeringsdetaljer.
Implementering af rumlige indekser på en global i OpenStreetMap XAPI
Billeder taget fra .
Hele kloden er opdelt i kvadrater, derefter sub-kvadrater, og sub-kvadrater i sub-under-kvadrater, og så videre. Generelt får vi en hierarkisk struktur til lagring af, hvilke globaler der oprettes.
På ethvert tidspunkt kan vi næsten øjeblikkeligt anmode om den ønskede firkant eller rydde den, og alle underkvadrater vil også blive returneret eller ryddet.
En lignende ordning på globaler kan implementeres på flere måder.
Mulighed 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ВторойТочки
...Mulighed 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...I begge tilfælde er det ikke svært at bruge COS/M til at anmode om punkter placeret i en firkant på et hvilket som helst niveau. Det vil være noget lettere at rengøre firkantede stykker plads på ethvert niveau i den første mulighed, men det er sjældent nødvendigt.
Et eksempel på en af kvadraterne på lavere niveau:
Og her er flere globaler fra XAPI-projektet: repræsentation af et indeks over globaler:
global ^måde bruges til at gemme point (veje, små floder osv.) og polygoner (lukkede områder: bygninger, skove osv.).
Groft klassificering af brugen af sparse arrays på globaler.
- Vi gemmer koordinaterne for visse objekter og deres tilstande (kortlægning, cellulære automater)
- Vi opbevarer sparsomme matricer.
For tilfælde 2) når vi anmoder om en specifik koordinat, hvor elementet ikke er tildelt en værdi, skal vi få værdien af standard sparse array-elementet.
Bonusser, som vi modtager ved lagring af multidimensionelle matricer i globaler
Fjern og/eller vælg hurtigt stykker rum, der er multipla af rækker, fly, terninger osv. I tilfælde, hvor der bruges heltalsindekser, kan muligheden for hurtigt at fjerne og/eller hente bidder af plads, der er multipla af rækker, planer, terninger osv. være nyttig.
Hold vi kan slette enten et enkelt element eller en række, eller endda et helt fly. Takket være egenskaberne for globaler sker dette meget hurtigt - tusindvis af gange hurtigere end element-for-element fjernelse.
Figuren viser et tredimensionelt array i en global ^a og forskellige typer sletninger.
For at vælge stykker plads ved hjælp af kendte indekser, kan du bruge kommandoen .
Valg af en matrixkolonne i kolonnevariablen:
; Зададим трёхмерный разреженный массив 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
Konklusion:
Column(0)=1
Column(2)=1
Det interessante ved kolonnevariablen er, at vi også har et sparsomt array, som også skal tilgås via , da standardværdier ikke er gemt i den.
Udvælgelse af stykker plads kan også ske gennem et lille program ved hjælp af funktionen . Dette er især praktisk på rum, hvis indeks ikke er kvantificeret (kartografi).
Konklusion
Den nuværende tid byder på nye ambitiøse opgaver. Grafer kan bestå af milliarder af hjørner, kort af milliarder af punkter, og nogle vil måske endda køre deres eget univers på cellulære automater (, ).
Når mængden af data fra sparsomme arrays ikke længere kan passe ind i RAM, men du skal arbejde med dem, så er det værd at overveje muligheden for at implementere lignende projekter på globals og COS.
Tak for din opmærksomhed! Vi venter på dine spørgsmål og ønsker i kommentarerne.
Ansvarsfraskrivelse: Denne artikel og mine kommentarer til den er min mening og har ingen relation til InterSystems Corporations officielle holdning.
Kilde: www.habr.com