U prethodnim dijelovima (, ) govorili smo o globalima kao stablima, u ovom ćemo promatrati globale kao rijetke nizove.
je vrsta niza u kojem većina vrijednosti ima istu vrijednost.
U praksi su rijetki nizovi č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, , . Ostali programski jezici imaju posebne biblioteke koje vam omogućuju njihovu implementaciju. Za C++ - itd.
Globali su dobri kandidati za implementaciju rijetkih nizova jer:
- Oni pohranjuju vrijednosti samo određenih čvorova i ne pohranjuju vrijednosti nedefiniranih;
- Sučelje za pristup vrijednosti čvora vrlo je slično koliko programskih jezika implementira pristup višedimenzionalnom elementu niza.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global je struktura prilično niske razine za pohranu podataka, stoga ima izvanredne karakteristike brzine (od stotina tisuća do desetaka milijuna transakcija u sekundi, ovisno o hardveru, vidi dolje). )
Budući da je global trajna struktura, ima smisla stvarati rijetke nizove na njima kada se unaprijed zna da količina RAM-a neće biti dovoljna.
Jedno od svojstava implementacija rijetkih polja je vraćanje neke zadane vrijednosti ako se pristupi nedefiniranoj ćeliji.
Ovo se može implementirati pomoću funkcije u COS-u. Ovaj primjer razmatra 3-dimenzionalni niz.
SET a = $GET(^a(x,y,z), defValue)Koji zadaci zahtijevaju rijetke nizove i kako globali mogu pomoći?
Matrica susjedstva (povezanosti).
koristi se za predstavljanje grafova:
Očito, što je graf veći, to će u matrici biti više nula. 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. bit će 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 matricu povezanosti, kao i broj rubova na svakom čvoru (tko je s kim prijatelj i broj prijatelja).
Ako broj elemenata u grafikonu nije veći od 29 milijuna (ovaj broj se uzima kao umnožak 8 * ), odnosno još ekonomičniji način pohranjivanja takvih matrica su nizovi bitova, budući da njihova implementacija na poseban način optimizira velike praznine.
Manipulacije nizovima bitova obavlja funkcija .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Prijelazna tablica stroja stanja
Budući da je tranzicijski graf konačnog automata običan graf, tada je tranzicijska tablica konačnog automata ista matrica susjedstva o kojoj se raspravljalo gore.
Stanični automati
Najpoznatiji stanični automat je , koji je zbog svojih pravila (kada ćelija ima mnogo susjeda, ona umire) rijedak niz.
Stephen Wolfram smatra da su stanični automati . Godine 2002. objavio je knjigu od 1280 stranica, Nova vrsta znanosti, u kojoj široko tvrdi da napredak u staničnim automatima nije izoliran, već je trajan i ima velike implikacije na sva područja znanosti.
Dokazano je da se bilo koji algoritam koji se može izvršiti na računalu može implementirati pomoću staničnog automata. Stanični automati koriste se za modeliranje dinamičkih okruženja i sustava, za rješavanje algoritamskih problema iu druge svrhe.
Ako imamo ogromno polje i trebamo zabilježiti sva međustanja staničnog automata, onda ima smisla koristiti globale.
Kartografija
Prva stvar koja mi pada na pamet kada se radi o korištenju rijetkih nizova su zadaci mapiranja.
U pravilu, na kartama ima puno praznog prostora. Ako je karta predstavljena velikim pikselima, tada će 71% Zemljinih piksela zauzimati ocean. Rijetki niz. A ako primijenite samo djela ljudskih ruku, tada će prazan prostor biti više od 95%.
Naravno, nitko ne pohranjuje karte u obliku rasterskih nizova, koristi se vektorski prikaz.
Ali što su vektorske karte? Ovo je vrsta okvira i polilinija i poligona koji se sastoje od točaka.
U biti baza podataka točaka i veza između njih.
Jedna od najambicioznijih misija mapiranja je misija teleskopa Gaia za mapiranje naše galaksije. Slikovito rečeno, naša galaksija, kao i cijeli svemir, kontinuirani je rijetki niz: ogromni prostori praznine u kojima se nalaze rijetke male točke – zvijezde. Prazan prostor je 99,999999…….%. Za pohranu karte naše galaksije odabrana je globalna baza podataka - Caché.
Ne znam točnu strukturu globala u ovom projektu, mogu pretpostaviti da je to 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 i udaljenosti do Sunca.
Fleksibilna struktura globala omogućuje vam spremanje svih potrebnih karakteristika zvijezda i planeta, budući da su baze na globalima bez sheme.
Za pohranu karte našeg svemira, Caché je odabran ne samo zbog svoje fleksibilnosti, već i zbog svoje sposobnosti da vrlo brzo pohrani tok podataka, dok istovremeno stvara globalne indekse za brza pretraživanja.
Ako se vratimo na Zemlju, onda su kartografski projekti nastali na globalima i račvanje OpenStreetMapa - .
Nedavno na implementirani su geoprostorni indeksi . Čekamo članak od autora s detaljima implementacije.
Implementacija prostornih indeksa na globalu u OpenStreetMap XAPI
Slike preuzete sa .
Cijeli je globus podijeljen na kvadrate, pa podkvadrate, a podkvadrati na podpodkvadrate i tako dalje. Općenito, dobivamo hijerarhijsku strukturu za pohranjivanje kreiranih globala.
U svakom trenutku možemo gotovo trenutno zatražiti željeni kvadrat ili ga izbrisati, a svi podkvadrati će također biti vraćeni ili izbrisani.
Slična shema 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 točaka smještenih u kvadratu bilo koje razine. Bit će nešto lakše očistiti četvrtaste komade prostora na bilo kojoj razini u prvoj opciji, ali to je rijetko potrebno.
Primjer jednog od kvadrata niže razine:
Evo nekoliko globala iz XAPI projekta: prikaz indeksa na globalima:
globalno ^ način koristi se za pohranjivanje bodova (ceste, rječice i sl.) i poligoni (zatvoreni prostori: zgrade, šume i sl.).
Gruba klasifikacija upotrebe rijetkih nizova na globalima.
- Pohranjujemo koordinate određenih objekata i njihova stanja (mapiranje, stanični automati)
- Pohranjujemo rijetke matrice.
Za slučaj 2) kada tražimo određenu koordinatu gdje elementu nije dodijeljena vrijednost, moramo dobiti vrijednost zadanog elementa rijetkog polja.
Bonusi koje dobivamo prilikom pohranjivanja višedimenzionalnih matrica u globale
Brzo uklonite i/ili odaberite dijelove prostora koji su višestruki redovi, ravnine, kocke itd. U slučajevima kada se koriste cjelobrojni indeksi, mogućnost brzog uklanjanja i/ili dohvaćanja dijelova prostora koji su višekratnici redaka, ravnina, kocki itd. može biti korisna.
tim možemo izbrisati ili jedan element ili red, ili čak cijelu ravninu. Zahvaljujući svojstvima globala, to se događa vrlo brzo - tisućama puta brže od uklanjanja element po element.
Slika prikazuje trodimenzionalni niz u globalu ^a i različite vrste brisanja.
Za odabir dijelova prostora koristeći poznate indekse, možete koristiti naredbu .
Odabir stupca matrice u varijablu Stupac:
; Зададим трёхмерный разреженный массив 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 s varijablom Stupac je da također imamo razrijeđeni niz, kojem se također mora pristupiti putem , budući da zadane vrijednosti nisu pohranjene u njemu.
Odabir dijelova prostora također se može izvršiti kroz mali program pomoću funkcije . Ovo je posebno zgodno na prostorima čiji indeksi nisu kvantizirani (kartografija).
Zaključak
Sadašnje vrijeme postavlja nove ambiciozne zadatke. Grafovi mogu biti sastavljeni od milijardi vrhova, karte od milijardi točaka, a neki bi čak željeli pokrenuti vlastiti svemir na staničnom automatu (, ).
Kada količina podataka iz rijetkih nizova više ne može stati u RAM, ali trebate raditi s njima, tada je vrijedno razmotriti mogućnost implementacije sličnih projekata na globalima i COS-u.
Hvala na pozornosti! Čekamo vaša pitanja i želje u komentarima.
Izjava o odricanju od odgovornosti: Ovaj članak i moji komentari na njega moje su mišljenje i nemaju nikakve veze sa službenim stavom InterSystems Corporation.
Izvor: www.habr.com