Globals jsou meče pokladů pro ukládání dat. Řídká pole. Část 3

V předchozích dílech (1, 2) jsme mluvili o globalech jako stromech, v tomto se podíváme na globaly jako na řídká pole.

Řídké pole je typ pole, ve kterém má většina hodnot stejnou hodnotu.

V praxi jsou řídká pole často tak obrovská, že nemá smysl zabírat paměť stejnými prvky. Proto má smysl implementovat řídká pole takovým způsobem, aby nedocházelo k plýtvání pamětí na ukládání identických hodnot.
V některých programovacích jazycích jsou řídká pole součástí samotného jazyka, například v J, MATLAB. Jiné programovací jazyky mají speciální knihovny, které vám je umožňují implementovat. Pro C++ - Vlastní et al.

Globals jsou dobrými kandidáty pro implementaci řídkých polí, protože:

1. Ukládají hodnoty pouze určitých uzlů a neukládají hodnoty nedefinovaných;
2. Rozhraní pro přístup k hodnotě uzlu je velmi podobné tomu, kolik programovacích jazyků implementuje přístup k prvku vícerozměrného pole.

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

3. Global je poměrně nízkoúrovňová struktura pro ukládání dat, proto má vynikající rychlostní charakteristiky (od stovek tisíc až po desítky milionů transakcí za sekundu, v závislosti na hardwaru, viz níže). 1)

Vzhledem k tomu, že globální je trvalá struktura, má smysl na nich vytvářet řídká pole, když je předem známo, že množství paměti RAM nebude stačit.

Jednou z vlastností implementací řídkého pole je vrátit nějakou výchozí hodnotu, pokud je proveden přístup k nedefinované buňce.

To lze implementovat pomocí funkce $GET v COS. Tento příklad uvažuje 3-rozměrné pole.

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

Jaké úlohy vyžadují řídká pole a jak mohou pomoci globální?

Matice sousedství (konektivity).

Takové matrice používá se k reprezentaci grafů:

Je zřejmé, že čím větší je graf, tím více nul bude v matici. Vezmeme-li například graf sociální sítě a předložíme jej ve formě podobné matice, pak se bude téměř celý skládat z nul, tzn. bude řídké 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 příkladu ušetříme globálně ^m matice konektivity a také počet hran v každém uzlu (kdo se s kým přátelí a počet přátel).

Pokud počet prvků v grafu není větší než 29 milionů (toto číslo se bere jako součin 8 * maximální velikost řádku), to znamená, že ještě ekonomičtějším způsobem uložení takových matic jsou bitové řetězce, protože jejich implementace speciálním způsobem optimalizuje velké mezery.

Manipulace s bitovými řetězci provádí funkce $ BIT.

; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)

Tabulka přechodů stavového stroje

Protože přechodový graf konečného automatu je obyčejný graf, pak přechodová tabulka konečného automatu je stejná matice sousednosti, o níž jsme pojednávali výše.

Buněčné automaty

Nejznámějším buněčným automatem je hra "život", které je díky svým pravidlům (když má buňka mnoho sousedů, zemře) řídké pole.

Stephen Wolfram věří, že celulární automaty jsou nový vědní obor. V roce 2002 vydal 1280stránkovou knihu A New Kind of Science, ve které široce argumentuje, že pokroky v buněčných automatech nejsou izolované, ale jsou trvalé a mají velké důsledky pro všechny oblasti vědy.

Bylo prokázáno, že pomocí celulárního automatu lze implementovat jakýkoli algoritmus spustitelný na počítači. Buněčné automaty se používají k modelování dynamických prostředí a systémů, k řešení algoritmických problémů a pro jiné účely.

Pokud máme obrovské pole a potřebujeme zaznamenat všechny mezistavy buněčného automatu, pak má smysl používat globály.

Kartografie

První věc, která mě napadne, když přijde na používání řídkých polí, je mapování úloh.

Na mapách je zpravidla hodně prázdného místa. Pokud je mapa znázorněna jako velké pixely, pak 71 % pixelů Země zabere oceán. Řídké pole. A pokud použijete pouze díla lidských rukou, pak bude prázdný prostor více než 95%.

Nikdo samozřejmě neukládá mapy ve formě rastrových polí, používá se vektorové znázornění.
Ale co jsou vektorové mapy? Jedná se o druh rámce a křivek a polygonů skládajících se z bodů.
V podstatě databáze bodů a spojení mezi nimi.

