Globali so zakladni meči za shranjevanje podatkov. Redki nizi. 3. del

V prejšnjih delih (1, 2) o globalih smo govorili kot o drevesih, v tem bomo globale obravnavali kot redke nize.

Redka matrika je vrsta matrike, v kateri ima večina vrednosti enako vrednost.

V praksi so redki nizi pogosto tako veliki, da nima smisla zasedati pomnilnika z enakimi elementi. Zato je smiselno izvajati redke nize tako, da se pomnilnik ne zapravlja za shranjevanje enakih vrednosti.
V nekaterih programskih jezikih so redki nizi vključeni v sam jezik, na primer v J, MATLAB. Drugi programski jeziki imajo posebne knjižnice, ki vam omogočajo njihovo implementacijo. Za C++ - Lastna itd

Globali so dobri kandidati za implementacijo redkih nizov, ker:

1. Shranjujejo vrednosti le določenih vozlišč in ne shranjujejo vrednosti nedefiniranih;
2. Vmesnik za dostop do vrednosti vozlišča je zelo podoben temu, koliko programskih jezikov izvaja dostop do elementa večdimenzionalne matrike.

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

3. Global je precej nizkonivojska struktura za shranjevanje podatkov, zato ima izjemne hitrostne lastnosti (od sto tisoč do več deset milijonov transakcij na sekundo, odvisno od strojne opreme, glej spodaj). 1)

Ker je global obstojna struktura, je smiselno na njih ustvariti redke nize, ko je vnaprej znano, da količina RAM-a ne bo zadostovala.

Ena od lastnosti izvedb redke matrike je, da vrne neko privzeto vrednost, če je opravljen dostop do nedefinirane celice.

To je mogoče izvesti s funkcijo $GET v COS. Ta primer obravnava 3-dimenzionalni niz.

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

Katere naloge zahtevajo redke nize in kako lahko globali pomagajo?

Matrika sosednosti (povezljivosti).

Takšne matrice uporablja se za predstavitev grafov:

Očitno je, da večji kot je graf, več ničel bo v matriki. Če na primer vzamemo graf družbenega omrežja in ga predstavimo v obliki podobne matrike, potem bo skoraj v celoti sestavljen iz ničel, tj. bo redko polje.

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

V tem primeru varčujemo globalno ^m matriko povezljivosti, pa tudi število robov na vsakem vozlišču (kdo je s kom prijatelj in število prijateljev).

Če število elementov v grafu ni večje od 29 milijonov (to število je vzeto kot produkt 8 * največja velikost vrstice), torej še bolj ekonomičen način shranjevanja takih matrik so bitni nizi, saj njihova implementacija na poseben način optimizira velike vrzeli.

Manipulacije z bitnimi nizi izvaja funkcija $bit.

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

Prehodna tabela državnega stroja

Ker je prehodni graf končnega avtomata navaden graf, je prehodna tabela končnega avtomata ista matrika sosednosti, o kateri smo razpravljali zgoraj.

Celični avtomati

Najbolj znan celični avtomat je igra "Življenje", ki je zaradi svojih pravil (če ima celica veliko sosedov, odmre) redek niz.

Stephen Wolfram meni, da so celični avtomati novo področje znanosti. Leta 2002 je izdal 1280 strani dolgo knjigo Nova vrsta znanosti, v kateri na splošno trdi, da napredek celičnih avtomatov ni osamljen, ampak je trajen in ima velike posledice za vsa področja znanosti.

Dokazano je, da je vsak algoritem, ki ga je mogoče izvesti v računalniku, mogoče implementirati z uporabo celičnega avtomata. Celični avtomati se uporabljajo za modeliranje dinamičnih okolij in sistemov, za reševanje algoritemskih problemov in za druge namene.

Če imamo ogromno polje in moramo zabeležiti vsa vmesna stanja celičnega avtomata, potem je smiselno uporabiti globale.

Kartografija

Prva stvar, ki mi pride na misel, ko gre za uporabo redkih nizov, so naloge preslikave.

Na zemljevidih ​​je praviloma veliko praznega prostora. Če je zemljevid predstavljen kot velike slikovne pike, potem bo 71 % slikovnih pik Zemlje zasedel ocean. Redka matrika. In če uporabite samo dela človeških rok, bo prazen prostor več kot 95%.

Seveda nihče ne shranjuje zemljevidov v obliki rastrskih nizov, uporablja se vektorska predstavitev.
Toda kaj so vektorski zemljevidi? To je nekakšen okvir in polilinije ter poligoni, sestavljeni iz točk.
V bistvu baza podatkov o točkah in povezavah med njimi.

Ena najbolj ambicioznih misij kartiranja je misija teleskopa Gaia za kartiranje naše galaksije. Slikovito povedano je naša galaksija, tako kot celotno vesolje, neprekinjen redek niz: ogromni prostori praznine, v katerih so redke majhne točke - zvezde. Prazen prostor je 99,999999…….%. Za shranjevanje zemljevida naše galaksije je bila izbrana globalna zbirka podatkov - Caché.

