En antaŭaj partoj (, ) ni parolis pri globaloj kiel arboj, en ĉi tiu ni rigardos globalojn kiel maldensajn tabelojn.
estas speco de tabelo en kiu la plej multaj el la valoroj prenas la saman valoron.
En praktiko, malabundaj tabeloj ofte estas tiom grandegaj, ke ne utilas okupi memoron per identaj elementoj. Tial, havas sencon efektivigi malabundajn tabelojn tiel ke memoro ne estas malŝparita dum stokado de identaj valoroj.
En kelkaj programlingvoj, malabundaj tabeloj estas inkluditaj en la lingvo mem, , . Aliaj programlingvoj havas specialajn bibliotekojn, kiuj permesas vin efektivigi ilin. Por C++ - kaj aliaj.
Globals estas bonaj kandidatoj por efektivigi malabundajn tabelojn ĉar:
- Ili stokas la valorojn de nur iuj nodoj kaj ne stokas la valorojn de nedifinitaj;
- La interfaco por aliri la valoron de nodo estas ekstreme simila al kiom da programlingvoj efektivigas aliron al plurdimensia tabelelemento.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Tutmonda estas sufiĉe malaltnivela strukturo por stoki datumojn, tial ĝi havas elstarajn rapidajn trajtojn (de centoj da miloj ĝis dekoj da milionoj da transakcioj sekundo, depende de la aparataro, vidu sube). )
Ĉar la tutmonda estas persista strukturo, estas senco krei maldensajn tabelojn sur ili kiam oni scias anticipe, ke la kvanto de RAM ne sufiĉos.
Unu el la trajtoj de maldensaj tabelefektivigoj estas redoni iun defaŭltan valoron se aliro estas farita al nedifinita ĉelo.
Ĉi tio povas esti efektivigita uzante la funkcion en COS. Ĉi tiu ekzemplo konsideras 3-dimensian tabelon.
SET a = $GET(^a(x,y,z), defValue)Kiuj taskoj postulas malabundajn tabelojn kaj kiel globaloj povas helpi?
Matrico de apudeco (konekto).
uzata por reprezenti grafikaĵojn:
Evidente, ju pli granda la grafeo, des pli da nuloj estos en la matrico. Se ni ekzemple prenas socian retan grafeon kaj prezentas ĝin en formo de simila matrico, tiam ĝi preskaŭ tute konsistos el nuloj, t.e. estos maldensa tabelo.
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
....
En ĉi tiu ekzemplo, ni ŝparas tutmonde ^m konektebleca matrico, same kiel la nombro da randoj ĉe ĉiu nodo (kiu estas amikoj kun kiu kaj la nombro da amikoj).
Se la nombro da elementoj en la grafikaĵo ne estas pli ol 29 milionoj (ĉi tiu nombro estas prenita kiel la produkto de 8 * ), tio estas, eĉ pli ekonomia maniero stoki tiajn matricojn estas bitĉenoj, ĉar ilia efektivigo optimumigas grandajn interspacojn laŭ speciala maniero.
Manipuladoj kun bitaj ĉenoj estas faritaj per la funkcio .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Ŝtata maŝino transiro tablo
Ĉar la transira grafeo de finhava aŭtomato estas ordinara grafeo, tiam la transira tablo de la finhava aŭtomato estas la sama apuda matrico diskutita supre.
Ĉelaj aŭtomatoj
La plej fama ĉela aŭtomato estas , kiu, pro siaj reguloj (kiam ĉelo havas multajn najbarojn, ĝi mortas) estas maldensa tabelo.
Stephen Wolfram kredas ke ĉelaj aŭtomatoj estas . En 2002, li publikigis 1280-paĝan libron, A New Kind of Science , en kiu li argumentas larĝe ke progresoj en ĉelaj aŭtomatoj ne estas izolitaj, sed estas eltenemaj kaj havas grandajn implicojn por ĉiuj areoj de scienco.
Estis pruvite ke ĉiu algoritmo plenumebla sur komputilo povas esti efektivigita uzante ĉelan aŭtomaton. Ĉelaj aŭtomatoj estas uzataj por modeligi dinamikajn mediojn kaj sistemojn, por solvi algoritmajn problemojn kaj por aliaj celoj.
Se ni havas grandegan kampon kaj ni bezonas registri ĉiujn mezajn statojn de ĉela aŭtomato, tiam havas sencon uzi globalojn.
Kartografio
La unua afero, kiu venas al mia menso, kiam temas pri uzado de maldensaj tabeloj, estas mapado de taskoj.
Kiel regulo, estas multe da malplena spaco sur mapoj. Se la mapo estas reprezentita kiel grandaj pikseloj, tiam 71% de la pikseloj de la Tero estos okupitaj de la oceano. Maldensa tabelo. Kaj se vi aplikas nur verkojn de homaj manoj, tiam la malplena spaco estos pli ol 95%.
Kompreneble, neniu stokas mapojn en la formo de rastrumaj tabeloj; vektora reprezentado estas uzata.
Sed kio estas vektoraj mapoj? Ĉi tio estas speco de kadro kaj plurlinioj kaj pluranguloj konsistantaj el punktoj.
Esence datumbazo de punktoj kaj ligoj inter ili.
Unu el la plej ambiciaj mapaj misioj estas la Gaia Telescope-misio por mapi nian galaksion. Figure parolante, nia galaksio, kiel la tuta universo, estas kontinua maldensa aro: grandegaj spacoj de malpleno en kiuj estas maloftaj malgrandaj punktoj - steloj. Malplena spaco estas 99,999999…….%. Por konservi la mapon de nia galaksio, oni elektis tutmondan datumbazon - Caché.
Mi ne konas la precizan strukturon de globaloj en ĉi tiu projekto, mi povas supozi, ke ĝi estas io simila 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
...
Kie b, l, d estas kaj distanco al la Suno.
La fleksebla strukturo de tutmondoj permesas vin konservi ajnajn necesajn karakterizaĵojn de steloj kaj planedoj, ĉar la bazoj sur globaloj estas skemaj malpli.
Por stoki la mapon de nia universo, Caché estis elektita ne nur pro sia fleksebleco, sed ankaŭ pro sia kapablo stoki fluon da datumoj tre rapide, samtempe kreante indeksajn tutmondojn por rapidaj serĉoj.
Se ni revenos al la Tero, tiam kreiĝis kartografaj projektoj sur globaloj kaj forko de OpenStreetMap - .
Lastatempe sur geospacaj indeksoj estis efektivigitaj . Ni atendas artikolon de la aŭtoroj kun realigaj detaloj.
Efektivigo de spacaj indeksoj sur tutmonda en OpenStreetMap XAPI
Bildoj prenitaj de .
La tuta globo estas dividita en kvadratojn, poste sub-kvadratojn, kaj sub-kvadratojn en sub-sub-kvadratojn, ktp. Ĝenerale, ni ricevas hierarkian strukturon por stoki kiuj globaloj estas kreitaj.
En ajna momento, ni povas preskaŭ tuj peti la deziratan kvadraton aŭ malplenigi ĝin, kaj ĉiuj subkvadratoj ankaŭ estos resenditaj aŭ purigitaj.
Simila skemo pri globaloj povas esti efektivigita laŭ pluraj manieroj.
Eblo 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ВторойТочки
...Eblo 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...En ambaŭ kazoj, estas ne malfacile uzi COS/M por peti punktojn situantajn en kvadrato de iu nivelo. Estos iom pli facile purigi kvadratajn pecojn de spaco je ajna nivelo en la unua opcio, sed ĉi tio malofte estas necesa.
Ekzemplo de unu el la pli malaltaj kvadratoj:
Kaj jen pluraj globaloj de la projekto XAPI: reprezentado de indekso pri globaloj:
tutmonda ^way uzata por konservi punktojn (vojoj, malgrandaj riveroj, ktp.) kaj pluranguloj (fermitaj areoj: konstruaĵoj, arbaroj, ktp.).
Malglata klasifiko de la uzo de malabundaj tabeloj sur globaloj.
- Ni konservas la koordinatojn de iuj objektoj kaj iliaj statoj (mapado, ĉelaj aŭtomatoj)
- Ni stokas malabundajn matricojn.
Por kazo 2) kiam oni petas specifan koordinaton kie la elemento ne estas asignita valoro, ni devas ricevi la valoron de la defaŭlta maldensa tabelelemento.
Gratifikoj kiujn ni ricevas dum stokado de multdimensiaj matricoj en globaloj
Rapide forigu kaj/aŭ elektu pecojn de spaco kiuj estas multobloj de vicoj, aviadiloj, kuboj, ktp. Por kazoj kie entjeraj indeksoj estas uzitaj, la kapablo rapide forigi kaj/aŭ preni pecojn de spaco kiuj estas multobloj de vicoj, aviadiloj, kuboj, ktp.
teamo ni povas forigi aŭ ununuran elementon aŭ vicon, aŭ eĉ tutan ebenon. Danke al la propraĵoj de globaloj, tio okazas tre rapide - miloble pli rapide ol elemento-post-elementa forigo.
La figuro montras tridimensian tabelon en tutmonda ^a kaj malsamaj specoj de forigoj.
Por elekti pecojn de spaco uzante konatajn indeksojn, vi povas uzi la komandon .
Elektante matrican kolumnon en la Kolonan variablon:
; Зададим трёхмерный разреженный массив 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
Konkludo:
Column(0)=1
Column(2)=1
Kio estas interesa pri la Kolumna variablo estas ke ni ankaŭ havas maldensan tabelon, kiu ankaŭ devas esti alirebla per , ĉar defaŭltaj valoroj ne estas stokitaj en ĝi.
Elektado de pecoj de spaco ankaŭ povas esti farita per malgranda programo uzante la funkcion . Ĉi tio estas precipe oportuna sur spacoj, kies indeksoj ne estas kvantigitaj (kartografio).
konkludo
La nunaj tempoj prezentas novajn ambiciajn taskojn. Grafikaĵoj povas konsisti el miliardoj da verticoj, mapoj el miliardoj da punktoj, kaj iuj eĉ eble volas prizorgi sian propran universon per ĉelaj aŭtomatoj (, ).
Kiam la volumo de datumoj de malabundaj tabeloj ne plu povas konveni en RAM, sed vi devas labori kun ili, tiam indas konsideri la eblecon efektivigi similajn projektojn pri tutmondaj kaj COS.
Dankon pro via atento! Ni atendas viajn demandojn kaj dezirojn en la komentoj.
malgarantio: Ĉi tiu artikolo kaj miaj komentoj al ĝi estas mia opinio kaj havas neniun rilaton al la oficiala pozicio de InterSystems Corporation.
fonto: www.habr.com