Globals ipfuma- minondo yekuchengetedza data. Sparse arrays. Chikamu 3

Muzvikamu zvakapfuura (1, 2) takataura nezvepasi rose semiti, mune ino tichatarisa maglobals as sparse arrays.

Sparse Array imhando yehurongwa umo mazhinji emakoshero anotora kukosha kwakafanana.

Mukuita, sparse arrays kazhinji akakura zvekuti hapana chikonzero chekutora ndangariro nezvinhu zvakafanana. Naizvozvo, zvine musoro kushandisa sparse arrays nenzira yekuti ndangariro dzisatambiswe pakuchengetedza zvakafanana hunhu.
Mune mimwe mitauro yekuronga, mitsetse mishoma inosanganisirwa mumutauro wacho, semuenzaniso muna J, MATLAB. Mimwe mitauro yepurogiramu ine maraibhurari akakosha anokutendera kuti uzviite. ZveC++ - Own uye vamwe.

Globals vakwikwidzi vakanaka vekushandisa sparse arrays nekuti:

1. Ivo vanochengeta hunhu hwemamwe manode chete uye havachengete kukosha kweasina kutsanangurwa;
2. Iyo interface yekuwana kukosha kwenode yakafanana zvakanyanya nekuti vangani mitauro yekuronga inoshandisa kuwana kune multidimensional array element.

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

3. Global inzvimbo yakaderera-chikamu chekuchengetedza data, saka ine yakatanhamara yekumhanyisa maitiro (kubva kumazana ezviuru kusvika kumakumi emamiriyoni ekutengeserana pasekondi, zvichienderana nehardware, ona pazasi). 1)

Sezvo iyo yepasirese iri chimiro chinoramba chiripo, zvine musoro kugadzira sparse arrays pavari kana ichizivikanwa pachine nguva kuti huwandu hwe RAM hauzokwane.

Imwe yezvivakwa zve sparse array mashandisirwo ndeyekudzosera imwe default kukosha kana mukana waitwa kune isina kutsanangurwa sero.

Izvi zvinogona kuitwa uchishandisa basa $GET muCOS. Uyu muenzaniso unotarisa 3-dimensional array.

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

Ndeapi mabasa anoda sparse arrays uye pasi rose angabatsira sei?

Adjacency (kubatanidzwa) matrix

Matrices akadaro rinoshandiswa kumiririra magirafu:

Zviripachena, iyo yakakura girafu, iyo yakawanda zero ichave iri mumatrix. Kana, semuenzaniso, tikatora girafu yesocial network toiratidza muchimiro chechimiro chakafanana, ipapo inenge iine zero, i.e. ichava shoma shoma.

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

Mumuenzaniso uyu, tinoponesa pasi rose ^m yekubatanidza matrix, pamwe nehuwandu hwemipendero pane imwe neimwe node (ndiani ishamwari naye uye nhamba yeshamwari).

Kana nhamba yezvinhu zviri mugirafu isingadarike mamiriyoni makumi maviri nemapfumbamwe (nhamba iyi inotorwa sechigadzirwa che29 * saizi yepamusoro yemutsetse), ndiko kuti, imwe nzira yakatonyanya hupfumi yekuchengetedza matrices akadaro tambo diki, sezvo kuita kwavo kunokwirisa mapundu makuru nenzira yakakosha.

Manipulations ane bit tambo anoitwa nebasa $BIT.

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

State muchina shanduko tafura

Sezvo girafu yeshanduko yeinogumira otomatiki iri girafu rakajairwa, saka tafura yeshanduko yeinogumira automaton ndiyo yakafanana matrix yepedyo yakurukurwa pamusoro.

Cellular automata

Iyo inonyanya kuzivikanwa cellular automaton ndeye mutambo "Hupenyu", iyo, nekuda kwemitemo yayo (apo sero rine vavakidzani vakawanda, rinofa) ndiro shoma shoma.

