A korábbi részekben (, ) a globálisokról mint fáról beszéltünk, ebben a részben a globálisokat szórt tömbökként fogjuk vizsgálni.
– egy olyan tömb típusa, amelyben a legtöbb érték azonos értéket vesz fel.
A gyakorlatban gyakran előfordulnak olyan hatalmas szórt tömbök, hogy nincs értelme memóriát foglalni az azonos elemekkel. Ezért érdemes szórt tömböket megvalósítani úgy, hogy ne pazaroljunk memóriát az azonos értékek tárolására.
Néhány programozási nyelvben a szórt tömbök magukban foglalják a nyelvet, , . Más programozási nyelvekben speciális könyvtárak állnak rendelkezésre, amelyek lehetővé teszik a megvalósítást. C++-hoz: és mások.
A globálisok jó jelöltek a szórt tömbök megvalósítására, mert:
- Csak a bizonyos csomópontok értékeit tárolják, és nem tárolják a meghatározatlan értékeket;
- A csomópont értékéhez való hozzáférés interfésze rendkívül hasonló ahhoz, ahogyan sok programozási nyelvben megvalósítják a többrétű tömb elemeihez való hozzáférést.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - A globális egy elég alacsony szintű adatstruktúra, ezért kiemelkedő sebességgel rendelkezik (százezrektől több tízmillió tranzakcióig másodpercenként, az eszközöktől függően, lásd: )
Mivel a globális egy tartós struktúra, a szórt tömböket akkor érdemes megvalósítani, amikor előre tudjuk, hogy az operatív memória mennyisége nem lesz elegendő.
A szórt tömbök megvalósításainak egyik jellemzője, hogy alapértelmezett értéket adnak vissza, ha egy meghatározatlan cellához fordulunk.
Ezt meg lehet valósítani az használatával a COS-ban. Ebben a példában egy 3 dimenziós tömböt vizsgálunk.
SET a = $GET(^a(x,y,z), defValue)Milyen feladatokhoz szükségesek a szórt tömbök, és hogyan segíthetnek a globálisok?
Kapcsolati mátrix
a grafikonok ábrázolására használják:
Nyilvánvaló, hogy minél nagyobb a grafikon, annál több nullának kell lennie a mátrixban. Ha például egy közösségi hálózat grafikonját vesszük, és hasonló mátrixban ábrázoljuk, akkor az majdnem teljes egészében nullákból fog állni, azaz szórt tömb lesz.
Állítsa be ^m(id1, id2) = 1
Állítsa be ^m(id1, id3) = 1
Állítsa be ^m(id1, id4) = 1
Állítsa be ^m(id1) = 3
Állítsa be ^m(id2, id4) = 1
Állítsa be ^m(id2, id5) = 1
Állítsa be ^m(id2) = 2
....
Ebben a példában globálisan tárolunk ^m a kapcsolatmátrixot, valamint a csúcsokhoz tartozó élek számát (ki kivel barátkozik és hány barátja van).
Ha a gráf elemeinek száma nem haladja meg a 29 milliót (ezt a számot 8 * ), akkor van egy még gazdaságosabb módszer ezen mátrixok tárolására — bitstringek, mivel a megvalósításuk során különösen optimalizáltak a nagy hézagok.
A bitstringekkel végzett manipulációkat a .
funkció végzi; bit beállítása
SET $BIT(rowID, positionID) = 1
; bit lekérdezése
Write $BIT(rowID, positionID)
A végleges automata átmeneti táblázata
Mivel a végleges automata átmeneti gráf egy hagyományos gráf, ezért a végleges automata átmeneti táblázata is ugyanaz a szomszédsági mátrix, amiről már korábban szó esett.
Sejtes automaták
A legismertebb sejtes automata — , amely a szabályai miatt (amikor a sejtnek sok szomszédja van — elhal) egy ritka tömböt képvisel.
Stephen Wolfram úgy véli, hogy a sejtes automata egy . 2002-ben megjelenteti 1280 oldalas könyvét, az 'A New Kind of Science'-t, amelyben széleskörűen érvel, hogy a sejtes automaták terén elért eredmények nem izoláltak, hanem meglehetősen tartósak és nagy jelentőséggel bírnak a tudomány minden területén.
Bizonyították, hogy bármely számítógépen végrehajtható algoritmus megvalósítható sejtes automatával. A sejtes automatákat dinamikus környezetek és rendszerek modellezésére, algoritmikus feladatok megoldására és egyéb célokra használják.
Ha hatalmas mezőnk van, és rögzítenünk kell a sejtes automata minden közbenső állapotát, érdemes globális változókat használni.
Térképészet
Az első dolog, ami eszembe jut, amikor ritka tömbök használatáról van szó — a térképészeti feladatok.
Általában a térképeken nagyon sok üres tér található. Ha a térképet nagy pixelek formájában képzeljük el, a Föld pixeljeinek 71%-a az óceánnal lesz elfoglalva. Ritka tömb. Ha pedig csak az emberi kezek által létrehozott dolgokat ábrázoljuk, akkor az üres terület több mint 95%-ot tesz ki.
Természetesen senki sem tárolja a térképeket raszteres tömbök formájában, vektoros ábrázolást használnak.
De mit is jelentenek a vektor térképek? Ez egyfajta keret, amely pontokból, polilineákból és poligonokból áll.
Tulajdonképpen ez egy pontokból és köztük lévő kapcsolatokból álló adatbázis.
Az egyik legambiciózusabb térképezési feladat a galaxisunk térképezése a Gaia teleszkóppal. Képzeljük el, hogy galaxisunk, akárcsak az egész univerzum, egy folyamatos, ritka mátrix: hatalmas üres terek, amelyekben ritkán előforduló kis pontok — csillagok — találhatók. Az üres hely 99,999999…….%. A galaxisunk térképének tárolására globálokat választottak — Caché.
Nem ismerem pontosan a globálok struktúráját ebben a projektben, de feltételezem, hogy valami hasonló lehet:
Set ^galaxy(b, l, d) = 1; A csillag katalógus szerinti száma, ha van
Set ^galaxy(b, l, d, "name") = "Nap"
Set ^galaxy(b, l, d, "type") = "normál"; lehetőségek: fekete lyuk, kvazár, vörös törpe stb.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Merkúr"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Ahol b, l, d — és a Napig terjedő távolság.
A globálok rugalmas struktúrája lehetővé teszi bármilyen szükséges jellemző tárolását a csillagok és bolygók esetében, mivel a globális adatbázisok séma nélküli (scheme-less).
A galaxisunk térképének tárolására a Cachét nemcsak a rugalmassága miatt választották, hanem azért is, mert rendkívül gyorsan képes adatfolyamokat tárolni, miközben mellékesen index globálokat hoz létre a gyors kereséshez.
Ha visszatérünk a Földre, globálokon térképezési projekteket hoztak létre. és az OpenStreetMap fork — .
Nemrég a geográfiai indexeket valósítottak meg. . Várjuk a cikk szerzőitól a megvalósítás részleteit.
A térbeli indexek megvalósítása a globálban az OpenStreetMap XAPI-ban.
A képek ebből a .
A Föld felszínét négyzetekre osztják, majd azokat alnégyzetekre, az alnégyzeteket pedig újabb alnégyzetekre és így tovább. Ezáltal hierarchikus struktúrát kapunk, amelynek tárolására globálokat hoztak létre.
Bármikor szinte azonnal kérhetjük a szükséges négyzetet vagy annak törlését, miközben az összes alnégyzetet is visszakapjuk vagy töröljük.
Hasonló elrendezést a globálokon többféleképpen meg lehet valósítani.
1. lehetőség:
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 1) = azElsőPontIdje
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 2) = aMásodikPontIdje
...2. lehetőség:
Set ^m('abacdabcdabacdabcda', 1) = idElsőPont
Set ^m('abacdabcdabacdabcda', 2) = idMásodikPont
...Mindkét esetben nem nehéz a COS/M-on megkérni a tetszőleges szintű négyzetben található pontokat. Az első esetben könnyebb lesz a tetszőleges szintű négyzetek területeinek tisztítása, de erre ritkán van szükség.
Egy alsó szintű négyzet példája:
Itt van néhány globális a XAPI projektből: indukciós index a globálisban:
Globális ^way pontok tárolására szolgál (utak, kis folyók stb.) és sokszögek (zárt területek: épületek, erdők stb.).
Durva osztályozás a ritka tömbök globális felhasználásáról.
- Tárhelyezzük bizonyos objektumok koordinátáit és állapotait (térképezés, sejtekkel működő automáták)
- Ritka mátrixokat tárolunk.
A 2. esetben, amikor egy adott koordinátát kérünk, ahol az elemnek nincs hozzárendelt értéke, az alapértelmezett értékét kell kapnunk a ritka tömbből.
Előnyök, amelyeket a többdimenziós mátrixok globális tárolásával kapunk
Gyors törlés és/vagy területek választása, amelyek a sorok, síkok, kockák stb. többévesek. Olyan esetekben, amikor egész számú indexeket használnak, hasznos lehet a területek gyors törlésének és/vagy választásának lehetősége, amelyek a sorok, síkok, kockák stb. többszörösei.
A parancs törölhetünk egyedi elemet, sort, sőt akár egy egész síkot is. A globálisok jellemzőinek köszönhetően ez nagymértékben felgyorsul – ezerrel gyorsabb, mint az elemenkénti törlés.
Az ábrán egy háromdimenziós tömb látható globálisan ^a és különböző törlési módok.
A területek kiválasztásához ismert indexek alapján a .
A mátrix oszlopának kiválasztása a Column változóba:
; Adjuk meg a háromdimenziós ritka tömböt 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)
; Hozzuk létre a Column változót
Zwrite Column
Következtetés:
Column(0)=1
Column(2)=1
Ami érdekes, hogy a Column változóban is egy ritka tömb keletkezett, amelyre szintén a , mivel az alapértelmezett értékek nincsenek benne tárolva.
A területek kiválasztása egy kis programon keresztül is lehetséges a $Order .
Zárás
A jelenlegi időszak új, ambiciózus feladatok elé állít minket. A gráfok milliárdokból álló csúcsokból, a térképek pedig milliárdokból álló pontokból állhatnak, és valaki akár a saját univerzuma létrehozását is meg kívánja valósítani sejtes automaták segítségével (, ).
Amikor a szórt tömbök adatmennyisége már nem fér el a memóriában, de szükség van a velük való munkára, érdemes megfontolni a hasonló projektek megvalósítását globális platformokon és COS-on.
Köszönjük a figyelmet! Várjuk a kérdéseiket és javaslataikat a megjegyzésekben.
Megjegyzés: Ez a cikk és az ehhez fűzött megjegyzéseim a saját véleményemet tükrözik, és nem állnak kapcsolatban az InterSystems vállalat hivatalos álláspontjával.
Forrás: habr.com
