Fil-partijiet preċedenti (, ) tkellimna dwar globali bħala siġar, f'dan wieħed se nħarsu lejn globali bħala arrays sparse.
huwa tip ta 'firxa li fiha ħafna mill-valuri jieħdu l-istess valur.
Fil-prattika, l-arrays skarsi huma ħafna drabi tant enormi li m'hemm l-ebda skop li tokkupa memorja b'elementi identiċi. Għalhekk, jagħmel sens li jiġu implimentati arrays sparse b'tali mod li l-memorja ma tinħelax fuq il-ħażna ta 'valuri identiċi.
F'xi lingwi ta' programmar, arrays sparse huma inklużi fil-lingwa nnifisha, , . Lingwi ta 'programmar oħra għandhom libreriji speċjali li jippermettulek timplimentahom. Għal C++ - и др.
Il-Globals huma kandidati tajbin għall-implimentazzjoni ta' arrays sparse minħabba li:
- Huma jaħżnu l-valuri ta 'ċerti nodi biss u ma jaħżnux il-valuri ta' dawk mhux definiti;
- L-interface għall-aċċess għall-valur ta 'node huwa estremament simili għal kemm lingwi ta' programmar jimplimentaw aċċess għal element ta 'firxa multidimensjonali.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Globali hija struttura ta 'livell pjuttost baxx għall-ħażna tad-dejta, għalhekk għandha karatteristiċi ta' veloċità pendenti (minn mijiet ta 'eluf għal għexieren ta' miljuni ta 'tranżazzjonijiet kull sekonda, skond il-hardware, ara hawn taħt). )
Peress li l-globali hija struttura persistenti, jagħmel sens li jinħolqu arrays sparse fuqhom meta jkun magħruf minn qabel li l-ammont ta 'RAM mhux se jkun biżżejjed.
Waħda mill-proprjetajiet ta 'implimentazzjonijiet ta' firxa skarsa hija li tirritorna xi valur default jekk isir aċċess għal ċellula mhux definita.
Dan jista 'jiġi implimentat bl-użu tal-funzjoni fil-COS. Dan l-eżempju jqis firxa 3-dimensjonali.
SET a = $GET(^a(x,y,z), defValue)Liema kompiti jeħtieġu firxa skarsi u kif jistgħu jgħinu l-globali?
Matriċi ta' adjaċenza (konnettività).
użati biex jirrappreżentaw graffs:
Ovvjament, iktar ma jkun kbir il-graff, iktar ikun hemm żerijiet fil-matriċi. Jekk, pereżempju, nieħdu graff tan-netwerk soċjali u nippreżentawha fil-forma ta 'matriċi simili, allura se tikkonsisti kważi kompletament f'żeri, i.e. se jkun firxa skarsa.
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
....
F'dan l-eżempju, aħna niffrankaw globalment ^m matriċi tal-konnettività, kif ukoll in-numru ta 'truf f'kull nodu (min huwa ħbieb ma' min u n-numru ta 'ħbieb).
Jekk in-numru ta' elementi fil-graff ma jkunx aktar minn 29 miljun (dan in-numru jittieħed bħala l-prodott ta' 8 * ), jiġifieri, mod saħansitra aktar ekonomiku biex jinħażnu tali matriċi huwa strings bit, peress li l-implimentazzjoni tagħhom tottimizza lakuni kbar b'mod speċjali.
Manipulazzjonijiet b'kordi tal-bit huma mwettqa mill-funzjoni .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabella tat-tranżizzjoni tal-magna tal-Istat
Peress li l-graff ta 'tranżizzjoni ta' awtomat finit huwa graff ordinarju, allura t-tabella ta 'transizzjoni ta' l-awtom finit hija l-istess matriċi ta 'adjaċenza diskussa hawn fuq.
Awtomati ċellulari
L-aktar awtomat ċellulari famuż huwa , li, minħabba r-regoli tagħha (meta ċellola jkollha ħafna ġirien, tmut) hija firxa skarsa.
Stephen Wolfram jemmen li l-awtomati ċellulari huma . Fl-2002, ippubblika ktieb ta’ 1280 paġna, A New Kind of Science, li fih jargumenta b’mod ġenerali li l-avvanzi fl-awtomati ċellulari mhumiex iżolati, iżda huma dejjiema u għandhom implikazzjonijiet kbar għall-oqsma kollha tax-xjenza.
Ġie ppruvat li kwalunkwe algoritmu eżekutibbli fuq kompjuter jista 'jiġi implimentat bl-użu ta' awtomat ċellulari. L-awtomati ċellulari jintużaw biex jimmudellaw ambjenti u sistemi dinamiċi, biex isolvu problemi algoritmiċi u għal skopijiet oħra.
Jekk ikollna qasam enormi u għandna bżonn nirreġistraw l-istati intermedji kollha ta 'awtomat ċellulari, allura jagħmel sens li tuża globali.
Kartografija
L-ewwel ħaġa li tiġi f'moħħi meta niġu għall-użu ta 'arrays sparse hija l-kompiti tal-mapping.
Bħala regola, hemm ħafna spazju vojt fuq il-mapep. Jekk il-mappa hija rappreżentata bħala pixels kbar, allura 71% tal-pixels tad-Dinja jkunu okkupati mill-oċean. Array skars. U jekk tapplika biss xogħlijiet ta 'idejn tal-bniedem, allura l-ispazju vojt ikun aktar minn 95%.
Naturalment, ħadd ma jaħżen mapep fil-forma ta 'arrays raster; hija użata rappreżentazzjoni ta' vettur.
Imma x'inhuma l-mapep tal-vettur? Dan huwa tip ta 'qafas u polylines u poligoni li jikkonsistu f'punti.
Essenzjalment database ta 'punti u konnessjonijiet bejniethom.
Waħda mill-missjonijiet tal-mapping l-aktar ambizzjużi hija l-missjoni tat-Teleskopju Gaia biex timmappja l-galaxie tagħna. B'mod figurattiv, il-galaxie tagħna, bħall-univers kollu, hija firxa skarsi kontinwa: spazji kbar ta 'vojt li fihom hemm punti żgħar rari - stilel. L-ispazju vojt huwa 99,999999…….%. Biex tinħażen il-mappa tal-galaxie tagħna, intgħażlet database globali - Caché.
Ma nafx l-istruttura eżatta tal-globals f'dan il-proġett, nista' nassumi li hija xi ħaġa simili għal:
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
...
Fejn huma b, l, d u d-distanza għax-Xemx.
L-istruttura flessibbli tal-globals tippermettilek li tiffranka kwalunkwe karatteristika meħtieġa ta 'stilel u pjaneti, peress li l-bażijiet fuq globali huma skemi inqas.
Biex taħżen il-mappa tal-univers tagħna, Caché intgħażel mhux biss għall-flessibbiltà tiegħu, iżda wkoll għall-kapaċità tiegħu li jaħżen fluss ta 'dejta malajr ħafna, filwaqt li fl-istess ħin joħloq indiċi globali għal tfittxijiet veloċi.
Jekk nerġgħu lura lejn id-Dinja, allura nħolqu proġetti kartografiċi fuq globali u furketta ta' OpenStreetMap - .
Riċentement fuq ġew implimentati indiċijiet ġeospazjali . Qed nistennew artiklu mill-awturi bid-dettalji tal-implimentazzjoni.
Implimentazzjoni ta 'indiċi spazjali fuq globali f'OpenStreetMap XAPI
Stampi meħuda minn .
Il-globu kollu huwa maqsum fi kwadri, imbagħad sub-kwadri, u sub-kwadri f'sub-sub-kwadri, eċċ. B'mod ġenerali, niksbu struttura ġerarkika għall-ħażna ta' liema globali huma maħluqa.
Fi kwalunkwe mument, nistgħu kważi istantanjament nitolbu l-kwadru mixtieq jew inaddfuh, u s-sub-kwadri kollha jiġu rritornati jew ikklerjati wkoll.
Skema simili fuq globali tista 'tiġi implimentata f'diversi modi.
Għażla 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ВторойТочки
...Għażla 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Fiż-żewġ każijiet, mhuwiex diffiċli li tuża COS/M biex titlob punti li jinsabu fi kwadru ta 'kwalunkwe livell. Ikun kemmxejn aktar faċli li jitnaddfu biċċiet kwadri ta 'spazju fi kwalunkwe livell fl-ewwel għażla, iżda dan rarament huwa meħtieġ.
Eżempju ta' wieħed mill-kwadri tal-livell aktar baxx:
U hawn diversi globali mill-proġett XAPI: rappreżentazzjoni ta 'indiċi fuq globali:
globali ^ mod użati biex jaħżnu punti (toroq, xmajjar żgħar, eċċ.) u poligoni (żoni magħluqa: bini, foresti, eċċ.).
Klassifikazzjoni approssimattiva tal-użu ta 'arrays sparse fuq globali....
- Aħna naħżnu l-koordinati ta 'ċerti oġġetti u l-istati tagħhom (mapping, awtoma ċellulari)
- Aħna naħżnu matriċi skarsa.
Għall-każ 2) meta titlob koordinata speċifika fejn l-element ma jiġix assenjat valur, irridu nġibu l-valur tal-element default sparse array.
Bonuses li nirċievu meta naħżnu matriċi multidimensjonali fil-globals
Neħħi u/jew agħżel malajr biċċiet ta 'spazju li huma multipli ta' ringieli, pjani, kubi, eċċ. Għal każijiet fejn jintużaw indiċijiet interi, l-abbiltà li jitneħħew u/jew jinġabru malajr biċċiet ta' spazju li huma multipli ta' ringieli, pjani, kubi, eċċ.
tim nistgħu nħassru jew element wieħed jew ringiela, jew saħansitra pjan sħiħ. Grazzi għall-proprjetajiet tal-globals, dan iseħħ malajr ħafna - eluf ta 'darbiet aktar malajr mit-tneħħija element b'element.
Il-figura turi firxa tridimensjonali f'globali ^a u tipi differenti ta' tħassir.
Biex tagħżel biċċiet ta 'spazju billi tuża indiċi magħrufa, tista' tuża l-kmand .
L-għażla ta' kolonna tal-matriċi fil-varjabbli tal-Kolonna:
; Зададим трёхмерный разреженный массив 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
Konklużjoni:
Column(0)=1
Column(2)=1
Dak li hu interessanti dwar il-varjabbli Kolonna huwa li għandna wkoll firxa skarsa, li trid tiġi aċċessata wkoll permezz , peress li l-valuri awtomatiċi mhumiex maħżuna fiha.
L-għażla ta 'biċċiet ta' spazju tista 'ssir ukoll permezz ta' programm żgħir li juża l-funzjoni . Dan huwa speċjalment konvenjenti fuq spazji li l-indiċi tagħhom mhumiex kwantizzati (kartografija).
Konklużjoni
Iż-żminijiet attwali joħolqu kompiti ambizzjużi ġodda. Il-grafiċi jistgħu jkunu magħmula minn biljuni ta’ vertiċi, mapep magħmulin minn biljuni ta’ punti, u xi wħud jistgħu saħansitra jkunu jridu jmexxu l-univers tagħhom stess fuq l-awtomati ċellulari (, ).
Meta l-volum ta 'dejta minn arrays skars ma jistax jibqa' jidħol fis-RAM, iżda għandek bżonn taħdem magħhom, allura ta 'min jikkunsidra l-possibbiltà li jiġu implimentati proġetti simili fuq globali u COS.
Grazzi tal-attenzjoni tiegħek! Qed nistennew il-mistoqsijiet u x-xewqat tiegħek fil-kummenti.
Ċaħda ta 'responsabbiltà: Dan l-artikolu u l-kummenti tiegħi għalih huma l-opinjoni tiegħi u m'għandhom l-ebda relazzjoni mal-pożizzjoni uffiċjali ta' InterSystems Corporation.
Sors: www.habr.com