V předchozích částech (, ) jsme hovořili o globálech jako o stromech, v této části se zaměříme na globály jako na řídké pole.
je specializovaný typ pole, ve kterém většina hodnot nabývá stejné hodnoty.
V praxi se často setkáváme s tak obrovskými řídkými poli, že nemá smysl zbytečně zabírat paměť stejnými prvky. Proto má smysl implementovat řídká pole tak, aby paměť nebyla využívána na uchovávání stejných hodnot.
V některých programovacích jazycích jsou řídká pole součástí jazyka, , . V jiných programovacích jazycích existují speciální knihovny, které umožňují jejich implementaci. Pro C++ — atd.
Globály jsou dobrými kandidáty pro implementaci řídkých polí, protože:
- Ukládají hodnoty pouze určitých uzlů a neukládají hodnoty neznámých;
- Rozhraní pro přístup k hodnotě uzlu je velmi podobné způsobu, jakým je v mnoha programovacích jazycích implementován přístup k prvku vícerozměrného pole.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Globál je dostatečně nízkoúrovňová struktura pro ukládání dat, proto má vynikající rychlostní charakteristiky (od stovek tisíc po desítky milionů transakcí za sekundu v závislosti na hardwaru, viz. )
Jelikož je globál perzistentní struktura, dává smysl vytvářet řídká pole na nich, když je předem známo, že objem operační paměti bude nedostatečný.
Jedním z vlastností implementací řídkých polí je vracení určité výchozí hodnoty, pokud se přistupuje k neznámé buňce.
To lze implementovat pomocí funkce v COS. V tomto příkladu je uvedeno 3D pole.
SET a = $GET(^a(x,y,z), defValue)V jakých úlohách jsou tedy řídká pole potřebná a jak mohou globály pomoct?
Matice sousednosti (spojenosti)
se používají k reprezentaci grafů:
Je zřejmé, že čím větší je graf, tím více nul bude v matici. Pokud například vezmeme graf sociální sítě a představíme si jej ve formě podobné matice, bude téměř celý tvořen nulami, tj. bude řídkým polem.
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 příkladu uchováváme v globálu ^m matice spojení a také počet hran u každého uzlu (kdo s kým přátelí a počet přátel).
Pokud je však počet prvků v grafu maximálně 29 milionů (toto číslo je bráno jako součin 8 * ), existuje ještě úspornější způsob ukládání takových matic — bitové řetězce, protože se jejich realizací speciálně optimalizují velké mezery.
Manipulace s bitovými řetězci se provádí funkcí .
; nastavení bitu
SET $BIT(rowID, positionID) = 1
; získání bitu
Write $BIT(rowID, positionID)
Tabulka přechodů konečného automatu
Protože graf přechodů konečného automatu je obyčejný graf, tabulka přechodů konečného automatu je také stejná matice sousednosti, o které se hovořilo výše.
Herní automaty
Nejznámější herní automat — , která díky svým pravidlům (když má buňka mnoho sousedů — umírá) představuje řídké pole.
Stephen Wolfram tvrdí, že herní automaty jsou . V roce 2002 vydává 1280stránkovou knihu „A New Kind of Science“, kde široce argumentuje, že úspěchy v oblasti herních automatů nejsou izolované, ale jsou velmi stabilní a mají velký význam pro všechny oblasti vědy.
Bylo prokázáno, že jakýkoli algoritmus proveditelný na počítači lze realizovat prostřednictvím herního automatu. Herní automaty se používají k modelování dynamických prostředí a systémů, k řešení algoritmických úloh a k dalším účelům.
Pokud máme obrovské pole a potřebujeme zaznamenávat všechny mezistavy herního automatu, je rozumné použít globální proměnné.
Kartografie
První, co mě napadne, když se hovoří o využití řídkých polí, jsou kartografické úkoly.
Jak je známo, na mapách je hodně prázdného prostoru. Pokud bychom mapu zobrazovali ve velkých pixelech, 71% pixelů Země by bylo obsazeno oceánem. Řídké pole. A pokud bychom zakreslovali pouze díla lidských rukou, prázdného prostoru by bylo více než 95%.
Samozřejmě, že nikdo neukládá mapy jako rastrová pole, používá se vektorové znázornění.
Ale co vlastně vektorové mapy představují? To je jakási kostra a z bodů složené polylinie a mnohoúhelníky.
Fakticky je to databáze bodů a vazeb mezi nimi.
Jedním z nejambicióznějších úkolů mapování je mise mapování naší galaxie teleskopem Gaia. Metaforicky řečeno, naše galaxie, stejně jako celé vesmír, je jednolitým řídkým polem: obrovské prostory prázdnoty, ve kterých se nacházejí vzácné malé body — hvězdy. Prázdného místa je 99,999999…….%. Pro ukládání mapy naší galaxie byla zvolena databáze na globálech — Caché.
Nevím přesnou strukturu globálů v tomto projektu, mohu se domnívat, že je to něco podobného:
Set ^galaxy(b, l, d) = 1; Číslo hvězdy podle katalogu, pokud existuje
Set ^galaxy(b, l, d, "name") = "Slunce"
Set ^galaxy(b, l, d, "type") = "normální" ; varianty blackhole, quazar, red_dwarf atd.
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
...
Kde b, l, d — to jsou a vzdálenost od Slunce.
Flexibilní struktura globálů umožňuje udržovat jakékoli potřebné charakteristiky hvězd a planet, protože databáze na globálech jsou bezschémové (scheme-less).
Pro ukládání mapy naší vesmíru byla Caché vybrána nejen kvůli flexibilitě, ale i schopnosti velmi rychle ukládat tok dat, přičemž zároveň vytvářela indexové globály pro rychlé vyhledávání.
Pokud se vrátíme na Zemi, byly na globálech vytvořeny kartografické projekty a fork OpenStreetMap — .
Nedávno na byly realizovány geospatiální indexy . Čekáme od autorů článku podrobnosti o realizaci.
Realizace prostorových indexů na globálu v OpenStreetMap XAPI
Obrázky jsou převzaty z .
Celá zeměkoule je rozdělena na čtverce, pak na podčtverce a podčtverce na pod-podčtverce a tak dále. Obecně dostáváme hierarchickou strukturu, pro jejíž uchovávání byly vytvořeny globály.
V jakémkoli okamžiku můžeme prakticky okamžitě požadovat potřebný čtverec, nebo ho vyčistit, přičemž všechny podčtverce budou také vráceny nebo vyčištěny.
Podobnou schéma na globálech lze realizovat několika způsoby.
Varianta 1:
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 1) = idPrvníBod
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 2) = idDruhýBod
...Varianta 2:
Set ^m('abacdabcdabacdabcda', 1) = idPrvníBod
Set ^m('abacdabcdabacdabcda', 2) = idDruhýBod
...V obou případech není problém žádat o body umístěné v čtverci jakékoli úrovně na COS/M. O něco snazší bude čistit čtvercové úseky prostoru jakékoli úrovně v prvním variantě, ale to je zřídka potřeba.
Příklad jednoho z čtverců nejnižší úrovně:
A zde je několik globálů z projektu XAPI: zobrazení indexu na globálech:
Globál ^way se používá k ukládání bodů (silnice, drobné řeky atd.) a polygonů (uzavřené oblasti: budovy, lesy atd.).
Hrubá klasifikace využití řídkých polí na globálech.
- Ukládáme souřadnice určitých objektů a jejich stavy (mapování, buněčné automaty)
- Ukládáme řídké matice.
V případě 2) při dotazu na konkrétní souřadnici, kde prvku není přiřazena hodnota, bychom měli obdržet výchozí hodnotu prvku řídkého pole.
Bonusy, které získáváme při ukládání vícerozměrných matic na globálech
Rychlé odstranění a/nebo výběr úseků prostoru násobků řádků, rovin, kostek atd. Pro případy, kdy se používají celočíselné indexy, se může ukázat jako užitečná možnost rychlého odstranění a/nebo výběru úseků prostoru násobků řádků, rovin, kostek atd.
Příkazem můžeme odstranit jak jednotlivý prvek, tak i řádek a dokonce celou rovinu. Díky vlastnostem globálů to probíhá velmi rychle — tisíckrát rychleji než poelementové odstranění.
Na obrázku je znázorněna trojrozměrná matice v globálu ^a a různé druhy odstranění.
Pro výběr úseků prostoru podle známých indexů lze použít příkaz .
Výběr sloupce matice do proměnné Column:
; Definujeme trojrozměrné řídké pole 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)
; Zobrazíme proměnnou Column
Zwrite Column
Výstup:
Column(0)=1
Column(2)=1
Co je zajímavé, že v proměnné Column máme také řídkou matici, k níž je třeba přistupovat také přes , protože v ní nejsou uloženy výchozí hodnoty.
Výběr úseků prostoru může být také prováděn prostřednictvím malé aplikace s využitím funkce . To je obzvláště pohodlné v prostorech, jejichž indexy nejsou kvantizovány (mapování).
Závěr
Současná doba klade nové ambiciózní úkoly. Grafy mohou mít miliardy vrcholů, mapy miliardy bodů a někdo si dokonce může přát spustit svůj vlastní vesmír na buněčných automatech (, ).
Když objem dat řídkých polí již nemůže být umístěn do operační paměti a je třeba s nimi pracovat, stojí za zvážení realizace takových projektů na globálních a COS.
Děkujeme za pozornost! Těšíme se na vaše otázky a přání v komentářích.
Poznámka: Tento článek a mé komentáře k němu představují můj názor a nemají nic společného s oficiálním postojem společnosti InterSystems.
Zdroj: habr.com
