Eelmistes osades (, ) rääkisime globaalsetest kui puudest, selles vaatleme globaale kui hõredaid massiive.
on massiivi tüüp, milles enamik väärtusi on sama väärtusega.
Praktikas on hõredad massiivid sageli nii suured, et pole mõtet identsete elementidega mälu hõivata. Seetõttu on mõttekas rakendada hõredaid massiive nii, et mälu ei kulutaks identsete väärtuste salvestamisele.
Mõnes programmeerimiskeeles sisalduvad hõredad massiivid keeles endas, , . Teistel programmeerimiskeeltel on spetsiaalsed teegid, mis võimaldavad teil neid rakendada. C++ jaoks - jne
Globaalid on head kandidaadid hõredate massiivide rakendamiseks, kuna:
- Nad salvestavad ainult teatud sõlmede väärtused ja ei salvesta määratlemata sõlmede väärtusi;
- Sõlme väärtusele juurdepääsu liides on äärmiselt sarnane sellega, kui paljud programmeerimiskeeled võimaldavad juurdepääsu mitmemõõtmelisele massiivi elemendile.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global on andmete salvestamiseks üsna madala tasemega struktuur, seetõttu on sellel silmapaistvad kiirusomadused (sadadest tuhandetest kuni kümnete miljonite tehinguteni sekundis, olenevalt riistvarast, vt allpool). )
Kuna globaalne on püsiv struktuur, on mõttekas luua neile hõredad massiivid, kui on ette teada, et RAM-i mahust ei piisa.
Üks hõreda massiivi rakenduste omadus on tagastada vaikeväärtus, kui juurdepääs tehakse määratlemata lahtrile.
Seda saab rakendada funktsiooni abil COS-is. See näide käsitleb 3-mõõtmelist massiivi.
SET a = $GET(^a(x,y,z), defValue)Millised ülesanded nõuavad hõredaid massiive ja kuidas saavad globaalsed aidata?
Külgnevuse (ühenduvuse) maatriks
kasutatakse graafikute esitamiseks:
Ilmselgelt, mida suurem on graafik, seda rohkem on maatriksis nulle. Kui võtame näiteks sotsiaalvõrgustiku graafiku ja esitame selle sarnase maatriksi kujul, siis koosneb see peaaegu täielikult nullidest, s.t. tuleb 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
....
Selles näites säästame globaalselt ^m ühenduvusmaatriks, samuti iga sõlme servade arv (kes kellega sõber on ja sõprade arv).
Kui elementide arv graafikus ei ületa 29 miljonit (seda arvu võetakse 8 * korrutisena ), see tähendab, et veelgi ökonoomsem viis selliste maatriksite salvestamiseks on bitistringid, kuna nende rakendamine optimeerib suuri lünki erilisel viisil.
Bitistringidega manipuleerimist teostab funktsioon .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Olekumasina üleminekutabel
Kuna lõpliku automaati siirdegraafik on tavaline graaf, siis lõpliku automaati üleminekutabeliks on sama külgnemismaatriks, millest oli juttu eespool.
Rakuautomaadid
Kõige kuulsam rakuautomaat on , mis oma reeglite tõttu (kui lahtril on palju naabreid, siis see sureb) on hõre massiiv.
Stephen Wolfram usub, et rakuautomaadid on . 2002. aastal avaldas ta 1280-leheküljelise raamatu A New Kind of Science, milles ta väidab üldjoontes, et edusammud rakuautomaatide vallas ei ole isoleeritud, vaid on püsivad ja avaldavad suurt mõju kõikidele teadusvaldkondadele.
On tõestatud, et mis tahes arvutis käivitatavat algoritmi saab rakendada mobiilsideautomaati kasutades. Rakuautomaate kasutatakse dünaamiliste keskkondade ja süsteemide modelleerimiseks, algoritmiliste probleemide lahendamiseks ja muudel eesmärkidel.
Kui meil on tohutu väli ja meil on vaja salvestada kõik rakuautomaadi vaheseisundid, siis on mõttekas kasutada globaale.
Kartograafia
Esimene asi, mis mulle hõredate massiivide kasutamisel meelde tuleb, on kaardistamisülesanded.
Reeglina on kaartidel palju tühja ruumi. Kui kaart on kujutatud suurte pikslitena, siis 71% Maa pikslitest hõivab ookean. Hõre massiiv. Ja kui kasutate ainult inimkäte teoseid, on tühi ruum üle 95%.
Muidugi ei salvesta keegi kaarte rastermassiividena, kasutatakse vektorkujutust.
Aga mis on vektorkaardid? See on mingi raam ning punktidest koosnevad polüliinid ja hulknurgad.
Sisuliselt punktide ja nendevaheliste ühenduste andmebaas.
Üks ambitsioonikamaid kaardistamismissioone on Gaia teleskoobi missioon meie galaktika kaardistamiseks. Piltlikult öeldes on meie galaktika, nagu kogu universum, pidev hõre massiiv: tohutud tühjused, milles on haruldased väikesed punktid - tähed. Tühja ruumi on 99,999999…….%. Meie galaktika kaardi salvestamiseks valiti globaalne andmebaas – Caché.
Ma ei tea selle projekti globaalsete täpset struktuuri, võin eeldada, et see on midagi sarnast:
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
...
Kus b, l, d on ja kaugus Päikesest.
Globaalide paindlik struktuur võimaldab salvestada tähtede ja planeetide kõik vajalikud omadused, kuna globaalide baasid on skeemivabad.
Meie universumi kaardi salvestamiseks valiti Caché mitte ainult selle paindlikkuse, vaid ka võime tõttu väga kiiresti andmevoogu talletada, luues samal ajal kiirete otsingute jaoks indeksiglobaale.
Kui pöördume tagasi Maale, siis kartograafilised projektid loodi globaalsetel ja OpenStreetMapi kahvel - .
Hiljuti sisse lülitatud rakendati georuumilisi indekseid . Ootame autoritelt artiklit teostuse üksikasjadega.
Ruumiindeksite juurutamine globaalsel kujul OpenStreetMap XAPI-s
Pildid tehtud alates .
Kogu maakera on jagatud ruutudeks, seejärel alamruutudeks ja alamruudud alamruutudeks jne. Üldiselt saame loodud globaalsete salvestamiseks hierarhilise struktuuri.
Iga hetk saame soovitud ruudu peaaegu koheselt taotleda või selle tühjendada, samuti tagastatakse või tühjendatakse kõik alamruudud.
Sarnast skeemi globaalsetel seadmetel saab rakendada mitmel viisil.
Võimalus 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ВторойТочки
...Võimalus 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Mõlemal juhul pole keeruline kasutada COS/M-i mis tahes tasemega ruudus asuvate punktide taotlemiseks. Esimeses variandis on ruudukujuliste ruumitükkide puhastamine igal tasandil mõnevõrra lihtsam, kuid see on harva vajalik.
Ühe madalama taseme ruudu näide:
Ja siin on mitu XAPI projekti globaalset väärtust: indeksi esitus globaalsetel andmetel:
globaalne ^ viis kasutatakse punktide salvestamiseks (teed, väikesed jõed jne) ja polügoonid (suletud alad: hooned, metsad jne).
Hõredate massiivide kasutamise ligikaudne klassifikatsioon globaalidel.
- Salvestame teatud objektide koordinaadid ja nende olekud (kaardistamine, rakuautomaadid)
- Ladustame hõredaid maatrikseid.
Juhtumi 2 puhul, kui küsitakse konkreetset koordinaati, kus elemendile väärtust ei omistata, peame saama vaikimisi hõreda massiivi elemendi väärtuse.
Boonused, mida saame mitmemõõtmeliste maatriksite globaalsesse salvestamisel
Eemaldage ja/või valige kiiresti ridade, tasapindade, kuubikute jne mitmekordsed ruumiosad. Juhtudel, kui kasutatakse täisarvu indekseid, võib olla kasulik võimalus kiiresti eemaldada ja/või tuua ruumi tükke, mis on ridade, tasapindade, kuubikute jne kordsed.
meeskond saame kustutada kas üksiku elemendi või rea või isegi terve tasapinna. Tänu globaalsete omadustele toimub see väga kiiresti – tuhandeid kordi kiiremini kui elemendihaaval eemaldamine.
Joonisel on kujutatud globaalses kolmemõõtmeline massiiv ^a ja erinevat tüüpi kustutamised.
Ruumitükkide valimiseks tuntud indeksite abil saate kasutada käsku .
Maatriksi veeru valimine muutujasse 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
Järeldus:
Column(0)=1
Column(2)=1
Muutuja Column juures on huvitav see, et meil on ka hõre massiiv, millele tuleb samuti juurde pääseda , kuna vaikeväärtusi sellesse ei salvestata.
Ruumi tükkide valimist saab teha ka väikese programmi kaudu, kasutades funktsiooni . See on eriti mugav ruumide puhul, mille indeksid ei ole kvantiseeritud (kartograafia).
Järeldus
Praegune aeg seab uued ambitsioonikad ülesanded. Graafikud võivad koosneda miljarditest tippudest, kaardid miljarditest punktidest ja mõned võivad isegi soovida käivitada oma universumi rakuautomaatide peal (, ).
Kui hõredate massiivide andmemaht ei mahu enam RAM-i, kuid peate nendega töötama, tasub kaaluda võimalust rakendada sarnaseid projekte globaalsetel ja COS-itel.
Täname tähelepanu eest! Ootame teie küsimusi ja soove kommentaaridesse.
Kaebused: See artikkel ja minu kommentaarid sellele on minu arvamus ega ole seotud InterSystems Corporationi ametliku seisukohaga.
Allikas: www.habr.com