Stephen Wolfram anotenda kuti cellular automata ndeye munda mutsva wesainzi. Muna 2002, akaburitsa bhuku rine peji 1280, A New Kind of Science, umo anopokana zvakanyanya kuti kufambira mberi mumaserura otomatiki hakuna kuparadzaniswa, asi kuri kutsungirira uye kune zvinokonzeresa munzvimbo dzese dzesainzi.

Izvo zvave zvichiratidzwa kuti chero algorithm inoitwa pakombuta inogona kuitwa uchishandisa cellular automaton. Cellular automata inoshandiswa kuenzanisa nharaunda dzakasimba uye masisitimu, kugadzirisa algorithmic matambudziko uye nezvimwe zvinangwa.

Kana isu tiine munda wakakura uye isu tinofanirwa kurekodha ese epakati nyika ye cellular automaton, saka zvine musoro kushandisa pasi rose.

Cartography

Chinhu chekutanga chinouya mupfungwa dzangu kana zvasvika pakushandisa sparse arrays kuita mepu mabasa.

Sezvo mutemo, kune nzvimbo yakawanda isina chinhu pamepu. Kana mepu ichimiririrwa semapikisi makuru, ipapo 71% yemapikisi ePasi ichagarwa negungwa. Sparse array. Uye kana ukashandisa mabasa emaoko evanhu chete, ipapo nzvimbo isina chinhu ichave inopfuura 95%.

Ehe, hapana anochengeta mamepu ari muchimiro cheraster arrays; inomiririra vector inoshandiswa.
Asi chii chinonzi vector mepu? Iyi imhando yefuremu uye mapolylines uye mapolygoni ane mapoinzi.
Chaizvoizvo dhatabhesi yemapoinzi uye kubatana pakati pavo.

Imwe yeanonyanya kushuvira mepu mishoni ndeye Gaia Telescope mishoni yekumisikidza nyeredzi yedu. Nekudimikira, gwara redu renzou, sechadenga chese, inoramba iine nhurikidzwa: nzvimbo huru dzekusava nechinhu umo mune madiki madiki - nyeredzi. Empty space is 99,999999 …….%. Kuchengeta mepu yegirazi redu, dhatabhesi repasi rose rakasarudzwa - Caché.

Ini handizive chimiro chaicho chepasi rose muchirongwa ichi, ndinogona kufunga kuti chimwe chinhu chakafanana ne:

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

Apo b, l, d vari galactic coordinates latitude, longitudo uye chinhambwe kuenda kuZuva.

Iyo inochinjika chimiro chepasi rose inobvumidza iwe kuchengetedza chero anodiwa maitiro enyeredzi nemapuraneti, sezvo mabhesi epasirese ari hurongwa-shoma.

Kuchengeta mepu yezvakasikwa zvedu, Caché yakasarudzwa kwete nekuda kwekushanduka kwayo chete, asiwo nekugona kwayo kuchengetedza rwizi rwe data nekukasira, ukuwo ichigadzira index globals yekutsvaga nekukurumidza.

Kana tikadzokera kuNyika, ipapo mapurojekiti emifananidzo akagadzirwa papasi rose OpenStreetMap XAPI uye forogo yeOpenStreetMap - FOSM.

Munguva pfupi yapfuura hackathon Caché geospatial indexes yakaitwa Geospatial. Takamirira chinyorwa kubva kune vanyori vane ruzivo rwekuita.

Kuitwa kwenzvimbo indekisi papasi rose muOpenStreetMap XAPI

Mifananidzo yakatorwa kubva mharidzo iyi.

Nyika yese yakakamurwa kuita masikweya, ipapo sub-squares, uye sub-squares kuita sub-sub-squares, zvichingodaro. Kazhinji, tinowana chimiro chehierarchical chekuchengetedza izvo zvinogadzirwa pasi rose.

Chero nguva, tinogona kukumbira ipapo ipapo yatinoda skweya kana kuibvisa, uye ese madiki-square anodzoserwa kana kucheneswa.

