Globaalid - andmete salvestamise mõõgakäepidemed. Jõhkrad massiivid. Osa 3

Eelmistes osades (1, 2) rääkisime globaalidest kui puudest, sel korral vaatleme globaale harudena.

Haruline massiiv on massiivi tüüp, kus enamus väärtusi on samad.

Praktikas esinevad tihti nii suured harulised massiivid, et pole mõtet neid mälu jaotada ühesuguste elementidega. Seetõttu on mõistlik implementerida harulisi massiive nii, et mälu ei kuluks sama väärtuse hoidmiseks.
Mõnes programmeerimiskeeles on harulised massiivid keele osa, näiteks J, MATLAB. Teistes programmeerimiskeeltes on spetsiaalsed teegid, mis võimaldavad neid teostada. C++ jaoks — Eigen jne.

Globaalid on head kandidaadid haruliste massiivide rakendamiseks, kuna:

1. Need hoiavad väärtusi ainult teatud sõlmedes ja ei hoia defineerimata väärtusi;
2. Sõlme väärtusele juurdepääsu liides sarnaneb väga sellele, kuidas paljudes programmeerimiskeeltes on rakendatud juurdepääs mitmemõõtmelise massiivi elemendile.

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

3. Globaal on piisavalt madala taseme struktuur andmete salvestamiseks, seega omab see erakordseid kiirusnäitajaid (sajad tuhanded kuni kümned miljonid tehingud sekundis sõltuvalt riistvarast, vt. 1)

Kuna globaal on püsiv struktuur, on mõtet luua haruldasi massiive siis, kui on eelnevalt teada, et pärisraha maht on ebapiisav.

Üheks haruldaste massiivide rakenduse omaduseks on mingi vaikimisi väärtuse tagastamine, kui pöördutakse määratlemata mälurakenduse poole.

Seda saab rakendada, kasutades funktsiooni $GET COSis. Antud näites on käsitletud kolme mõõtme massiivi.

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

Millistes ülesannetes on vajalikud haruldased massiivid ja kuidas globaalid võivad abiks olla?

Sidematriits (ühenduse)

Sellised matriitsid kasutatakse graafide esitamiseks:

On ilmne, et mida suurem on graaf, seda rohkem nullväärtusi on matriitsis. Näiteks, kui võtta sotsiaalvõrgustiku graaf ja esitada see sarnase matriitsina, koosneb see peaaegu täielikult nullidest, see tähendab, et see on haruldane massiiv.

Sea ^m(id1, id2) = 1 
Sea ^m(id1, id3) = 1 
Sea ^m(id1, id4) = 1 
Sea ^m(id1) = 3 
Sea ^m(id2, id4) = 1 
Sea ^m(id2, id5) = 1 
Sea ^m(id2) = 2
....

Selles näites salvestame globaalselt ^m ühenduvuse maatriksi ja iga sõlme külgnevate (kellega keegi sõbrustab ja sõprade arvu).

Kui graafis on elemente mitte rohkem kui 29 miljonit (see number võetakse 8 * maksimaalne stringi suurus), siis on veelgi ökonoomsem viis selliste maatriksite hoidmiseks — bitijad, kuna nende rakenduses optimeeritakse suurte vahedega spetsiaalselt.

Bitijad manipuleerimise teostab funktsioon $BIT.

; bit'i seadmine
SEA $BIT(rowID, positionID) = 1
; bit'i saamine
Kirjuta $BIT(rowID, positionID)

Lõppautomaatide üleminekute tabel

Kuna lõppautomaatide üleminekute graaf on tavaline graaf, on ka lõppautomaatide üleminekute tabel sama, mis eelpool mainitud külgnevuse maatriks.

Rakendused automaatide

Kõige tuntum rakendusautomaat on mäng "Elu", mis oma reeglite tõttu (kui rakendusel on palju naabreid — see sureb) kujutab endast hõre massiivi.

Steven Wolfram peab rakenduste automaatide olemuseks uue teaduse valdkonnaks. 2002. aastal avaldab ta 1280-leheküljelise raamatu «A New Kind of Science», kus ta laialdaselt argumenteerib, et rakkuautomaadid ei ole eraldiseisvad saavutused, vaid on väga püsivad ja olulised kõigis teaduse valdkondades.

On tõestatud, et iga arvutis töötav algoritm saab rakkuautomaadi kaudu teostatud. Rakkautomaate kasutatakse dünaamiliste keskkondade ja süsteemide modelleerimiseks, algoritmiliste probleemide lahendamiseks ja muudel eesmärkidel.

Kui meil on suur väli ja peame salvestama kõik rakkuautomaadi vahepealsed olekud, on mõistlik kasutada globaale.

Kaardistus

Esimene asi, mis mulle meelde tuleb, kui rääkida haruldaste massiivide kasutamisest, on kaardistamise ülesanded.

Tavaliselt on kaartidel palju tühja ruumi. Kui kaarti kujutada suurte pikslitena, siis 71% Maa pikslitest oleks ookeani katte all. Haruldane massiiv. Ja kui joonistada ainult inimkäte looming, siis on tühja ruumi rohkem kui 95%.

Loomulikult ei hoia keegi kaarte rasterdatana, kasutatakse vektorgraafikat.
Aga mis on vektorkaardid? Need koosnevad raamistikust ning punktidest, polülinetest ja polügoonidest.
Tegelikult on see punktide ja nendevaheliste seoste andmebaas.

