V predchádzajúcich častiach (, ) sme hovorili o globáloch ako o stromoch, v tejto sa pozrieme na globály ako na riedke polia.
je špeciálny typ poľa, v ktorom väčšina hodnôt má rovnakú hodnotu.
V praxi sa často stretávame s tak obrovskými riedkymi poliami, že nemá zmysel zaberanie pamäte rovnakými prvkami. Preto má zmysel implementovať riedke polia tak, aby sa šetřila pamäť na uchovávanie rovnakých hodnôt.
V niektorých programovacích jazykoch sú riedke polia súčasťou samotného jazyka, , V iných programovacích jazykoch existujú špeciálne knižnice, ktoré umožňujú ich implementáciu. Pre C++ — a ďalšie.
Globály sú dobrými kandidátmi na implementáciu riedkych polí, pretože:
- Ukladajú hodnoty iba určitých uzlov a neukladajú hodnoty neurčených;
- Prístupové rozhranie k hodnote uzla je extrémne podobné tomu, ako je v mnohých programovacích jazykoch implementovaný prístup k prvku viacdimenziálnych polí.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global je dostatočne nízkoúrovňová štruktúra na uchovávanie dát, preto má vynikajúce rýchlostné charakteristiky (stovky tisíc až desiatky miliónov transakcií za sekundu v závislosti od hardvéru, pozri. )
Keďže global je perzistentná štruktúra, má zmysel vytvárať riedke polia, keď je vopred známe, že objem operačnej pamäte bude nedostatočný.
Jednou z vlastností implementácií riedkych polí je návrat určitej predvolenej hodnoty, ak je prístup k neurčenej bunke.
To je možné realizovať použitím funkcie v COS. V tomto príklade je zobrazené 3-dimenzionálne pole.
SET a = $GET(^a(x,y,z), defValue)Na aké úlohy sú potrebné riedke polia a ako môžu globály pomôcť?
Matica susednosti (prepojenosti)
sa používajú na reprezentáciu grafov:
Je zrejmé, že čím väčší je graf, tým viac núl bude v matici. Ak by sme napríklad zobrali graf sociálnej siete a predstavili ho v podobe takejto matice, tak by sa takmer celý skladal z núl, t.j. by bol riedkym poľom.
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 tomto príklade uchovávame v globále ^m maticu súvislosti, ako aj počet hrán pre každý uzol (kto s kým je priateľ a počet priateľov).
Ak je však počet prvkov v grafe maximálne 29 miliónov (toto číslo sa berie ako súčin 8 * ), existuje ešte ekonomickejší spôsob uchovávania takýchto matíc — bitové reťazce, pretože v ich realizácii sú špeciálnym spôsobom optimalizované veľké prázdne miesta.
Manipulácie s bitovými reťazcami sa vykonávajú funkciou .
; nastavenie bitu
SET $BIT(rowID, positionID) = 1
; získanie bitu
Write $BIT(rowID, positionID)
Tabuľka prechodov konečného automatu
Keďže graf prechodov konečného automatu je obyčajný graf, tabuľka prechodov konečného automatu je vlastne tá istá matica susednosti, o ktorej sme hovorili vyššie.
Kryštálové automaty
Najznámejší kryštálový automat — , ktorá kvôli svojim pravidlám (keď má bunka veľa susedov — umiera) predstavuje riedky pole.
Stephen Wolfram považuje kryštálové automaty za . V roku 2002 vydáva 1280-stranovú knihu 'A New Kind of Science', kde široko argumentuje, že dosiahnutia v oblasti kryštálových automatov nie sú izolované, ale sú veľmi stabilné a majú veľký význam pre všetky oblasti vedy.
Dokázalo sa, že každý algoritmus vykonateľný na počítači môže byť realizovaný prostredníctvom kryštálového automatu. Kryštálové automaty sa používajú na modelovanie dynamických prostredí a systémov, na riešenie algoritmických úloh a iné účely.
Ak máme obrovské pole a potrebujeme zapisovať všetky medziľahlé stavy kryštálového automatu, je celkom rozumné používať globále.
Kartografia
Prvá vec, ktorá mi napadne, keď sa hovorí o používaní riedkych polí — sú to kartografické úlohy.
Na mapách je spravidla veľmi veľa prázdneho priestoru. Ak by sme mapu zobrazovali ako veľké pixely, 71 % pixelov Zeme by bolo obsadených oceánom. Riedke pole. A ak by sme znázornili iba dielo ľudských rúk, prázdneho priestoru by bolo viac ako 95 %.
Samozrejme, nikto neuchováva mapy vo forme rastrových polí, používa sa vektorové zobrazenie.
Čo sú vektorové mapy? To je rámec pozostávajúci z bodov, polylínie a polygónov.
Fakticky je to databáza bodov a vzťahov medzi nimi.
Jednou z najambicióznejších úloh mapovania je misia mapovania našej galaxie teleskopom Gaia. Obrazne povedané, naša galaxia, rovnako ako celý vesmír, je hustý rozptýlený priestor: obrovské prázdne miesta s rozptýlenými malými bodmi — hviezdami. Prazdnoty je 99,999999…….%. Pre uloženie mapy našej galaxie bola vybraná databáza na globáloch — Caché.
Neviem presnú štruktúru globálov v tomto projekte, môžem predpokladať, že je to niečo ako:
Set ^galaxy(b, l, d) = 1; Číslo hviezdy podľa katalógu, ak existuje
Set ^galaxy(b, l, d, "name") = "Slnko"
Set ^galaxy(b, l, d, "type") = "normal" ; varianty blackhole, quasar, red_dwarf atď.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Merkúr"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Kde b, l, d — to sú a vzdialenosť od Slnka.
Flexibilná štruktúra globálov umožňuje ukladať akékoľvek potrebné charakteristiky hviezd a planét, pretože databázy na globáloch sú bez schémy (scheme-less).
Pre uloženie mapy nášho vesmíru bol Caché vybraný nielen kvôli flexibilite, ale aj schopnosti veľmi rýchlo ukladať prúd dát a súčasne vytvárať indexové globály pre rýchle vyhľadávanie.
Ak sa však vrátime na Zem, na globáloch boli vytvorené kartografické projekty a fork OpenStreetMap — .
Nedávno na boli implementované geografické indexy . Čakáme od autorov článku detaily implementácie.
Implementácia priestorových indexov na globáli v OpenStreetMap XAPI
Obrázky sú prevzaté z .
Celá zemská guľa je rozdelená na kocky, potom na podkocky a podkocky zase na menšie podkocky a tak ďalej. V podstate dostávame hierarchickú štruktúru, na ktorú boli globály vytvorené.
V akomkoľvek momente môžeme prakticky okamžite požiadať o potrebnú kocku alebo ju vyčistiť, pričom všetky podkocky tiež budú vrátené alebo vyčistené.
Podobnú schému na globáloch je možné uskutočniť niekoľkými spôsobmi.
Varianta 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idPrvejBod
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idDruhejBod
...Varianta 2:
Nastavte ^m('abacdabcdabacdabcda', 1) = idPrvejBodky
Nastavte ^m('abacdabcdabacdabcda', 2) = idDruhejBodky
...V oboch prípadoch nie je ťažké na COS/M požadovať body nachádzajúce sa v štvorci akejkoľvek úrovne. O niečo jednoduchšie bude čistiť štvorcové úseky priestoru akejkoľvek úrovne v prvom variante, ale to sa zriedka vyžaduje.
Príklad jedného z štvorčekov dolnej úrovne:
A tu je niekoľko globálov z projektu XAPI: reprezentácia indexu na globáloch:
Globál ^way používa sa na uchovávanie bodov (ciest, malých riek a pod.) a polygónov (uzavreté oblasti: budovy, lesy a pod.).
Hrubá klasifikácia využitia riedkych matíc na globáloch.
- Ukladáme súradnice určitých objektov a ich stavy (mapovanie, bunkové automaty)
- Ukladáme riedke matice.
Pre prípad 2) pri dopyte určitej súradnice, kde prvku nebolo pridelené hodnotu, by sme mali získať hodnotu prvku riedkeho poľa predvolene.
Bonifikácie, ktoré získavame pri ukladaní viacrozmerných matíc na globáloch
Rýchle odstraňovanie a/alebo výber úsekov priestoru, násobných riadkom, rovinám, kockám a pod. Pre prípady, keď sú použité celistvé indexy, môže byť užitočná možnosť rýchleho odstraňovania a/alebo výberu úsekov priestoru, násobných riadkom, rovinám, kockám a pod.
Príkazom môžeme odstrániť ako jednotlivý prvok, tak aj riadok, a dokonca celú rovinu. Vďaka vlastnostiam globálov sa to deje veľmi rýchlo — tisíckrát rýchlejšie, než poelementové odstraňovanie.
Na obrázku je znázornená trojrozmerná matica v globále ^a a rôzne druhy odstraňovania.
Na výber úsekov priestoru podľa známych indexov možno použiť príkaz .
Výber stĺpca matice do premennej Column:
; Nastavíme trojrozmernú riedku maticu 3x3x3
Nastavte ^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
Zlúčiť Stĺpec = ^a(2,2)
; Vytlačíme premennú Stĺpec
Zwrite Stĺpec
Výstup:
Stĺpec(0)=1
Stĺpec(2)=1
Zaujímavé je, že v premennej Stĺpec sa nám tiež vytvoril riedky poľ, ku ktorému je potrebné pristupovať tiež cez , pretože predvolené hodnoty v ňom nie sú uložené.
Výber úsekov priestoru sa môže tiež robiť prostredníctvom malého programu s využitím funkcie . To je osobitne pohodlné na priestoroch, ktorých indexy nie sú kvantované (kartografia).
Záver
Súčasné časy kladú nové ambiciózne úlohy. Grafy môžu obsahovať miliardy vrcholov, mapy miliardy bodov a niekto môže dokonca chcieť spustiť svoju vlastnú univerzum na základných automatoch (, ).
Keď objem dát rozptýlených polí už nemôže byť umiestnený v operačnej pamäti a je potrebné s nimi pracovať, mali by ste zvážiť realizáciu takýchto projektov na globáloch a COS.
Ďakujeme za pozornosť! Tešíme sa na vaše otázky a priania v komentároch.
Upozornenie: tento článok a moje komentáre k nemu sú môj názor a nemajú nič spoločné s oficiálnym stanoviskom korporácie InterSystems.
Zdroj: habr.com
