U prethodnim delovima (, ) govorili smo o globalima kao o stablima, u ovom delu ćemo razmotriti globale kao retke nizove.
je vrsta niza u kojem većina vrednosti ima istu vrednost.
U praksi, često se susreću tako ogromni retki nizovi da nema smisla trošiti memoriju na iste elemente. Stoga ima smisla implementirati retke nizove tako da memorija ne bude trošena na čuvanje istih vrednosti.
U nekim programskim jezicima retki nizovi su deo jezika, , . U drugim programskim jezicima postoje posebne biblioteke koje omogućavaju njihovu implementaciju. Za C++ — i dr.
Globali su dobri kandidati za implementaciju retkih nizova jer:
- Čuvaju vrednosti samo određenih čvorova i ne čuvaju vrednosti neodređenih;
- Interfejs za pristup vrednosti čvora je izuzetno sličan načinu kako je u mnogim programskim jezicima implementiran pristup elementima višedimenzionalnog niza.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global je dovoljno niskonivo struktura za skladištenje podataka, stoga ima odlične karakteristike brzine (od stotina hiljada do desetina miliona transakcija u sekundi, u zavisnosti od hardvera, vidi. )
Budući da je global perzistentna struktura, ima smisla praviti retke nizove na njima kada je unapred poznato da će kapacitet RAM-a biti nedovoljan.
Jedna od osobina implementacija retkih nizova je vraćanje nekog podrazumevanog vrednosti, ako se pristupa neodređenoj ćeliji.
To se može implementirati korišćenjem funkcije u COS. U ovom primeru razmatramo trodimenzionalni niz.
SET a = $GET(^a(x,y,z), defValue)U kojim zadacima su potrebni retki nizovi i kako globali mogu pomoći?
Matrica susedstva (povezanosti)
se koriste za predstavljanje grafova:
Očigledno je da što je graf veći, to će više nula biti u matrici. Na primer, ako uzmemo graf društvene mreže i predstavimo ga u obliku slične matrice, on će gotovo u potpunosti biti sačinjen od nula, tj. biće ređi 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 primeru čuvamo u globalu ^m matrica povezanosti, kao i broj bridova za svaki čvor (tko se s kim druži i broj prijatelja).
Ako broj elemenata u grafu ne prelazi 29 milijuna (taj se broj uzima kao umnožak 8 * ), postoji još ekonomičniji način pohrane takvih matrica — bitni nizovi, jer se u njihovoj implementaciji posebno optimiziraju veliki prazni prostori.
Manipulacije s bitnim nizovima izvode se funkcijom .
; postavljanje bita
SET $BIT(rowID, positionID) = 1
; dobivanje bita
Write $BIT(rowID, positionID)
Tablica prijelaza konačnog automata
Budući da je graf prijelaza konačnog automata običan graf, tako je i tablica prijelaza konačnog automata ista ona matrica susjednosti o kojoj je ranije bilo riječi.
Ćelijski automati
Najpoznatiji ćelijski automat je , koja zbog svojih pravila (kada ćelija ima mnogo susjeda — umire) predstavlja rijetki niz.
Stephen Wolfram smatra da su ćelijski automati . Godine 2002. objavljuje knjigu od 1280 stranica 'A New Kind of Science', gdje široko argumentira da dostignuća u području ćelijskih automata nisu izolirana, već su vrlo stabilna i imaju veliku važnost za sve grane znanosti.
Dokazano je da se svaki algoritam koji se može izvršiti na računalu može realizirati pomoću ćelijskog automata. Ćelijski automati se koriste za modeliranje dinamičkih okruženja i sustava, za rješavanje algoritamskih zadataka i druge svrhe.
Ako imamo ogroman teren i trebamo zapisati sve međustanja ćelijskog automata, sasvim je razborito koristiti globalne varijable.
Kartografija
Prvo što mi pada na pamet kada se govori o upotrebi rijetkih nizova su kartografski zadaci.
Općenito, na kartama ima jako puno praznog prostora. Ako bismo kartu predstavljali velikim pikselima, 71% pikselâ Zemlje bi bilo zauzeto oceanom. Rijetki niz. A ako prikazujemo samo djela ljudskih ruku, tada će praznog prostora biti više od 95%.
Naravno, nitko ne pohranjuje karte u obliku rasternih nizova, već se koristi vektorsko predstavljanje.
Ali što predstavljaju vektorske karte? To je neka okvir i polilinije i poligoni koji se sastoje od točaka.
Zapravo, baza podataka točaka i veza između njih.
Jedan od najambicioznijih zadataka mapiranja je misija mapiranja naše galaksije teleskopom Gaia. Figurativno govoreći, naša galaksija, kao i cijeli svemir, predstavlja kontinuirani rijetki sustav: ogromni prostori praznine, u kojima se nalaze rijetke male točke — zvijezde. Praznog prostora 99,999999…….%. Za pohranu karte naše galaksije odabrana je baza podataka na globalama — Caché.
Ne znam točnu strukturu globalâ u ovom projektu, mogu pretpostaviti da je to nešto slično:
Set ^galaxy(b, l, d) = 1; Broj zvijezde prema katalogu, ako postoji
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; opcije blackhole, quazar, red_dwarf itd.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercur"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Gdje b, l, d — to su i udaljenost do Sunca.
Fleksibilna struktura globalâ omogućava pohranu svih potrebnih karakteristika zvijezda i planeta, budući da baze na globalima nemaju shemu (scheme-less).
Za pohranu karte našeg svemira Caché je odabrana ne samo zbog fleksibilnosti, već i zbog sposobnosti vrlo brzo pohranjivati tok podataka, pri čemu se istovremeno stvaraju indeksni globali za brzu pretragu.
Vratimo li se zemlji, na globalima su stvoreni kartografski projekti i fork OpenStreetMap — .
Nedavno su na proveli su se geoprostoreindeksi . Očekujemo od autora članka detalje implementacije.
Implementacija prostornog indeksa na globalu u OpenStreetMap XAPI
Slike su preuzete iz .
Cijela zemaljska kugla dijeli se na kvadrate, zatim podkvadrate, a podkvadrati na pod-podkvadrate i tako dalje. Uglavnom, dobivamo hijerarhijsku strukturu za pohranu kojoj su stvoreni globali.
U bilo kojem trenutku možemo praktički odmah zatražiti potrebni kvadrat ili ga očistiti, pri čemu će svi podkvadrati također biti vraćeni ili očišćeni.
Sličnu shemu na globalima moguće je realizirati 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) = idPrveTočke
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idDrugeTočke
...Opcija 2:
Set ^m('abacdabcdabacdabcda', 1) = idPrveTočke
Set ^m('abacdabcdabacdabcda', 2) = idDrugeTočke
...U oba slučaja nije teško zatražiti točke unutar kvadrata bilo kojeg nivoa na COS/M. Bit će nešto lakše očistiti kvadratne dijelove prostora bilo kojeg nivoa u prvom slučaju, no to je rijetko potrebno.
Primjer jednog od kvadratića donjeg nivoa:
Evo nekoliko globalnih varijabli iz projekta XAPI: prikaz indeksa na globalima:
Globalna varijabla ^way koristi se za pohranu točaka (puteva, malih rijeka i sl.) i poligona (zatvorene površine: zgrade, šume itd.).
Gruba klasifikacija korištenja rijetkih nizova na globalima.
- Pohranjujemo koordinate određenih objekata i njihova stanja (mapiranje, stanični automati)
- Pohranjujemo rijetke matrice.
Za slučaj 2) pri zahtjevu za određenom koordinatom, gdje elementu nije dodijeljena vrijednost, trebamo dobiti zadanu vrijednost elementa rijetkog niza.
Bodovi koje dobijamo prilikom pohrane višedimenzionalnih matrica u globalima
Brzo brisanje i/ili uzimanje dijelova prostora, višekratnih po redovima, ravninama, kockama itd. Za slučajeve kada se koriste cijeli brojevi kao indeksi, može biti korisna mogućnost brzog brisanja i/ili uzimanja dijelova prostora, višekratnih po redovima, ravninama, kockama itd.
Naredbom možemo ukloniti kao pojedinačni element, tako i redak, pa čak i cijelu ravninu. Zahvaljujući svojstvima globalnih varijabli, to se događa vrlo brzo — tisućama puta brže nego element po element.
Na slici je prikazana trodimenzionalna matrica u globalnoj varijabli ^a i različiti tipovi brisanja.
Za uzimanje dijelova prostora prema poznatim indeksima može se koristiti komanda .
Uzimanje stupca matrice u varijablu Column:
; Definirajmo trodimenzionalni rijetki niz 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)
; Ispišimo varijablu Column
Zwrite Column
Izvještaj:
Column(0)=1
Column(2)=1
Što je zanimljivo, u varijabli Column također imamo rijetki niz, na koji se treba obratiti također kroz , jer se u njemu ne pohranjuju zadane vrijednosti.
Uzimanje dijelova prostora također se može raditi kroz malu aplikaciju korištenjem funkcije . Ovo je posebno zgodno u prostorima čiji su indeksi nekvantizirani (karta).
Zaključak
Sadašnje vrijeme postavlja nove ambiciozne zadatke. Grafovi mogu imati milijarde čvorova, karte milijarde točaka, a netko čak može poželjeti pokrenuti vlastiti svemir na staničnim automatima (, ).
Kada volumen podataka rijetkih nizova više ne može stati u radnu memoriju, a potrebno je raditi s njima, valja razmotriti mogućnost implementacije sličnih projekata na globalima i COS.
Hvala na pažnji! Očekujemo vaša pitanja i sugestije u komentarima.
Odricanje: Ovaj članak i moji komentari su moje mišljenje i nemaju veze s službenim stavom korporacije InterSystems.
Izvor: habr.com
