Ankstesnėse dalyse (, ) kalbėjome apie globalius kaip medžius, šiame į globalius žiūrėsime kaip į retus masyvus.
yra masyvo tipas, kuriame dauguma reikšmių turi tą pačią reikšmę.
Praktiškai reti masyvai dažnai būna tokie didžiuliai, kad nėra prasmės užimti atmintį identiškais elementais. Todėl prasminga retus masyvus įdiegti taip, kad atmintis nebūtų švaistoma identiškų verčių saugojimui.
Kai kuriose programavimo kalbose negausūs masyvai įtraukiami į pačią kalbą, , . Kitos programavimo kalbos turi specialias bibliotekas, leidžiančias jas įgyvendinti. C++ - ir kt.
„Globals“ yra geri kandidatai retiems masyvams įgyvendinti, nes:
- Jie saugo tik tam tikrų mazgų reikšmes ir nesaugo neapibrėžtų mazgų verčių;
- Prieigos prie mazgo vertės sąsaja yra labai panaši į tai, kiek programavimo kalbų įgyvendina prieigą prie daugiamačio masyvo elemento.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global yra gana žemo lygio duomenų saugojimo struktūra, todėl ji pasižymi išskirtinėmis greičio charakteristikomis (nuo šimtų tūkstančių iki dešimčių milijonų operacijų per sekundę, priklausomai nuo aparatinės įrangos, žr. toliau). )
Kadangi globali struktūra yra nuolatinė, prasminga jose kurti retus masyvus, kai iš anksto žinoma, kad RAM nepakaks.
Viena iš negausaus masyvo diegimo savybių yra grąžinti tam tikrą numatytąją reikšmę, jei prieiga prie neapibrėžto langelio.
Tai galima įgyvendinti naudojant funkciją COS. Šiame pavyzdyje nagrinėjamas 3 matmenų masyvas.
SET a = $GET(^a(x,y,z), defValue)Kokioms užduotims atlikti reikia retų masyvų ir kaip gali padėti globaliai?
Gretimo (jungiamumo) matrica
naudojami grafikams pavaizduoti:
Akivaizdu, kad kuo didesnis grafikas, tuo daugiau nulių bus matricoje. Jei, pavyzdžiui, paimsime socialinio tinklo grafiką ir pateiksime jį panašios matricos pavidalu, tai jis beveik visas susidės iš nulių, t.y. bus negausus masyvas.
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
....
Šiame pavyzdyje mes taupome visame pasaulyje ^m ryšio matrica, taip pat briaunų skaičius kiekviename mazge (kas su kuo draugauja ir draugų skaičius).
Jei elementų skaičius grafike yra ne didesnis kaip 29 milijonai (šis skaičius laikomas sandauga iš 8 * ), tai yra, dar ekonomiškesnis būdas saugoti tokias matricas yra bitų eilutės, nes jų įgyvendinimas ypatingu būdu optimizuoja didelius tarpus.
Manipuliacijas bitų eilutėmis atlieka funkcija .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Būsenos mašinų perėjimo lentelė
Kadangi baigtinio automato perėjimo grafikas yra įprastas grafikas, tai baigtinio automato perėjimų lentelė yra ta pati aukščiau aptarta gretimų matrica.
Korinio ryšio automatai
Garsiausias korinis automatas yra , kuris dėl savo taisyklių (kai ląstelė turi daug kaimynų, ji miršta) yra retas masyvas.
Stephenas Wolframas mano, kad ląstelių automatai yra . 2002 m. jis išleido 1280 XNUMX puslapių knygą „A New Kind of Science“, kurioje jis plačiai teigia, kad ląstelių automatų pažanga nėra izoliuota, bet yra ilgalaikė ir turi didelę reikšmę visoms mokslo sritims.
Įrodyta, kad bet koks kompiuteryje vykdomas algoritmas gali būti įgyvendintas naudojant korinio ryšio automatą. Korinio ryšio automatai naudojami dinaminei aplinkai ir sistemoms modeliuoti, algoritminėms problemoms spręsti ir kitiems tikslams.
Jei turime didžiulį lauką ir mums reikia įrašyti visas tarpines korinio automato būsenas, tada prasminga naudoti globalius.
Kartografija
Pirmas dalykas, kuris ateina į galvą, kai reikia naudoti retus masyvus, yra atvaizdavimo užduotys.
Paprastai žemėlapiuose yra daug laisvos vietos. Jei žemėlapis pavaizduotas kaip dideli pikseliai, tada 71% Žemės pikselių užims vandenynas. Retas masyvas. O jei taikysite tik žmogaus rankų darbus, tuščia vieta bus daugiau nei 95%.
Žinoma, niekas nesaugo žemėlapių rastrinių masyvų pavidalu, naudojamas vektorinis vaizdavimas.
Bet kas yra vektoriniai žemėlapiai? Tai savotiškas rėmelis ir polilinijos bei daugiakampiai, susidedantys iš taškų.
Iš esmės taškų ir ryšių tarp jų duomenų bazė.
Viena iš ambicingiausių žemėlapių sudarymo misijų yra Gaia teleskopo misija, skirta mūsų galaktikai. Vaizdžiai tariant, mūsų galaktika, kaip ir visa visata, yra ištisinis negausus masyvas: didžiulės tuštumos erdvės, kuriose yra reti maži taškai – žvaigždės. Tuščia vieta yra 99,999999…….%. Mūsų galaktikos žemėlapiui saugoti buvo pasirinkta pasaulinė duomenų bazė – Caché.
Nežinau tikslios globalių struktūros šiame projekte, galiu manyti, kad tai kažkas panašaus į:
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
...
Kur b, l, d ir atstumas iki Saulės.
Lanksti globalų struktūra leidžia išsaugoti bet kokias būtinas žvaigždžių ir planetų charakteristikas, nes globalių bazėse nėra schemų.
Mūsų visatos žemėlapiui saugoti Caché buvo pasirinktas ne tik dėl lankstumo, bet ir dėl galimybės labai greitai saugoti duomenų srautą, tuo pat metu kuriant indeksų globalius greitoms paieškoms.
Jei grįšime į Žemę, tai kartografiniai projektai buvo kuriami ant globalių ir OpenStreetMap šakutė - .
Neseniai įjungta buvo įgyvendinti geoerdviniai indeksai . Laukiame autorių straipsnio su įgyvendinimo detalėmis.
Erdvinių indeksų diegimas visame pasaulyje OpenStreetMap XAPI
Nuotraukos darytos iš .
Visas gaublys yra padalintas į kvadratus, po to kvadratus, o pokvadračiai į sub-kvadratus ir pan. Apskritai gauname hierarchinę sukurtų globalų saugojimo struktūrą.
Bet kurią akimirką galime beveik akimirksniu paprašyti norimo kvadrato arba jį išvalyti, o visi subkvadratai taip pat bus grąžinti arba išvalyti.
Panaši schema globaliuose gali būti įgyvendinta keliais būdais.
Variantas 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ВторойТочки
...Variantas 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Abiem atvejais nėra sunku naudoti COS/M, kad užklaustumėte taškų, esančių bet kokio lygio kvadrate. Pirmuoju variantu bus šiek tiek lengviau išvalyti kvadratines erdvės dalis bet kuriame lygyje, tačiau tai retai reikalinga.
Vieno iš žemesnio lygio kvadratų pavyzdys:
Ir čia yra keletas XAPI projekto globalių: indekso vaizdavimas globaliuose:
globalus ^ būdas naudojamas taškams saugoti (keliai, mažos upės ir kt.) ir daugiakampiai (uždaros teritorijos: pastatai, miškai ir kt.).
Apytikslė retų masyvų naudojimo globaliuose klasifikacija.
- Saugome tam tikrų objektų koordinates ir jų būsenas (kartojimas, korinio ryšio automatai)
- Saugome retas matricas.
2 atveju, kai prašome konkrečios koordinatės, kai elementui nėra priskirta reikšmė, turime gauti numatytojo reto masyvo elemento reikšmę.
Premijos, kurias gauname saugodami daugiamates matricas globaliuose
Greitai pašalinkite ir (arba) pasirinkite vietos dalis, kurios yra eilučių, plokštumų, kubelių ir kt. kartotiniai. Tais atvejais, kai naudojami sveikųjų skaičių indeksai, gali būti naudinga galimybė greitai pašalinti ir (arba) paimti vietos dalis, kurios yra eilučių, plokštumų, kubelių ir kt. kartotiniai.
komanda galime ištrinti arba vieną elementą, arba eilutę, arba net visą plokštumą. Dėl globalių savybių tai įvyksta labai greitai – tūkstančius kartų greičiau nei elementų pašalinimas.
Paveikslėlyje parodytas trimatis masyvas globaliame ^a ir įvairių tipų ištrynimų.
Norėdami pasirinkti vietos dalis naudodami žinomus indeksus, galite naudoti komandą .
Matricos stulpelio pasirinkimas į stulpelio kintamąjį:
; Зададим трёхмерный разреженный массив 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
Išvada:
Column(0)=1
Column(2)=1
Įdomiausias stulpelio kintamasis yra tai, kad mes taip pat turime nedidelį masyvą, kurį taip pat reikia pasiekti per , nes numatytosios reikšmės jame nesaugomos.
Pasirinkti vietos dalis taip pat galima naudojant nedidelę programą naudojant funkciją . Tai ypač patogu erdvėse, kurių indeksai nėra kvantuojami (kartografija).
išvada
Dabartinis laikas kelia naujų ambicingų užduočių. Grafikai gali būti sudaryti iš milijardų viršūnių, žemėlapiai – iš milijardų taškų, o kai kurie netgi gali norėti paleisti savo visatą korinio ryšio automatuose (, ).
Kai duomenų kiekis iš retų masyvų nebetelpa į RAM, bet reikia su jais dirbti, verta pagalvoti apie galimybę įgyvendinti panašius projektus globaliuose ir COS.
Ačiū už dėmesį! Laukiame Jūsų klausimų ir pageidavimų komentaruose.
Atsakomybės neigimas: Šis straipsnis ir mano komentarai yra mano nuomonė ir nesusiję su oficialia InterSystems Corporation pozicija.
Šaltinis: www.habr.com