Sa mga nakaraang bahagi (, ) napag-usapan natin ang tungkol sa mga global bilang mga puno, sa isang ito ay titingnan natin ang mga global bilang mga kalat-kalat na array.
ay isang uri ng array kung saan ang karamihan sa mga value ay may parehong halaga.
Sa pagsasagawa, ang mga kalat-kalat na array ay kadalasang napakalaki na walang punto sa pag-okupa ng memorya ng magkaparehong elemento. Samakatuwid, makatuwirang ipatupad ang mga kalat-kalat na array sa paraang hindi masasayang ang memorya sa pag-iimbak ng magkatulad na mga halaga.
Sa ilang mga programming language, ang mga kalat-kalat na array ay kasama sa mismong wika, , . Ang iba pang mga programming language ay may mga espesyal na library na nagpapahintulot sa iyo na ipatupad ang mga ito. Para sa C++ - at iba pa
Ang mga global ay mahusay na kandidato para sa pagpapatupad ng mga kalat-kalat na array dahil:
- Iniimbak nila ang mga halaga ng ilang mga node lamang at hindi iniimbak ang mga halaga ng mga hindi natukoy;
- Ang interface para sa pag-access sa halaga ng isang node ay lubos na katulad sa kung gaano karaming mga programming language ang nagpapatupad ng access sa isang multidimensional array element.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Ang Global ay isang medyo mababang antas na istraktura para sa pag-iimbak ng data, samakatuwid mayroon itong natitirang mga katangian ng bilis (mula sa daan-daang libo hanggang sampu-sampung milyong mga transaksyon sa bawat segundo, depende sa hardware, tingnan sa ibaba). )
Dahil ang pandaigdigan ay isang paulit-ulit na istraktura, makatuwiran na lumikha ng mga kalat-kalat na array sa mga ito kapag alam nang maaga na ang halaga ng RAM ay hindi magiging sapat.
Ang isa sa mga katangian ng mga kalat-kalat na pagpapatupad ng array ay ang pagbabalik ng ilang default na halaga kung ang isang pag-access ay ginawa sa isang hindi natukoy na cell.
Ito ay maaaring ipatupad gamit ang function sa COS. Isinasaalang-alang ng halimbawang ito ang isang 3-dimensional na array.
SET a = $GET(^a(x,y,z), defValue)Anong mga gawain ang nangangailangan ng kalat-kalat na array at paano makakatulong ang mga global?
Adjacency (connectivity) matrix
ginamit upang kumatawan sa mga graph:
Malinaw, mas malaki ang graph, mas maraming mga zero ang magkakaroon sa matrix. Kung, halimbawa, kumuha kami ng isang graph ng social network at ipinakita ito sa anyo ng isang katulad na matrix, kung gayon ito ay halos ganap na binubuo ng mga zero, i.e. magiging kalat-kalat na hanay.
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
....
Sa halimbawang ito, nagtitipid tayo sa buong mundo ^m connectivity matrix, pati na rin ang bilang ng mga gilid sa bawat node (sino ang kaibigan kung kanino at ang bilang ng mga kaibigan).
Kung ang bilang ng mga elemento sa graph ay hindi hihigit sa 29 milyon (ang bilang na ito ay kinuha bilang produkto ng 8 * ), iyon ay, ang isang mas matipid na paraan upang mag-imbak ng mga naturang matrice ay mga bit string, dahil ang kanilang pagpapatupad ay nag-optimize ng malalaking gaps sa isang espesyal na paraan.
Ang mga manipulasyon na may bit string ay ginagawa ng function .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Talaan ng paglipat ng makina ng estado
Dahil ang transition graph ng isang finite automaton ay isang ordinaryong graph, kung gayon ang transition table ng finite automaton ay ang parehong adjacency matrix na tinalakay sa itaas.
Cellular na automata
Ang pinakasikat na cellular automat ay , na, dahil sa mga panuntunan nito (kapag ang isang cell ay maraming kapitbahay, namamatay ito) ay isang kalat-kalat na hanay.
Naniniwala si Stephen Wolfram na ang cellular automata ay . Noong 2002, naglathala siya ng 1280-pahinang aklat, A New Kind of Science, kung saan malawak niyang pinagtatalunan na ang mga pag-unlad sa cellular automata ay hindi nakahiwalay, ngunit nagtatagal at may malaking implikasyon para sa lahat ng larangan ng agham.
Napatunayan na ang anumang algorithm na maipapatupad sa isang computer ay maaaring ipatupad gamit ang isang cellular automaton. Ginagamit ang cellular automata upang magmodelo ng mga dynamic na kapaligiran at system, upang malutas ang mga problema sa algorithm at para sa iba pang mga layunin.
Kung mayroon tayong napakalaking larangan at kailangan nating itala ang lahat ng intermediate na estado ng isang cellular automaton, makatuwirang gumamit ng mga global.
Kartograpiya
Ang unang bagay na pumapasok sa isip ko pagdating sa paggamit ng mga kalat-kalat na array ay ang mga gawain sa pagmamapa.
Bilang isang patakaran, mayroong maraming walang laman na espasyo sa mga mapa. Kung ang mapa ay kinakatawan bilang malalaking pixel, 71% ng mga pixel ng Earth ang sasakupin ng karagatan. Kalat-kalat na hanay. At kung ilalapat mo lamang ang mga gawa ng mga kamay ng tao, kung gayon ang walang laman na espasyo ay higit sa 95%.
Siyempre, walang nag-iimbak ng mga mapa sa anyo ng mga raster array; isang representasyon ng vector ang ginagamit.
Ngunit ano ang mga mapa ng vector? Ito ay isang uri ng frame at polyline at polygon na binubuo ng mga puntos.
Mahalagang database ng mga punto at koneksyon sa pagitan nila.
Ang isa sa mga pinakaambisyoso na misyon sa pagmamapa ay ang misyon ng Gaia Telescope na imapa ang ating kalawakan. Sa makasagisag na pagsasalita, ang ating kalawakan, tulad ng buong uniberso, ay isang tuluy-tuloy na kalat-kalat na hanay: malalaking espasyo ng kawalan kung saan mayroong mga bihirang maliliit na punto - mga bituin. Ang bakanteng espasyo ay 99,999999…….%. Upang maimbak ang mapa ng ating kalawakan, isang pandaigdigang database ang napili - Caché.
Hindi ko alam ang eksaktong istraktura ng mga global sa proyektong ito, maaari kong ipagpalagay na ito ay katulad ng:
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
...
Nasaan ang b, l, d at distansya sa Araw.
Ang nababaluktot na istraktura ng mga global ay nagbibigay-daan sa iyo na i-save ang anumang mga kinakailangang katangian ng mga bituin at planeta, dahil ang mga batayan sa mga global ay hindi gaanong scheme.
Upang iimbak ang mapa ng ating uniberso, pinili ang Caché hindi lamang para sa kakayahang umangkop nito, ngunit para din sa kakayahang mag-imbak ng stream ng data nang napakabilis, habang sabay na lumilikha ng mga index global para sa mabilis na paghahanap.
Kung babalik tayo sa Earth, ang mga cartographic na proyekto ay ginawa sa mga global at isang tinidor ng OpenStreetMap - .
Kamakailan sa ipinatupad ang mga geospatial index . Naghihintay kami ng isang artikulo mula sa mga may-akda na may mga detalye ng pagpapatupad.
Pagpapatupad ng mga spatial index sa isang pandaigdigan sa OpenStreetMap XAPI
Mga larawan na kinuha mula sa .
Ang buong globo ay nahahati sa mga parisukat, pagkatapos ay mga sub-kuwadrado, at mga sub-kuwadrado sa mga sub-sub-kuwadrado, at iba pa. Sa pangkalahatan, nakakakuha kami ng hierarchical na istraktura para sa pag-iimbak kung aling mga global ang nilikha.
Sa anumang sandali, maaari naming halos agad na hilingin ang nais na parisukat o i-clear ito, at lahat ng mga sub-kuwadrado ay ibabalik o iki-clear din.
Ang isang katulad na pamamaraan sa mga global ay maaaring ipatupad sa maraming paraan.
Pagpipilian 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ВторойТочки
...Pagpipilian 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Sa parehong mga kaso, hindi mahirap gamitin ang COS/M upang humiling ng mga puntos na matatagpuan sa isang parisukat ng anumang antas. Ito ay medyo mas madali upang linisin ang mga parisukat na piraso ng espasyo sa anumang antas sa unang opsyon, ngunit ito ay bihirang kinakailangan.
Isang halimbawa ng isa sa mas mababang antas ng mga parisukat:
At narito ang ilang globals mula sa XAPI project: representasyon ng isang index sa globals:
global ^ paraan ginagamit upang mag-imbak ng mga puntos (mga kalsada, maliliit na ilog, atbp.) at mga polygon (mga saradong lugar: mga gusali, kagubatan, atbp.).
Magaspang na pag-uuri ng paggamit ng mga kalat-kalat na array sa mga global.
- Iniimbak namin ang mga coordinate ng ilang partikular na bagay at ang kanilang mga estado (mapping, cellular automata)
- Nag-iimbak kami ng mga kalat-kalat na matrice.
Para sa kaso 2) kapag humihiling ng isang partikular na coordinate kung saan ang elemento ay hindi nakatalaga ng isang halaga, dapat nating makuha ang halaga ng default na elemento ng sparse array.
Mga bonus na natatanggap namin kapag nag-iimbak ng mga multidimensional na matrice sa mga global
Mabilis na mag-alis at/o pumili ng mga piraso ng espasyo na maramihang mga row, eroplano, cube, atbp. Para sa mga kaso kung saan ginagamit ang mga integer index, maaaring maging kapaki-pakinabang ang kakayahang mabilis na mag-alis at/o kumuha ng mga chunks ng espasyo na maramihang mga row, eroplano, cube, atbp.
Koponan maaari naming tanggalin ang alinman sa isang elemento o isang hilera, o kahit isang buong eroplano. Salamat sa mga pag-aari ng mga global, ito ay nangyayari nang napakabilis - libu-libong beses na mas mabilis kaysa sa pag-alis ng bawat elemento.
Ipinapakita ng figure ang isang three-dimensional na array sa isang global ^a at iba't ibang uri ng pagtanggal.
Upang pumili ng mga piraso ng espasyo gamit ang mga kilalang index, maaari mong gamitin ang command .
Pagpili ng column ng matrix sa variable ng Column:
; Зададим трёхмерный разреженный массив 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
Konklusyon:
Column(0)=1
Column(2)=1
Ano ang kawili-wili sa variable ng Column ay mayroon din kaming kalat-kalat na hanay, na dapat ding ma-access sa pamamagitan ng , dahil ang mga default na halaga ay hindi nakaimbak dito.
Ang pagpili ng mga piraso ng espasyo ay maaari ding gawin sa pamamagitan ng isang maliit na programa gamit ang function . Ito ay lalong maginhawa sa mga puwang na ang mga indeks ay hindi binibilang (cartography).
Konklusyon
Ang kasalukuyang panahon ay nagpapakita ng mga bagong ambisyosong gawain. Ang mga graph ay maaaring binubuo ng bilyun-bilyong vertices, mga mapa na binubuo ng bilyun-bilyong puntos, at maaaring gusto ng ilan na patakbuhin ang sarili nilang uniberso sa cellular automata (, ).
Kapag ang dami ng data mula sa mga kalat-kalat na array ay hindi na magkasya sa RAM, ngunit kailangan mong magtrabaho sa kanila, kung gayon ito ay nagkakahalaga ng pagsasaalang-alang sa posibilidad ng pagpapatupad ng mga katulad na proyekto sa mga global at COS.
Salamat sa iyong atensyon! Naghihintay kami para sa iyong mga katanungan at kagustuhan sa mga komento.
Pagtanggi sa pananagutan: Ang artikulong ito at ang mga komento ko dito ay opinyon ko at walang kaugnayan sa opisyal na posisyon ng InterSystems Corporation.
Pinagmulan: www.habr.com