Iepriekšējās daļās (, ) runājām par globālajiem kā kokiem, šajā aplūkosim globālos kā retus masīvus.
ir masīva veids, kurā lielākajai daļai vērtību ir tāda pati vērtība.
Praksē retie masīvi bieži ir tik milzīgi, ka nav jēgas aizņemt atmiņu ar identiskiem elementiem. Tāpēc ir jēga ieviest retus masīvus tā, lai atmiņa netiktu tērēta identisku vērtību glabāšanai.
Dažās programmēšanas valodās reti masīvi ir iekļauti pašā valodā, , . Citām programmēšanas valodām ir īpašas bibliotēkas, kas ļauj tās ieviest. C++ — uc
Globālie ir labi kandidāti retu masīvu ieviešanai, jo:
- Tie saglabā tikai noteiktu mezglu vērtības un nesaglabā nenoteiktu mezglu vērtības;
- Saskarne, lai piekļūtu mezgla vērtībai, ir ļoti līdzīga tam, cik daudz programmēšanas valodu nodrošina piekļuvi daudzdimensiju masīva elementam.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global ir diezgan zema līmeņa struktūra datu glabāšanai, tāpēc tai ir izcili ātruma raksturlielumi (no simtiem tūkstošu līdz desmitiem miljonu transakciju sekundē atkarībā no aparatūras, skatīt zemāk). )
Tā kā globālā struktūra ir noturīga, ir lietderīgi uz tiem izveidot retus masīvus, ja ir iepriekš zināms, ka ar RAM nepietiks.
Viena no retu masīvu ieviešanas īpašībām ir atgriezt kādu noklusējuma vērtību, ja tiek nodrošināta piekļuve nedefinētai šūnai.
To var īstenot, izmantojot funkciju COS. Šajā piemērā ir aplūkots trīsdimensiju masīvs.
SET a = $GET(^a(x,y,z), defValue)Kādiem uzdevumiem ir nepieciešami reti masīvi, un kā globālie var palīdzēt?
Blakus (savienojamības) matrica
izmanto, lai attēlotu grafikus:
Acīmredzot, jo lielāks ir grafiks, jo vairāk nulles būs matricā. Ja, piemēram, ņemam sociālo tīklu grafiku un attēlosim to līdzīgas matricas veidā, tad tas gandrīz pilnībā sastāvēs no nullēm, t.i. būs rets masīvs.
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
....
Šajā piemērā mēs ietaupām globāli ^m savienojamības matrica, kā arī malu skaits katrā mezglā (kurš ar kuru draudzējas un draugu skaits).
Ja elementu skaits grafikā nav lielāks par 29 miljoniem (šis skaitlis tiek pieņemts kā reizinājums ar 8 * ), tas ir, vēl ekonomiskāks veids, kā uzglabāt šādas matricas, ir bitu virknes, jo to ieviešana īpašā veidā optimizē lielas spraugas.
Manipulācijas ar bitu virknēm veic funkcija .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Stāvokļa mašīnu pārejas tabula
Tā kā ierobežota automāta pārejas grafiks ir parasts grafs, tad galīgā automāta pārejas tabula ir tā pati blakusesības matrica, par kuru tika runāts iepriekš.
Šūnu automāti
Slavenākais šūnu automāts ir , kas savu noteikumu dēļ (kad šūnai ir daudz kaimiņu, tā mirst) ir rets masīvs.
Stīvens Volframs uzskata, ka šūnu automāti ir . 2002. gadā viņš publicēja 1280 lappušu garu grāmatu “A New Kind of Science”, kurā viņš plaši apgalvo, ka šūnu automātu sasniegumi nav izolēti, bet gan ilgstoši un lielā mērā ietekmē visas zinātnes jomas.
Ir pierādīts, ka jebkuru datorā izpildāmu algoritmu var realizēt, izmantojot šūnu automātu. Šūnu automāti tiek izmantoti dinamiskas vides un sistēmu modelēšanai, algoritmisku problēmu risināšanai un citiem mērķiem.
Ja mums ir milzīgs lauks un mums ir jāreģistrē visi šūnu automāta starpstāvokļi, tad ir jēga izmantot globālos.
Kartogrāfija
Pirmā lieta, kas man ienāk prātā, kad runa ir par retu masīvu izmantošanu, ir kartēšanas uzdevumi.
Kā likums, kartēs ir daudz tukšas vietas. Ja karte ir attēlota kā lieli pikseļi, tad 71% no Zemes pikseļiem aizņems okeāns. Rets masīvs. Un, ja jūs lietojat tikai cilvēka roku darbus, tad tukšā vieta būs vairāk nekā 95%.
Protams, neviens neuzglabā kartes rastra masīvu veidā, tiek izmantots vektora attēlojums.
Bet kas ir vektorkartes? Tas ir sava veida rāmis un polilīnijas un daudzstūri, kas sastāv no punktiem.
Būtībā punktu un savienojumu datubāze starp tiem.
Viena no vērienīgākajām kartēšanas misijām ir Gaia teleskopa misija mūsu galaktikas kartēšanai. Tēlaini izsakoties, mūsu galaktika, tāpat kā viss Visums, ir nepārtraukts rets masīvs: milzīgas tukšuma telpas, kurās ir reti mazi punkti - zvaigznes. Tukša vieta ir 99,999999…….%. Lai saglabātu mūsu galaktikas karti, tika izvēlēta globāla datu bāze - Caché.
Es nezinu precīzu globālo struktūru šajā projektā, varu pieņemt, ka tas ir kaut kas līdzīgs:
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
...
Kur ir b, l, d un attālums līdz Saulei.
Elastīgā globālo struktūra ļauj saglabāt visas nepieciešamās zvaigžņu un planētu īpašības, jo globālo bāzēm nav shēmas.
Lai saglabātu mūsu Visuma karti, Caché tika izvēlēts ne tikai tās elastības dēļ, bet arī spējas ļoti ātri uzglabāt datu straumi, vienlaikus veidojot indeksu globālos rādītājus ātrai meklēšanai.
Ja atgriežamies uz Zemes, tad kartogrāfiskie projekti tika radīti uz globāliem un OpenStreetMap dakša - .
Nesen ieslēgts tika ieviesti ģeotelpiskie indeksi . Gaidām rakstu no autoriem ar ieviešanas detaļām.
Telpisko indeksu ieviešana globālā vidē OpenStreetMap XAPI
Bildes ņemtas no .
Visa zemeslode ir sadalīta kvadrātos, tad apakškvadrātos un apakškvadrāti apakškvadrātos utt. Kopumā mēs iegūstam hierarhisku struktūru izveidoto globālo glabāšanai.
Jebkurā brīdī mēs varam gandrīz uzreiz pieprasīt vēlamo laukumu vai notīrīt to, un visi apakšlaukumi tiks arī atgriezti vai notīrīti.
Līdzīgu shēmu globālajiem modeļiem var īstenot vairākos veidos.
Variants 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ВторойТочки
...Variants 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Abos gadījumos nav grūti izmantot COS/M, lai pieprasītu punktus, kas atrodas jebkura līmeņa kvadrātā. Pirmajā variantā būs nedaudz vieglāk notīrīt kvadrātveida vietas gabalus jebkurā līmenī, taču tas ir reti nepieciešams.
Viena no zemākā līmeņa kvadrātiem piemērs:
Un šeit ir vairāki XAPI projekta globālie elementi: globālā indeksa attēlojums:
globāli ^ veidā izmanto punktu glabāšanai (ceļi, mazas upes utt.) un poligoni (slēgtas teritorijas: ēkas, meži utt.).
Retu masīvu izmantošanas aptuvenā klasifikācija globālajos attēlos.
- Mēs saglabājam noteiktu objektu koordinātas un to stāvokļus (kartēšana, šūnu automāti)
- Mēs uzglabājam retas matricas.
2. gadījumam, pieprasot konkrētu koordinātu, kurā elementam nav piešķirta vērtība, mums jāiegūst noklusējuma retā masīva elementa vērtība.
Bonusi, ko saņemam, glabājot daudzdimensionālas matricas globālās
Ātri noņemiet un/vai atlasiet vietas gabalus, kas sastāv no rindu, plakņu, kubu utt. Gadījumos, kad tiek izmantoti veseli skaitļi, var būt noderīga iespēja ātri noņemt un/vai iegūt vietas gabalus, kas ir rindu, plakņu, kubu utt.
komanda mēs varam izdzēst vienu elementu vai rindu, vai pat visu plakni. Pateicoties globālu īpašībām, tas notiek ļoti ātri – tūkstošiem reižu ātrāk nekā elementa noņemšana.
Attēlā parādīts trīsdimensiju masīvs globālā formā ^a un dažāda veida svītrojumi.
Lai atlasītu vietas gabalus, izmantojot zināmus indeksus, varat izmantot komandu .
Matricas kolonnas atlase kolonnas mainīgajam:
; Зададим трёхмерный разреженный массив 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
Secinājums:
Column(0)=1
Column(2)=1
Kolonnas mainīgā interesants ir tas, ka mums ir arī rets masīvs, kuram arī ir jāpiekļūst, izmantojot , jo noklusējuma vērtības tajā netiek saglabātas.
Vietas gabalu atlasi var veikt arī ar nelielu programmu, izmantojot funkciju . Tas ir īpaši ērti telpās, kuru indeksi nav kvantificēti (kartogrāfija).
Secinājums
Pašreizējais laiks izvirza jaunus ambiciozus uzdevumus. Grafikus var veidot miljardiem virsotņu, kartes, kas sastāv no miljardiem punktu, un daži pat varētu vēlēties vadīt savu Visumu uz šūnu automātiem (, ).
Ja datu apjoms no retiem masīviem vairs neietilpst RAM, bet jums ir jāstrādā ar tiem, tad ir vērts apsvērt iespēju īstenot līdzīgus projektus globālajos un COS.
Paldies par jūsu uzmanību! Gaidīsim jūsu jautājumus un vēlmes komentāros.
Atbildības noraidīšana: Šis raksts un mani komentāri par to ir mans viedoklis, un tiem nav nekādas saistības ar InterSystems Corporation oficiālo nostāju.
Avots: www.habr.com