Globaale — andmete salvestamise mõõgad-ladenetsed. Harulduse massiivid. Osa 3.

Eelmine osa (1, 2) rääkisime globaalsusest kui puudest, nüüd uurime globaalsust kui hõredaid massiive.

Hõre massiiv on eriline massiivitüüp, kus enamus väärtustest on samad.

Praktikas esinevad sedavõrd suured hõredad massiivid, et ei ole mõtet mäluruumi raisata samade elementide tõttu. Seetõttu on mõistlik hõredeid massiive rakendada nii, et mälu ei raiskataks samade väärtuste hoidmisele.
Mõnes programmeerimiskeeles on hõredad massiivid juba keele osa, näiteks J, MATLAB. Teistes programmeerimiskeeltes on spetsiaalsed teegid, mille abil neid rakendada. C++ jaoks — Eigen ja palju muud.

Globaalsed olendid on head kandidaadid hõredate massiivide rakendamiseks, sest:

1. Nad hoiavad ainult teatud sõlmede väärtusi, mitte määramata väärtusi;
2. Sõlme väärtusele pääsemise liides sarnaneb väga sellele, kuidas paljudes programmeerimiskeeltes rakendatakse mitmemõõtmelise massiivi elementi.

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

3. Gloobaal on piisavalt madala taseme struktuur andmete hoidmiseks, seega omab see suurepäraseid kiirusomadusi (sadu tuhandeid kuni kümneid miljoneid tehinguid sekundis, sõltuvalt riistvarast, vt. 1)

Kuna gloobaal on püsiv struktuur, on mõistlik rakendada hõredeid massiive, kui on juba ette teada, et operatiivmälu mahust ei piisa.

Üks hõrede massiivi rakenduse omadustest on vaikimisi mingi väärtuse tagastamine, kui pöördutakse määramata lahtri poole.

Seda saab rakendada, kasutades funktsiooni $GET COS-is. Antud näites käsitletakse 3-mõõtmelist massiivi.

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

Millistes ülesannetes on hõredaid massiive vaja ja kuidas gloobaalid saavad abiks olla?

Siduva (seosetabeli) maatriks

Selliseid maatrikseid kasutatakse graafide esitlemiseks:

Ilmselgelt, et mida suurem on graaf, seda rohkem nullväärtusi on maatriksis. Kui näiteks võtta sotsiaalvõrgustiku graaf ja esitada see sarnases maatriksis, siis koosneb see peaaegu täielikult nullidest, st see on hõre massiiv.

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

Antud näites salvestame gloobaali ^m ühenduvuse maatriks, samuti iga sõlme servade arv (kes kellega sõbrustab ja sõprade arv).

Kui graafis on elemente mitte rohkem kui 29 miljonit (see number saadakse 8 * maksimaalne stringi suurus), siis on olemas veelgi ökonoomsem viis selliste maatriksite salvestamiseks — bittide read, kuna nende rakenduses optimeerivad suured tühimikud eriliselt.

Bittide ridade manipuleerimine toimub funktsiooni $BIT.

; bit, seadistamine
SET $BIT(rowID, positionID) = 1
; bit, saamine
Write $BIT(rowID, positionID)

Lõpliku automaadi üleminekute tabel

Kuna lõpliku automaadi ülemineku graaf on tavaline graaf, on lõpliku automaadi üleminekute tabel sama, millest eespool räägiti — see on samuti adjektiivmaatriks.

Raku automaadid

Tuntuim raku automaat on mäng "Elu", mille tõttu tema reeglid (kui rakul on palju naabreid — see sureb) esindab hõredat masiivi.

Steven Wolfram peab raku automate uus teaduse valdkond. . Aastal 2002 avaldas ta 1280-leheküljelise raamatu "Uus teadustüüp", kus ta laialdaselt väidab, et edusammud raku automaatide valdkonnas ei ole isoleeritud, vaid on piisavalt stabiilsed ja omavad suurt tähtsust kõigis teaduse valdkondades.On tõestatud, et iga arvutuslik algoritm, mida saab arvutis teostada, saab rakendada raku automaatide abil. Raku automate kasutatakse dünaamiliste keskkondade ja süsteemide modelleerimiseks, algoritmiliste probleemide lahendamiseks ja teiste eesmärkide saavutamiseks.

Kui meil on tohutu ala ja peame salvestama kõik raku automaadi vahepealsed seisundid, on täiesti mõistlik kasutada globaalset.

Kartoograafia

Esimene asi, mis mulle pähe tuleb, kui rääkida hõredate masiivide kasutamisest — on kaartide ülesanded.

Üldiselt on kaartidel väga palju tühja ruumi. Kui kaarti kujutada suurte pikslitena, siis 71% Maa pikslitest on ookean. Hõre maatriks. Ja kui joonistada vaid inimkäte tekitatud teosed, siis tühja ruumi on üle 95%.

Muidugi ei hoia keegi kaarte rastermasiivide kujul, kasutatakse vektorivat esitamist.

Aga mis on vektorikaardid? See on mingi raam ja punktidest koosnevad polüjooned ja polügoonid.
Aga mis on vektorkaartide olemus? Need on teatud raamistik ning koosnevad punktidest, polüliinidest ja poligonidest.
Tegelikult on punktide ja nende vaheliste sidemete andmebaas.

Üks kõige ambitsioonikamaid kaardistamise ülesandeid on meie galaktika kaardistamise missioon Gaia teleskoobiga. Kujutledes, meie galaktika, nagu kogu universum, on ühtne hõre mass: tohutud tühjad ruumid, milles on haruldased väiksed punktid — tähed. Tühja ruumi on 99,999999…….%. Meie galaktika kaardi salvestamiseks valiti globaalide andmebaas — Caché.

