V predchádzajúcich častiach (, ) sme hovorili o globáloch ako stromoch, v tomto sa pozrieme na globály ako na riedke polia.
je typ poľa, v ktorom má väčšina hodnôt rovnakú hodnotu.
V praxi sú riedke polia často také obrovské, že nemá zmysel obsadzovať pamäť rovnakými prvkami. Preto má zmysel implementovať riedke polia takým spôsobom, aby sa neplytvala pamäťou na ukladanie rovnakých hodnôt.
V niektorých programovacích jazykoch sú riedke polia zahrnuté v samotnom jazyku, , . Ostatné programovacie jazyky majú špeciálne knižnice, ktoré vám umožňujú implementovať ich. Pre C++ - et al.
Globálne sú dobrými kandidátmi na implementáciu riedkych polí, pretože:
- Ukladajú hodnoty iba určitých uzlov a neukladajú hodnoty nedefinovaných;
- Rozhranie pre prístup k hodnote uzla je veľmi podobné tomu, koľko programovacích jazykov implementuje prístup k viacrozmernému prvku poľa.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Globálna je pomerne nízkoúrovňová štruktúra na ukladanie údajov, preto má vynikajúce rýchlostné charakteristiky (od stoviek tisíc až po desiatky miliónov transakcií za sekundu, v závislosti od hardvéru, pozri nižšie). )
Keďže globálne je perzistentná štruktúra, má zmysel vytvárať na nich riedke polia, keď je vopred známe, že množstvo pamäte RAM nebude stačiť.
Jednou z vlastností implementácií riedkych polí je vrátiť nejakú predvolenú hodnotu, ak sa uskutoční prístup k nedefinovanej bunke.
Toto je možné implementovať pomocou funkcie v COS. Tento príklad uvažuje 3-rozmerné pole.
SET a = $GET(^a(x,y,z), defValue)Aké úlohy vyžadujú riedke polia a ako môžu pomôcť globálne?
Matica susednosti (konektivity).
používa sa na znázornenie grafov:
Je zrejmé, že čím väčší je graf, tým viac núl bude v matici. Ak napríklad vezmeme graf sociálnej siete a predložíme ho vo forme podobnej matice, potom bude takmer celý pozostávať z núl, t.j. bude riedke pole.
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 šetríme globálne ^m maticu konektivity, ako aj počet hrán v každom uzle (kto sa s kým kamaráti a počet priateľov).
Ak počet prvkov v grafe nie je väčší ako 29 miliónov (toto číslo sa považuje za súčin 8 * ), čiže ešte ekonomickejším spôsobom ukladania takýchto matíc sú bitové reťazce, pretože ich implementácia špeciálnym spôsobom optimalizuje veľké medzery.
Manipulácie s bitovými reťazcami vykonáva funkcia .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabuľka prechodu stavového stroja
Pretože prechodový graf konečného automatu je obyčajný graf, potom prechodová tabuľka konečného automatu je rovnaká matica susednosti, o ktorej sme hovorili vyššie.
Bunkové automaty
Najznámejší celulárny automat je , ktoré je vďaka svojim pravidlám (keď má bunka veľa susedov, odumrie) riedke pole.
Stephen Wolfram verí, že bunkové automaty sú . V roku 2002 vydal 1280-stranovú knihu A New Kind of Science, v ktorej široko tvrdí, že pokroky v celulárnych automatoch nie sú izolované, ale sú trvalé a majú veľké dôsledky pre všetky oblasti vedy.
Bolo dokázané, že pomocou mobilného automatu je možné implementovať akýkoľvek algoritmus spustiteľný na počítači. Bunkové automaty sa používajú na modelovanie dynamických prostredí a systémov, na riešenie algoritmických problémov a na iné účely.
Ak máme obrovské pole a potrebujeme zaznamenať všetky medzistavy bunkového automatu, potom má zmysel použiť globály.
Kartografia
Prvá vec, ktorá mi napadne pri používaní riedkych polí, je mapovanie úloh.
Na mapách je spravidla veľa prázdneho miesta. Ak je mapa znázornená ako veľké pixely, potom 71 % pixelov Zeme bude zaberať oceán. Riedke pole. A ak použijete iba diela ľudských rúk, potom bude prázdny priestor viac ako 95%.
Samozrejme, nikto neukladá mapy vo forme rastrových polí, používa sa vektorové zobrazenie.
Ale čo sú vektorové mapy? Toto je druh rámca a lomených čiar a polygónov pozostávajúcich z bodov.
V podstate databáza bodov a spojení medzi nimi.
Jednou z najambicióznejších mapovacích misií je misia Gaia Telescope na mapovanie našej galaxie. Obrazne povedané, naša galaxia, rovnako ako celý vesmír, je súvislé riedke pole: obrovské priestory prázdnoty, v ktorých sú vzácne malé body – hviezdy. Prázdne miesto je 99,999999……. %. Na uloženie mapy našej galaxie bola zvolená globálna databáza – Caché.
Nepoznám presnú štruktúru globalov v tomto projekte, môžem predpokladať, že je to niečo podobné ako:
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
...
Kde sú b, l, d a vzdialenosť od Slnka.
Flexibilná štruktúra globálov vám umožňuje uložiť všetky potrebné charakteristiky hviezd a planét, pretože základne globálov sú bez schém.
Na uloženie mapy nášho vesmíru bola Caché vybraná nielen pre jej flexibilitu, ale aj pre jej schopnosť veľmi rýchlo ukladať tok údajov a súčasne vytvárať indexové globály pre rýchle vyhľadávanie.
Ak sa vrátime na Zem, tak kartografické projekty vznikli na globáloch a rozvetvenie OpenStreetMap - .
Nedávno boli implementované geopriestorové indexy . Čakáme na článok od autorov s detailmi implementácie.
Implementácia priestorových indexov na globále v OpenStreetMap XAPI
Obrázky prevzaté z .
Celá zemeguľa je rozdelená na štvorce, potom podštvorce a podštvorce na podštvorce atď. Vo všeobecnosti dostaneme hierarchickú štruktúru na uloženie, ktoré globály sú vytvorené.
V každom okamihu môžeme takmer okamžite požiadať o požadovaný štvorec alebo ho vyčistiť a všetky podštvorce budú tiež vrátené alebo vymazané.
Podobná schéma na globáloch môže byť implementovaná niekoľkými spôsobmi.
Možnosť 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žnosť 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...V oboch prípadoch nie je ťažké použiť COS/M na vyžiadanie bodov umiestnených v štvorci akejkoľvek úrovne. V prvej možnosti bude o niečo jednoduchšie vyčistiť štvorcové kusy priestoru na akejkoľvek úrovni, ale je to zriedka potrebné.
Príklad jedného zo štvorcov nižšej úrovne:
A tu je niekoľko globálov z projektu XAPI: reprezentácia indexu na globály:
globálne ^ spôsob slúži na ukladanie bodov (cesty, malé rieky atď.) a polygóny (uzavreté oblasti: budovy, lesy atď.).
Hrubá klasifikácia použitia riedkych polí na globáloch.
- Ukladáme súradnice určitých objektov a ich stavy (mapovanie, bunkové automaty)
- Ukladáme riedke matrice.
Pre prípad 2) pri požiadavke na konkrétnu súradnicu, kde prvku nie je priradená hodnota, musíme získať hodnotu predvoleného prvku riedkeho poľa.
Bonusy, ktoré dostávame pri ukladaní viacrozmerných matíc v globáloch
Rýchlo odstráňte a/alebo vyberte časti priestoru, ktoré sú násobkami riadkov, rovín, kociek atď. V prípadoch, keď sa používajú celočíselné indexy, môže byť užitočná schopnosť rýchlo odstrániť a/alebo načítať časti priestoru, ktoré sú násobkami riadkov, rovín, kociek atď.
tím môžeme odstrániť buď jeden prvok alebo riadok, alebo dokonca celú rovinu. Vďaka vlastnostiam globals sa to deje veľmi rýchlo – tisíckrát rýchlejšie ako odstraňovanie prvku po prvku.
Obrázok ukazuje trojrozmerné pole v globále ^a a rôzne typy vymazaní.
Ak chcete vybrať časti priestoru pomocou známych indexov, môžete použiť príkaz .
Výber stĺpca matice do premennej 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
Záver:
Column(0)=1
Column(2)=1
Na premennej Column je zaujímavé to, že máme aj riedke pole, ku ktorému je potrebné pristupovať aj cez , pretože v ňom nie sú uložené predvolené hodnoty.
Výber kúskov priestoru je možné vykonať aj prostredníctvom malého programu pomocou funkcie . Toto je obzvlášť výhodné v priestoroch, ktorých indexy nie sú kvantované (kartografia).
Záver
Súčasná doba kladie nové ambiciózne úlohy. Grafy sa môžu skladať z miliárd vrcholov, mapy z miliárd bodov a niektorí dokonca môžu chcieť spustiť svoj vlastný vesmír na celulárnych automatoch (, ).
Keď sa objem dát z riedkych polí už nezmestí do RAM, ale potrebujete s nimi pracovať, potom stojí za zváženie možnosť implementácie podobných projektov na globaloch a COS.
Ďakujem za tvoju pozornosť! Čakáme na vaše otázky a želania v komentároch.
Vylúčenie zodpovednosti: Tento článok a moje komentáre k nemu sú mojím názorom a nesúvisia s oficiálnym stanoviskom InterSystems Corporation.
Zdroj: hab.com