Jednou z nejambicióznějších mapovacích misí je mise Gaia Telescope, která má zmapovat naši galaxii. Obrazně řečeno, naše galaxie, stejně jako celý vesmír, je souvislá řídká soustava: obrovské prostory prázdnoty, ve kterých jsou vzácné malé body – hvězdy. Prázdné místo je 99,999999……. %. Pro uložení mapy naší galaxie byla vybrána globální databáze – Caché.

Neznám přesnou strukturu globalů v tomto projektu, mohu předpokládat, že je to něco podobného:

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 jsou b, l, d galaktické souřadnice zeměpisná šířka, délka a vzdálenost ke Slunci.

Flexibilní struktura globálů vám umožňuje ukládat jakékoli nezbytné charakteristiky hvězd a planet, protože základny na globálech jsou bez schématu.

Pro uložení mapy našeho vesmíru bylo Caché vybráno nejen pro svou flexibilitu, ale také pro svou schopnost velmi rychle ukládat proud dat a současně vytvářet indexové globály pro rychlé vyhledávání.

Pokud se vrátíme na Zemi, tak kartografické projekty vznikly na globálech OpenStreetMap XAPI a větev OpenStreetMap - FOSM.

Nedávno na hackathon Caché byly implementovány geoprostorové indexy Geospatial. Čekáme na článek od autorů s detaily implementace.

Implementace prostorových indexů na globální v OpenStreetMap XAPI

Obrázky převzaty z tuto prezentaci.

Celá zeměkoule je rozdělena na čtverce, pak podčtverce a podčtverce na podčtverce a tak dále. Obecně získáme hierarchickou strukturu pro ukládání, které globaly jsou vytvořeny.

V každém okamžiku můžeme téměř okamžitě požádat o požadovaný čtverec nebo jej vymazat a všechny podčtverce budou také vráceny nebo vymazány.

Podobné schéma na globálech lze implementovat několika způsoby.

Možnost 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žnost 2:

Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...

V obou případech není obtížné použít COS/M k vyžádání bodů umístěných ve čtverci libovolné úrovně. V první možnosti bude o něco snazší vyčistit čtvercové kusy prostoru na jakékoli úrovni, ale to je zřídka nutné.

Příklad jednoho ze čtverců nižší úrovně:

A zde je několik globálů z projektu XAPI: reprezentace indexu na globálech:

globální ^ způsob slouží k ukládání bodů lomené čáry (silnice, malé řeky atd.) a polygony (uzavřené oblasti: budovy, lesy atd.).

Hrubá klasifikace použití řídkých polí na globály.

1. Ukládáme souřadnice určitých objektů a jejich stavy (mapování, celulární automaty)
2. Ukládáme řídké matrice.

Pro případ 2) při požadavku na konkrétní souřadnice, kde prvku není přiřazena hodnota, musíme získat hodnotu výchozího prvku řídkého pole.

Bonusy, které dostáváme při ukládání vícerozměrných matic do globalů

Rychle odstraňte a/nebo vyberte části prostoru, které jsou násobky řádků, rovin, krychlí atd. V případech, kdy se používají celočíselné indexy, může být užitečná schopnost rychle odstranit a/nebo načíst části prostoru, které jsou násobky řádků, rovin, krychlí atd.

tým Zabít můžeme odstranit buď jeden prvek nebo řádek, nebo dokonce celou rovinu. Díky vlastnostem globals se to děje velmi rychle - tisíckrát rychleji než odstranění prvku po prvku.

Obrázek ukazuje trojrozměrné pole v globálu ^a a různé typy mazání.

Chcete-li vybrat části prostoru pomocí známých indexů, můžete použít příkaz Spojit.

Výběr sloupce matice do proměnné 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ávěr:

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

Na proměnné Column je zajímavé, že máme také řídké pole, ke kterému je také nutné přistupovat prostřednictvím $GET, protože v něm nejsou uloženy výchozí hodnoty.

Výběr kusů prostoru lze také provést pomocí malého programu pomocí funkce $Objednávka. To je zvláště výhodné na prostorech, jejichž indexy nejsou kvantovány (kartografie).

Závěr

Současná doba klade nové ambiciózní úkoly. Grafy se mohou skládat z miliard vrcholů, mapy složené z miliard bodů a někteří mohou dokonce chtít provozovat svůj vlastní vesmír na celulárních automatech (1, 2).

Když už se objem dat z řídkých polí nevejde do RAM, ale potřebujete s nimi pracovat, pak stojí za zvážení možnost implementace podobných projektů na globalech a COS.

Děkuji za pozornost! Čekáme na vaše dotazy a přání v komentářích.

Odmítnutí odpovědnosti: Tento článek a mé komentáře k němu jsou mým názorem a nemají žádný vztah k oficiálnímu stanovisku InterSystems Corporation.

Zdroj: www.habr.com