Ma ei tea projekti globaalide täpset struktuuri, kuid võin eeldada, et see on midagi sellist:

Set ^galaxy(b, l, d) = 1; Tähe number kataloogis, kui see on olemas
Set ^galaxy(b, l, d, "name") = "Päike"
Set ^galaxy(b, l, d, "type") = "tavaline" ; variandid blackhole, quazar, punane kääbus jne.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Merkur"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...

Kus b, l, d — on galaktilised koordinaadid laius, pikkus ja kaugus Päikesest.

Globaalide paindlik struktuur võimaldab salvestada igasuguseid tähti ja planeetide omadusi, kuna globaalide andmebaasid on skeemivabad (scheme-less).

Meie universumi kaardi salvestamiseks valiti Caché mitte ainult paindlikkuse tõttu, vaid ka selle tõttu, et see salvestab andmevooge väga kiiresti, samal ajal luues indekseeritud globaalid kiireks otsimiseks.

Kui aga naasta Maale, siis globaalidesse loodi kaardistamisprojektid OpenStreetMap XAPI ja OpenStreetMapi fork — FOSM.

Hiljuti Caché hackathonil rakendati georuumilisi indekse Geospatial. Ootame artikli autoritelt teavet juurutamise detailide kohta.

Ruumiliste indeksite rakendamine globaalides OpenStreetMap XAPI-s

Pildid on pärit selles esitluses.

Kogu maakera jaguneb ruutudeks, siis väikesteks ruutudeks, ja väiksed ruudud jaotatakse veelgi väiksemateks ruutudeks jne. Kokkuvõttes saame hierarhilise struktuuri, mille jaoks globaalid on loodud.

Igal ajal saame praktiliselt koheselt nõuda vajalikku ruutu või selle eemaldada, samal ajal tagastatakse kõik väikesed ruudud või need puhastatakse.

Sarnast skeemi globaalides on võimalik rakendada mitmel viisil.

Variant 1:

Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idEsimesePunkti
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idTeisePunkti
...

Variant 2:

Set ^m('abacdabcdabacdabcda', 1) = idEsimesePunkti
Set ^m('abacdabcdabacdabcda', 2) = idTeisePunkti
...

Mõlemal juhul on COS/M-is lihtne taotleda ruutude punkte mis tahes tasemel. Esimeses variandis on ruutude tükkide puhastamine mistahes tasemel pisut lihtsam, kuid seda harva vajatakse.

Näide ühest madalama taseme ruudust:

Siin on mõned globaalid projektist XAPI: indeksi esitamine globaalides:

Globaal ^way kasutatakse punktide talletamiseks polüliinid (teed, väiksed jõed jne) ja polügoonid (sulgudes piirkonnad: hooned, metsad jne).

Karm klassifikatsioon hõredate massiivide kasutamisest globaalides.

1. Me talletame teatud objektide koordinaadid ja nende olekud (kaartimine, rakud automaadid)
2. Me talletame hõredaid maatrikseid.

Juhtumi 2 korral, kui pärime teatud koordinaati, kus elemendile pole väärtust määratud, peame saama hõreda massiivi elemendi vaikeväärtuse.

Boonused, mida me saame mitmemõõtmeliste maatriksite talletamisel globaalides

Kiire eemaldamine ja/või ruutude valikud, mis on mitmekordsed ridadele, tasapindadele, kuubikutele jne. Juhtudel, kus kasutatakse täisarvulisi indekseid, võib osutuda kasulikuks kiire eemaldamise ja/või ruutude valikute võimalus, mis on mitmekordsed ridadele, tasapindadele, kuubikutele jne.

Käsuga Tapa me saame eemaldada nii eraldi elementi, rida kui ka terve tasapinna. Tänu globaalide omadustele toimub see väga kiiresti — tuhandete kordi kiiremini kui elemendi eemaldamine.

Joonisel on näidatud kolmemõõtmeline massiiv globaalides ^a ja erinevad eemaldamise viisid.

Ruudukeste valimiseks tuntud indeksite alusel saab kasutada käsku Merge.

Maatriksi veeru valimine muutujasse Column:

; Määrame kolmemõõtmelise hõreda massiivi 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)
; Väljastame muutuja Column
Zwrite Column

Kokkuvõte:

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

Mis on huvitav, muutuja Column on ka saanud hõreda massiivi, millele tuleb viidata samuti läbi $GET, kuna vaikeväärtusi selles ei talletata.

Ruutekeste valimine võib samuti toimuda läbi väikese programmi, kasutades funktsiooni $Käsk. See on eriti mugav ruumides, mille indeksid ei ole kvantitud (kaardistamine).

Kokkuvõte

Praegused ajad seavad uusi ambitsioonikaid ülesandeid. Graafikud võivad koosneda miljarditest tipudest, kaardid miljarditest punktidest ja keegi võib isegi soovida oma universumit käivitada rakendatud automaatidel (1, 2).

Kui andmete kogus hajusates massiivides ei mahugi enam operatiivmälu, kuid nendega tuleb siiski töötada, tasub kaaluda sarnaste projektide elluviimise võimalust globaalselt ja COS-il.

Aitäh tähelepanu eest! Ootame teie küsimusi ja soovitusi kommentaarides.

Märkus: See artikkel ja minu kommentaarid sellele on minu arvamus ning ei kajasta InterSystems korporatsiooni ametlikku seisukohta.

Allikas: habr.com