Globalni su mačevi blaga za pohranjivanje podataka. Retki nizovi. dio 3

U prethodnim dijelovima (1, 2) govorili smo o globalima kao stablima, u ovom ćemo globale gledati kao rijetke nizove.

Sparse Array je tip niza u kojem većina vrijednosti uzima istu vrijednost.

U praksi, rijetki nizovi su često toliko ogromni da nema smisla zauzimati memoriju identičnim elementima. Stoga, ima smisla implementirati rijetke nizove na takav način da se memorija ne troši na pohranjivanje identičnih vrijednosti.
U nekim programskim jezicima, rijetki nizovi su uključeni u sam jezik, na primjer u J, MATLAB. Drugi programski jezici imaju posebne biblioteke koje vam omogućavaju da ih implementirate. Za C++ - Vlastiti i drugi.

Globali su dobri kandidati za implementaciju rijetkih nizova jer:

1. Oni pohranjuju vrijednosti samo određenih čvorova i ne pohranjuju vrijednosti nedefiniranih;
2. Interfejs za pristup vrijednosti čvora je izuzetno sličan tome koliko programskih jezika implementira pristup višedimenzionalnom elementu niza.

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

3. Global je struktura prilično niskog nivoa za skladištenje podataka, stoga ima izvanredne karakteristike brzine (od stotina hiljada do desetina miliona transakcija u sekundi, u zavisnosti od hardvera, pogledajte dole). 1)

Budući da je global trajna struktura, ima smisla kreirati rijetke nizove na njima kada se unaprijed zna da količina RAM-a neće biti dovoljna.

Jedno od svojstava implementacije rijetkih nizova je vraćanje neke zadane vrijednosti ako se pristupi nedefiniranoj ćeliji.

Ovo se može implementirati pomoću funkcije $GET u COS. Ovaj primjer razmatra 3-dimenzionalni niz.

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

Koji zadaci zahtijevaju rijetke nizove i kako globalni mogu pomoći?

Matrica susjedstva (povezivosti).

Takve matrice koristi se za predstavljanje grafova:

Očigledno, što je veći graf, to će više nula biti u matrici. Ako, na primjer, uzmemo graf društvene mreže i predstavimo ga u obliku slične matrice, tada će se on gotovo u potpunosti sastojati od nula, tj. će biti rijedak niz.

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
....

U ovom primjeru štedimo globalno ^m matrica povezivanja, kao i broj ivica na svakom čvoru (ko je s kim prijatelj i broj prijatelja).

Ako broj elemenata u grafu nije veći od 29 miliona (ovaj broj se uzima kao proizvod 8 * maksimalna veličina linije), odnosno, još ekonomičniji način pohranjivanja takvih matrica su bitni stringovi, jer njihova implementacija optimizira velike praznine na poseban način.

Manipulacije sa nizovima bitova obavlja funkcija $BIT.

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

Prijelazna tablica državnog stroja

Budući da je graf prijelaza konačnog automata običan graf, tada je prijelazna tablica konačnog automata ista matrica susjedstva o kojoj smo gore govorili.

Ćelijski automati

Najpoznatiji ćelijski automat je igra "život", koji je, zbog svojih pravila (kada ćelija ima mnogo susjeda, umire) rijedak niz.

Stephen Wolfram vjeruje da ćelijski automati jesu nova oblast nauke. Godine 2002. objavio je knjigu od 1280 stranica, Nova vrsta nauke, u kojoj široko tvrdi da napredak u ćelijskim automatima nije izolovan, već je trajan i ima velike implikacije za sva područja nauke.

Dokazano je da se bilo koji algoritam koji se može izvršiti na računaru može implementirati pomoću ćelijskog automata. Ćelijski automati se koriste za modeliranje dinamičkih okruženja i sistema, za rješavanje algoritamskih problema i za druge svrhe.

Ako imamo ogromno polje i trebamo zabilježiti sva međustanja ćelijskog automata, onda ima smisla koristiti globalne vrijednosti.

Kartografija

Prva stvar koja mi pada na pamet kada je u pitanju korištenje rijetkih nizova su zadaci mapiranja.

Po pravilu, na kartama ima puno praznog prostora. Ako je mapa predstavljena kao veliki pikseli, tada će 71% Zemljinih piksela biti zauzeto okeanom. Sparse array. A ako primijenite samo djela ljudskih ruku, tada će prazan prostor biti više od 95%.

Naravno, niko ne pohranjuje karte u obliku rasterskih nizova, već se koristi vektorska reprezentacija.
Ali šta su vektorske karte? Ovo je vrsta okvira i polilinija i poligona koji se sastoje od tačaka.
U suštini baza podataka tačaka i veza između njih.