Chirongwa chakafanana chepasi rose chinogona kuitwa nenzira dzinoverengeka.

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

Sarudzo 2:

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

Muzviitiko zvese izvi, hazvina kunetsa kushandisa COS/M kukumbira mapoinzi ari muskweya yechero nhanho. Zvichave zviri nyore kuchenesa mativi enzvimbo pane chero nhanho mune yekutanga sarudzo, asi izvi hazviwanzo kudikanwa.

Muenzaniso weimwe yezasi nhanho masikweya:

Uye heano akati wandei epasi rose kubva kuXAPI purojekiti: inomiririra index pane globals:

global ^nzira aishandiswa kuchengeta mapoinzi polylines (migwagwa, nzizi duku, etc.) uye polygons (nzvimbo dzakavharwa: zvivakwa, masango, nezvimwewo).

Rough classification yekushandiswa kwe sparse arrays pane zvepasi rose.

1. Isu tinochengeta kurongeka kwezvimwe zvinhu uye nyika dzazvo (mepu, cellular automata)
2. Tinochengeta matrices mashoma.

Panyaya 2) kana uchikumbira kurongeka chaiko uko chinhu chisina kupihwa kukosha, isu tinofanirwa kuwana kukosha kweiyo default sparse array element.

Mabhonasi atinogashira kana tichichengeta multidimensional matrices mupasi rose

Kurumidza bvisa uye/kana sarudza zvimedu zvemuchadenga zvakapetwa mitsara, ndege, cubes, nezvimwe. Panyaya dzinoshandiswa nhamba dzakakwana, kukwanisa kubvisa nekukasira kubvisa uye/kana kutora machunks enzvimbo anowanza mitsetse, ndege, machubhu, nezvimwe zvinogona kubatsira.

team Uraya tinogona kudzima chinhu chimwe chete kana mutsara, kana kunyange ndege yese. Nekuda kwezvimiro zvepasirese, izvi zvinoitika nekukurumidza - zviuru zvenguva nekukurumidza kupfuura element-ne-element kubviswa.

Nhamba yacho inoratidza matatu-dimensional array mupasi rose ^a nemhando dzakasiyana dzekudzima.

Kuti usarudze zvidimbu zvenzvimbo uchishandisa ma index anozivikanwa, unogona kushandisa murairo Batanidza.

Kusarudza matrix column muColumn variable:

; Зададим трёхмерный разреженный массив 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

Mhedziso:

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

Chii chinonakidza nezve Column kusiyanisa ndechekuti isu zvakare tine sparse array, iyo inofanirwawo kuwanikwa kuburikidza $GET, sezvo default tsika dzisina kuchengetwa mairi.

Kusarudza zvidimbu zvepakati zvinogonawo kuitwa kuburikidza nepurogiramu duku uchishandisa basa $Order. Izvi zvinonyanya nyore pane nzvimbo dzine ma indices asina kuverengerwa (cartography).

mhedziso

Nguva dzazvino dzinoisa mabasa matsva ekuda. Magirafu anogona kuumbwa nemabhiriyoni emavertices, mepu dzakagadzirwa nemabhiriyoni emapoinzi, uye vamwe vangatoda kumhanyisa chadenga chavo pacellular automata (1, 2).

Kana iyo vhoriyamu yedata kubva kune sparse arrays isingachakwanise kukwana mu RAM, asi iwe unofanirwa kushanda navo, saka zvakakosha kufunga nezve mukana wekuita mapurojekiti akafanana paglobals neCOS.

Ndinokutendai nekuteerera kwenyu! Isu takamirira mibvunzo yako uye zvishuwo mumhinduro.

Disclaimer: Ichi chinyorwa uye zvandinotaura kwazviri maonero angu uye hazvina hukama nenzvimbo yepamutemo yeInterSystems Corporation.

Source: www.habr.com