Yn foarige dielen (, ) wy hawwe it oer globalen as beammen, yn dizze sille wy globalen sjen as sparse arrays.
is in soarte fan array wêryn de measte wearden deselde wearde nimme.
Yn 'e praktyk binne sparse arrays faak sa grut dat it gjin punt hat om ûnthâld te besetten mei identike eleminten. Dêrom is it logysk om sparse arrays op sa'n manier te ymplementearjen dat ûnthâld net fergriemd wurdt op it bewarjen fan identike wearden.
Yn guon programmeartalen binne sparse arrays opnommen yn 'e taal sels, , . Oare programmeartalen hawwe spesjale bibleteken wêrmei jo se kinne ymplementearje. Foar C++ - en oaren.
Globalen binne goede kandidaten foar it ymplementearjen fan sparse arrays om't:
- Se bewarje de wearden fan allinich bepaalde knooppunten en bewarje de wearden fan undefinieare net;
- De ynterface foar tagong ta de wearde fan in knooppunt is ekstreem fergelykber mei hoefolle programmeartalen tagong ta in multydinsjoneel array-elemint ymplementearje.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global is in frijwat leech-nivo struktuer foar it opslaan fan gegevens, dêrom hat it treflike snelheidskaaimerken (fan hûnderttûzenen oant tsientûzenen miljoenen transaksjes per sekonde, ôfhinklik fan 'e hardware, sjoch hjirûnder). )
Sûnt de globale is in oanhâldende struktuer, it makket sin te meitsjen sparse arrays op harren as it is bekend fan tefoaren dat it bedrach fan RAM sil net genôch.
Ien fan 'e eigenskippen fan sparse array-ymplementaasjes is om wat standertwearde werom te jaan as in tagong wurdt makke ta in net definieare sel.
Dit kin útfierd wurde mei de funksje yn COS. Dit foarbyld beskôget in 3-diminsjonale array.
SET a = $GET(^a(x,y,z), defValue)Hokker taken fereaskje sparse arrays en hoe kinne globalen helpe?
Adjacency (ferbining) matrix
brûkt om grafiken foar te stellen:
Fansels, hoe grutter de grafyk, hoe mear nullen der sille wêze yn 'e matrix. As wy bygelyks in sosjale netwurkgrafyk nimme en dy yn 'e foarm fan in ferlykbere matrix presintearje, dan sil it hast folslein út nullen bestean, d.w.s. sil in sparse array wêze.
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
....
Yn dit foarbyld bewarje wy globaal ^m ferbiningsmatrix, lykas it oantal rânen op elke knooppunt (wa is freonen mei wa en it oantal freonen).
As it oantal eleminten yn 'e grafyk net mear is as 29 miljoen (dit nûmer wurdt nommen as it produkt fan 8 * ), dat is, in noch mear ekonomyske manier om sokke matriksen op te slaan is bitstrings, om't har ymplemintaasje grutte gatten op in spesjale manier optimalisearret.
Manipulaasjes mei bitstrings wurde útfierd troch de funksje .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
State machine oergong tafel
Sûnt de oergongsgrafyk fan in finite automaton in gewoane grafyk is, dan is de oergongstabel fan 'e finite automaton deselde neistlizzende matrix dy't hjirboppe besprutsen is.
Sellulêre automaten
De meast ferneamde sellulêre automaat is , dy't, troch syn regels (as in sel in protte buorlju hat, stjert) in sparse rige is.
Stephen Wolfram is fan betinken dat sellulêre automaten binne . Yn 2002 publisearre er in boek fan 1280 siden, A New Kind of Science , wêryn't er breed beweart dat foarútgong yn sellulêre automaten net isolearre binne, mar duorsum binne en grutte gefolgen hawwe foar alle gebieten fan 'e wittenskip.
It is bewiisd dat elke útfierbere algoritme op in kompjûter kin wurde ymplementearre mei in sellulêre automaat. Sellulêre automaten wurde brûkt om dynamyske omjouwings en systemen te modellearjen, algoritmyske problemen op te lossen en foar oare doelen.
As wy in enoarm fjild hawwe en wy moatte alle tuskensteaten fan in sellulêre automaat opnimme, dan makket it sin om globalen te brûken.
Kartografy
It earste ding dat yn 't sin komt as it giet om it brûken fan sparse arrays is mappingtaken.
As regel is der in soad lege romte op kaarten. As de kaart wurdt fertsjintwurdige as grutte piksels, dan sil 71% fan de piksels fan 'e ierde wurde beset troch de oseaan. Sparse array. En as jo allinich wurken fan minsklike hannen tapasse, dan sil de lege romte mear as 95% wêze.
Fansels bewarret gjinien kaarten yn 'e foarm fan raster-arrays; in fektorfoarstelling wurdt brûkt.
Mar wat binne vector kaarten? Dit is in soarte fan frame en polylines en polygonen besteande út punten.
Yn wêzen in databank fan punten en ferbinings tusken harren.
Ien fan 'e meast ambisjeuze mapping misjes is de Gaia Telescope missy om ús galaxy yn kaart te bringen. Figuratyf sprutsen, ús galaxy, lykas it hiele hielal, is in trochgeande sparse array: enoarme romten fan leechte dêr't der binne seldsum lytse punten - stjerren. Lege romte is 99,999999…….%. Om de kaart fan ús galaxy op te slaan, waard in globale databank keazen - Caché.
Ik wit net de krekte struktuer fan globalen yn dit projekt, ik kin oannimme dat it wat fergelykber is mei:
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
...
wêr b, l, d binne en ôfstân nei de sinne.
De fleksibele struktuer fan globalen lit jo alle nedige skaaimerken fan stjerren en planeten bewarje, om't de basisen op globalen skema-minder binne.
Om de kaart fan ús universum op te slaan, waard Caché net allinich keazen foar syn fleksibiliteit, mar ek foar syn fermogen om in stream fan gegevens heul fluch op te slaan, wylst tagelyk yndeksglobalen meitsje foar rappe sykopdrachten.
As wy weromkomme nei ierde, dan waarden kartografyske projekten makke op globalen en in foarke fan OpenStreetMap - .
Koartlyn op geospatiale yndeksen waarden ymplementearre . Wy wachtsje op in artikel fan 'e auteurs mei ymplemintaasjedetails.
Ymplemintaasje fan romtlike yndeksen op in globale yn OpenStreetMap XAPI
Foto's nommen fan .
De hiele wrâld is ferdield yn fjouwerkanten, dan sub-kwadraten, en sub-kwadraten yn sub-sub-kwadraten, ensfh. Yn 't algemien krije wy in hiërargyske struktuer foar it bewarjen fan hokker globalen binne makke.
Op elts momint kinne wy it winske plein hast direkt oanfreegje of it wiskje, en alle sub-kwadraten wurde ek weromjûn of wiske.
In ferlykber skema op globalen kin op ferskate manieren ymplementearre wurde.
Option 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ВторойТочки
...Option 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Yn beide gefallen is it net dreech om COS / M te brûken om punten oan te freegjen dy't yn in fjouwerkant fan elk nivo lizze. It sil wat makliker wêze om fjouwerkante stikken romte op elk nivo te skjin te meitsjen yn 'e earste opsje, mar dit is selden nedich.
In foarbyld fan ien fan de legere nivo kwadraten:
En hjir binne ferskate globalen fan it XAPI-projekt: fertsjintwurdiging fan in yndeks op globalen:
mondiaal ^wei brûkt om punten op te slaan (wegen, lytse rivieren, ensfh.) en polygoanen (sletten gebieten: gebouwen, bosken, ensfh.).
Rûge klassifikaasje fan it brûken fan sparse arrays op globalen.
- Wy bewarje de koördinaten fan bepaalde objekten en har steaten (mapping, sellulêre automaten)
- Wy bewarje sparse matriksen.
Foar gefal 2) by it oanfreegjen fan in spesifike koördinaat wêr't it elemint gjin wearde wurdt tawiisd, moatte wy de wearde krije fan it standert sparse array-elemint.
Bonussen dy't wy ûntfange by it opslaan fan multidimensionale matrices yn globals
Fuortsmite en/of selektearje stikken romte fluch dy't meardere rigen, fleantugen, kubes, ensfh. Foar gefallen dêr't integer yndeksen wurde brûkt, kin de mooglikheid om fluch fuortsmite en / of ophelje brokken romte dy't meardere rigen, fleantugen, kubes, ensfh kin nuttich.
ploech wy kinne wiskje of in inkele elemint of in rige, of sels in hiele fleantúch. Mei tank oan de eigenskippen fan globals, dit bart hiel fluch - tûzenen kearen flugger as elemint-by-elemint ferwidering.
De figuer toant in trijediminsjonale array yn in globale ^a en ferskate soarten wiskjes.
Om stikken romte te selektearjen mei bekende yndeksen, kinne jo it kommando brûke .
Selektearje in matrixkolom yn 'e Kolomfariabele:
; Зададим трёхмерный разреженный массив 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
Fermelding:
Column(0)=1
Column(2)=1
Wat nijsgjirrich is oer de Column-fariabele is dat wy ek in sparse array hawwe, dy't ek tagong wurde moat fia , om't standertwearden der net yn wurde opslein.
It selektearjen fan stikken romte kin ek dien wurde fia in lyts programma mei de funksje . Dit is benammen handich op romten wêrfan de yndeksen net kwantisearre binne (kartografy).
konklúzje
De hjoeddeistige tiden jouwe nije ambisjeuze taken. Grafiken kinne wurde opboud út miljarden hoekpunten, kaarten opboud út miljarden punten, en guon kinne sels wolle rinne harren eigen universum op sellulêre automaten (, ).
Wannear't it folume fan gegevens út sparse arrays kin net mear passe yn RAM, mar jo moatte wurkje mei harren, dan is it wurdich beskôgje de mooglikheid fan it útfieren fan ferlykbere projekten op globals en COS.
Tank foar jo oandacht! Wy wachtsje op jo fragen en winsken yn 'e kommentaren.
Disclaimer: Dit artikel en myn opmerkingen dêrop binne myn miening en hawwe gjin relaasje mei de offisjele posysje fan InterSystems Corporation.
Boarne: www.habr.com