Ne poznam natančne strukture globalov v tem projektu, lahko domnevam, da je nekaj podobnega:

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

Kjer so b, l, d galaktične koordinate širina, dolžina in oddaljenost od sonca.

Prilagodljiva struktura globalov vam omogoča, da shranite vse potrebne značilnosti zvezd in planetov, saj so osnove na globalih brez shem.

Za shranjevanje zemljevida našega vesolja je bil Caché izbran ne le zaradi njegove prilagodljivosti, ampak tudi zaradi njegove zmožnosti zelo hitrega shranjevanja toka podatkov, hkrati pa ustvarja globalne indekse za hitro iskanje.

Če se vrnemo na Zemljo, potem so kartografski projekti nastajali na globalih OpenStreetMap XAPI in razcep OpenStreetMap - FOSM.

Pred kratkim na hackathon Caché implementirani geoprostorski indeksi Geoprostorskih. Čakamo na članek avtorjev s podrobnostmi o izvedbi.

Implementacija prostorskih indeksov na globalu v OpenStreetMap XAPI

Slike posnete iz to predstavitev.

Celotna obla je razdeljena na kvadrate, nato podkvadrate, podkvadrate pa na podpodkvadrate in tako naprej. Na splošno dobimo hierarhično strukturo za shranjevanje, kateri globali so ustvarjeni.

V vsakem trenutku lahko skoraj v trenutku zahtevamo želeni kvadrat ali ga počistimo, vrnjeni ali počiščeni pa bodo tudi vsi podkvadrati.

Podobno shemo na globalih je mogoče izvesti na več načinov.

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

Možnost 2:

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

V obeh primerih ni težko uporabiti COS/M za zahtevanje točk v kvadratu katere koli ravni. V prvi možnosti bo nekoliko lažje očistiti kvadratne kose prostora na kateri koli ravni, vendar je to redko potrebno.

Primer enega izmed kvadratov nižje ravni:

Tukaj je nekaj globalov iz projekta XAPI: predstavitev indeksa na globalih:

globalno ^ način uporablja za shranjevanje točk polilinije (ceste, reke ipd.) in poligoni (zaprta območja: zgradbe, gozdovi ipd.).

Groba klasifikacija uporabe redkih nizov na globalih.

1. Shranjujemo koordinate določenih objektov in njihova stanja (mapiranje, celični avtomati)
2. Shranjujemo redke matrice.

Za primer 2), ko zahtevamo določeno koordinato, kjer elementu ni dodeljena vrednost, moramo pridobiti vrednost privzetega elementa redke matrike.

Bonusi, ki jih prejmemo pri shranjevanju večdimenzionalnih matrik v globale

Hitro odstranite in/ali izberite dele prostora, ki so večkratniki vrstic, ravnin, kock itd. Za primere, kjer se uporabljajo celoštevilski indeksi, je lahko koristna zmožnost hitrega odstranjevanja in/ali pridobivanja kosov prostora, ki so večkratniki vrstic, ravnin, kock itd.

ekipa Kill izbrišemo lahko posamezen element ali vrstico ali celo celotno ravnino. Zahvaljujoč lastnostim globalov se to zgodi zelo hitro – tisočkrat hitreje kot odstranjevanje elementov po elementih.

Slika prikazuje tridimenzionalni niz v globalu ^a in različne vrste izbrisov.

Če želite izbrati dele prostora z znanimi indeksi, lahko uporabite ukaz Spoji.

Izbira stolpca matrike v spremenljivki Column:

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

Zaključek:

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

Pri spremenljivki Column je zanimivo to, da imamo tudi redko matriko, do katere moramo prav tako dostopati prek $GET, saj privzete vrednosti niso shranjene v njem.

Izbiranje kosov prostora lahko izvedete tudi prek majhnega programa s funkcijo $Naročilo. To je še posebej priročno na prostorih, katerih indeksi niso kvantizirani (kartografija).

Zaključek

Sedanji čas postavlja nove ambiciozne naloge. Grafi so lahko sestavljeni iz milijard vozlišč, zemljevidi iz milijard točk, nekateri pa bi morda celo želeli zagnati lastno vesolje na celičnih avtomatih (1, 2).

Ko se količina podatkov iz redkih nizov ne more več prilegati RAM-u, vendar morate z njimi delati, potem je vredno razmisliti o možnosti izvajanja podobnih projektov na globalih in COS.

Hvala za vašo pozornost! Čakamo na vaša vprašanja in želje v komentarjih.

Zavrnitev odgovornosti: Ta članek in moji komentarji nanj so moje mnenje in nimajo nobene zveze z uradnim stališčem InterSystems Corporation.

Vir: www.habr.com