Üks ambitsioonikamaid kaardistamise ülesandeid on meie galaksie kaardistamine Gaia teleskoobi abil. Kujundlikult öeldes on meie galaktika, nagu kogu universum, pidev hõre mass: tohutud tühjad ruumid, kus leidub harva väikeseid punkte — tähti. Tühja ruumi on 99,999999…….%. Meie galaktika kaardi salvestamiseks on valitud globaalide andmebaas — Caché.

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

Set ^galaxy(b, l, d) = 1; Tärni number kataloogis, kui see on olemas
Set ^galaxy(b, l, d, "name") = "Päike"
Set ^galaxy(b, l, d, "type") = "tavaline"; variandid: must auk, kvasaari, 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) = "Merkuur"
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 säilitada kõiki vajalikke tähtede ja planeetide omadusi, kuna globaalide alused on skeemivabad (scheme-less).

Meie universumi kaardi hoidmiseks valiti Caché mitte ainult paindlikkuse, vaid ka selle võime tõttu salvestada andmevooge väga kiiresti, samal ajal luues indekseerimise globaalid kiireks otsimiseks.

Kui tagasi Maale tulla, siis on globaalides loodud kaardistamisprojektid OpenStreetMap XAPI ja OpenStreetMapi fork — FOSM.

Hiljuti Caché hackathon'il rakendati georuumilisi indekseid Geospatial. Ootame artikli autoritelt rakenduse üksikasju.

Ruumiliste indeksite rakendamine globaalil OpenStreetMap XAPI

Pildid on saadud selles esituses.

Kogu Maapind jaguneb ruutudeks, siis alakategooriateks ning alakategooriad jaotatakse veelgi. Lõppkokkuvõttes saame hierarhilise struktuuri, mille jaoks on globaalid loodud.

Igal ajal saame peaaegu koheselt nõuda vajalikku ruutu või selle puhastada, samal ajal kui kõik alakategooriad tagastatakse või puhastatakse.

Sarnast skeemi globaalides saab rakendada mitmel viisil.

Variant 1:

Määrake ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idEsimesePunkti
Määrake ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idTeisePunkti
...

Variant 2:

Määrake ^m('abacdabcdabacdabcda', 1) = idEsimesePunkti
Määrake ^m('abacdabcdabacdabcda', 2) = idTeisePunkti
...

Mõlemas olukorras ei ole COS/M-is raskusi nõuda punkte, mis asuvad mistahes taseme ruudis. Esimeses variandis on ruutude tükkide puhastamine mistahes tasemel veidi lihtsam, kuid see on harva vajalik.

Näide ühest madalama taseme ruudust:

Siin on mõned globaalsed objektid projektist XAPI: indeksi esitamine globaalsetes:

Globaal ^way kasutatakse punktide salvestamiseks polüliinide (teed, väiksed jõed jne) ja polügoonide (sulguvad alad: hooned, metsad jne).

Hämmastav klassifikatsioon hõredate massiivide kasutamisest globaalsetes.

1. Me salvestame teatud objektide koordinaadid ja nende seisundid (kaardistamine, rakuautomaatide puhul)
2. Me salvestame hõredaid maatrikseid.

Juhtumi 2 korral, kui nõutakse teatud koordinaati, kus elemendile ei ole väärtust määratud, peame saama hõreda massiivi elemendi vaikeväärtuse.

Boonused, mida me saame, kui salvestame mitmemõõtmelisi maatrikseid globaalsetes

Kiirelt saab eemaldada ja/või valida ruumide osi, mis on jagatud ridade, tasandeid, kuubikute jne järgi. Kohandatud tervete indeksite kasutamisel võib olla kasulik võimalus kiiresti eemaldada ja/või valida ruumide osi, mis on jagatud ridade, tasandeid, kuubikute jne järgi.

Käsk Tappa saame eemaldada nii eraldi elemendi, rea kui ka terve tasandi. Globalide omaduste tõttu toimub see väga kiiresti — tuhandetes kordadest kiiremini kui elementi kaupa eemaldamine.

Joonisel on kujutatud kolme mõõtmega massiivi globaalis ^a ja erinevad eemaldamisviisid.

Ruumide osade valimiseks tuntud indeksite järgi saab kasutada käsku Ühenda.

Veeru valimine maatriksist muutuja Column:

; Määrame kolme mõõtmega 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
Kombineeri Column = ^a(2,2)
; Väljastame muutuja Column
Zwrite Column

Väljund:

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

Huvitaval kombel on muutuja Column samuti saavutanud hõreda massiivi, millele tuleb viidata ka läbi $GET, kuna vaikimisi väärtused selles ei hoitakse.

Ruumide osade valimine võib toimuda ka väikese programmi kaudu, kasutades funktsiooni $Order. See on eriti mugav ruumides, mille indeksid ei ole kvantitud (kaardistamine).

Kokkuvõte

Tänapäeva ajad toovad uusi ambitsioonikaid väljakutseid. Graafid võivad koosneda miljarditest tipudest, kaardid miljarditest punktidest ning keegi võib isegi soovida käivitada omaenda universumi rakenduste põhjal (1, 2).

Kui hajusate massiivide andmemaht ei mahu enam operatiivmälu, kuid nendega tuleb töötada, tuleks kaaluda selliste projektide rakendamist globaalselt ja COS-is.

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

Märkus: Antud artikkel ja minu kommentaarid sellele on minu arvamus ja ei oma seost InterSystems korporatsiooni ametliku positsiooniga.

Allikas: habr.com