Jedna od najambicioznijih misija mapiranja je misija Gaia Telescope za mapiranje naše galaksije. Slikovito rečeno, naša galaksija, kao i cijeli univerzum, je kontinuirani rijetki niz: ogromni prostori praznine u kojima se nalaze rijetke male tačke - zvijezde. Prazan prostor je 99,999999…….%. Za pohranjivanje karte naše galaksije odabrana je globalna baza podataka - Caché.

Ne znam tačnu strukturu globala u ovom projektu, mogu pretpostaviti da je nešto slično:

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
...

Gdje su b, l, d galaktičke koordinate geografska širina, dužina i udaljenosti do Sunca.

Fleksibilna struktura globala omogućava vam da sačuvate sve potrebne karakteristike zvijezda i planeta, budući da su baze na globalima bez shema.

Za pohranjivanje mape našeg univerzuma, Caché je odabran ne samo zbog svoje fleksibilnosti, već i zbog svoje sposobnosti da vrlo brzo pohrani tok podataka, dok istovremeno kreira indekse globala za brza pretraživanja.

Ako se vratimo na Zemlju, onda su kartografski projekti kreirani na globalima OpenStreetMap XAPI i račva OpenStreetMap-a - FOSM.

Nedavno hackathon Caché implementirani su geoprostorni indeksi geoprostornih. Čekamo članak autora s detaljima implementacije.

Implementacija prostornih indeksa na globalnom u OpenStreetMap XAPI

Slike preuzete sa ovu prezentaciju.

Cijeli globus je podijeljen na kvadrate, zatim na podkvadrate, a potkvadrati na pod-podkvadrate, itd. Općenito, dobijamo hijerarhijsku strukturu za pohranjivanje globalnih vrijednosti koje su kreirane.

U svakom trenutku možemo gotovo trenutno zatražiti željeni kvadrat ili ga očistiti, a svi podkvadrati će također biti vraćeni ili očišćeni.

Slična šema na globalima može se implementirati na nekoliko načina.

Opcija 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ВторойТочки
...

Opcija 2:

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

U oba slučaja, nije teško koristiti COS/M za traženje bodova koji se nalaze u kvadratu bilo kojeg nivoa. U prvoj opciji bit će nešto lakše očistiti kvadratne komade prostora na bilo kojem nivou, ali to je rijetko potrebno.

Primjer jednog od kvadrata nižeg nivoa:

A evo nekoliko globala iz XAPI projekta: predstavljanje indeksa na globalima:

globalno ^put koristi se za pohranjivanje bodova polilinije (putevi, rječice, itd.) i poligoni (zatvorena područja: zgrade, šume itd.).

Gruba klasifikacija upotrebe rijetkih nizova na globalima.

1. Pohranjujemo koordinate određenih objekata i njihova stanja (mapiranje, ćelijski automati)
2. Mi skladištimo rijetke matrice.

Za slučaj 2) kada se traži određena koordinata gdje elementu nije dodijeljena vrijednost, moramo dobiti vrijednost zadanog elementa rijetkog niza.

Bonusi koje dobijamo pri skladištenju višedimenzionalnih matrica u globalima

Brzo uklonite i/ili odaberite dijelove prostora koji su višestruki redovima, ravnima, kockama itd. Za slučajeve u kojima se koriste indeksi s cijelim brojevima, mogućnost brzog uklanjanja i/ili dohvaćanja dijelova prostora koji su višestruki redovima, ravnima, kockama itd. može biti korisna.

tim Ubiti možemo izbrisati ili jedan element ili red, ili čak cijelu ravan. Zahvaljujući svojstvima globala, to se dešava vrlo brzo - hiljade puta brže od uklanjanja element po element.

Slika prikazuje trodimenzionalni niz u globalu ^a i različite vrste brisanja.

Da biste odabrali dijelove prostora koristeći poznate indekse, možete koristiti naredbu Spoji se.

Odabir kolone matrice u varijablu 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

Zaključak:

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

Ono što je zanimljivo u vezi varijable Column je da imamo i rijedak niz, kojem se također mora pristupiti putem $GET, budući da se u njemu ne pohranjuju zadane vrijednosti.

Odabir dijelova prostora također se može obaviti kroz mali program pomoću funkcije $Order. Ovo je posebno pogodno za prostore čiji indeksi nisu kvantizirani (kartografija).

zaključak

Sadašnja vremena postavljaju nove ambiciozne zadatke. Grafovi mogu biti sastavljeni od milijardi vrhova, mape sastavljene od milijardi tačaka, a neki bi čak mogli htjeti pokrenuti vlastiti svemir na ćelijskim automatima (1, 2).

Kada količina podataka iz rijetkih nizova više ne može stati u RAM, ali morate raditi s njima, onda je vrijedno razmotriti mogućnost implementacije sličnih projekata na globalima i COS-u.

Hvala vam na pažnji! Čekamo vaša pitanja i želje u komentarima.

odricanje: Ovaj članak i moji komentari na njega su moje mišljenje i nemaju nikakve veze sa zvaničnim stavom InterSystems Corporation.

izvor: www.habr.com