Az előző részekben (, ) a globálisokról mint fákról beszéltünk, ebben a globalokra ritka tömbökként fogunk tekinteni.
egy olyan tömbtípus, amelyben a legtöbb érték ugyanazt az értéket veszi fel.
A gyakorlatban a ritka tömbök gyakran olyan hatalmasak, hogy nincs értelme a memóriát azonos elemekkel elfoglalni. Ezért célszerű a ritka tömböket úgy megvalósítani, hogy a memóriát ne pazaroljuk el azonos értékek tárolására.
Néhány programozási nyelvben ritka tömbök szerepelnek magában a nyelvben, , . Más programozási nyelvek speciális könyvtárakkal rendelkeznek, amelyek lehetővé teszik azok megvalósítását. C++ esetén - stb
A globalok jó jelöltek ritka tömbök megvalósítására, mert:
- Csak bizonyos csomópontok értékeit tárolják, és nem tárolják a meghatározatlanok értékeit;
- A csomópont értékéhez való hozzáférés interfésze rendkívül hasonló ahhoz, hogy hány programozási nyelv valósítja meg a hozzáférést egy többdimenziós tömbelemhez.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - A Global egy meglehetősen alacsony szintű adattárolási struktúra, ezért kiemelkedő sebességi jellemzőkkel rendelkezik (hardvertől függően másodpercenként százezertől több tízmillió tranzakcióig, lásd alább). )
Mivel a global egy állandó struktúra, érdemes ritka tömböket létrehozni rajtuk, ha előre tudjuk, hogy a RAM mennyisége nem lesz elég.
A ritka tömb-megvalósítások egyik tulajdonsága, hogy visszaadnak valamilyen alapértelmezett értéket, ha nem definiált cellához férnek hozzá.
Ez a függvény segítségével valósítható meg a COS-ben. Ez a példa egy 3-dimenziós tömböt vesz figyelembe.
SET a = $GET(^a(x,y,z), defValue)Milyen feladatok igényelnek ritka tömböket, és hogyan segíthetnek a globalok?
Szomszédsági (csatlakozási) mátrix
grafikonok ábrázolására használják:
Nyilvánvaló, hogy minél nagyobb a grafikon, annál több nulla lesz a mátrixban. Ha például veszünk egy közösségi hálózat gráfot, és egy hasonló mátrix formájában mutatjuk be, akkor az szinte teljes egészében nullákból fog állni, pl. ritka tömb lesz.
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
....
Ebben a példában globálisan mentünk ^m kapcsolódási mátrix, valamint az egyes csomópontok éleinek száma (ki kivel barát, és hány barát).
Ha a grafikon elemeinek száma nem több 29 milliónál (ezt a számot 8* szorzatának tekintjük ), vagyis az ilyen mátrixok tárolásának még gazdaságosabb módja a bitkarakterlánc, mivel megvalósításuk speciális módon optimalizálja a nagy hézagokat.
A bitsorokkal végzett manipulációkat a függvény hajtja végre .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Állapotgép átmeneti táblázat
Mivel egy véges automata átmeneti gráfja egy közönséges gráf, ezért a véges automata átmeneti táblázata ugyanaz a szomszédsági mátrix, amelyet fentebb tárgyaltunk.
Sejtes automaták
A leghíresebb sejtautomata az , amely szabályaiból adódóan (ha egy cellának sok szomszédja van, elhal) ritka tömb.
Stephen Wolfram úgy véli, hogy a sejtautomaták azok . 2002-ben kiadott egy 1280 oldalas könyvet A New Kind of Science címmel, amelyben nagy vonalakban kifejti, hogy a sejtautomaták fejlődése nem elszigetelt, hanem tartós, és a tudomány minden területére nagy hatással van.
Bebizonyosodott, hogy bármilyen számítógépen végrehajtható algoritmus megvalósítható cellás automata segítségével. A cellás automatákat dinamikus környezetek és rendszerek modellezésére, algoritmikus problémák megoldására és egyéb célokra használják.
Ha hatalmas mezővel rendelkezünk, és fel kell jegyeznünk egy sejtautomata összes köztes állapotát, akkor van értelme a globalok használatának.
Térképészet
Az első dolog, ami eszembe jut, amikor ritka tömbökről van szó, a leképezési feladatok.
Általában sok üres hely van a térképeken. Ha a térképet nagy képpontokként ábrázolják, akkor a Föld képpontjainak 71%-át az óceán fogja elfoglalni. Ritka tömb. És ha csak emberi kéz műveit alkalmazza, akkor az üres hely több mint 95%.
Természetesen senki sem tárolja a térképeket raszteres tömbök formájában, vektoros ábrázolást használunk.
De mik is azok a vektoros térképek? Ez egyfajta keret és vonalláncok és sokszögek, amelyek pontokból állnak.
Lényegében a pontok és a köztük lévő kapcsolatok adatbázisa.
Az egyik legambiciózusabb térképészeti küldetés a Gaia teleszkóp küldetése, amely galaxisunkat térképezi fel. Képletesen szólva, galaxisunk, mint az egész univerzum, egy folytonos ritka tömb: hatalmas üres terek, amelyekben ritka kis pontok - csillagok - találhatók. Az üres hely 99,999999…….%. Galaxisunk térképének tárolására egy globális adatbázist választottunk - a Cachét.
Nem ismerem a globálisok pontos felépítését ebben a projektben, feltételezhetem, hogy valami hasonló, mint:
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
...
Ahol b, l, d van és a Nap távolságától.
A globálisok rugalmas szerkezete lehetővé teszi a csillagok és bolygók minden szükséges jellemzőjének elmentését, mivel a globálisok alapjai séma nélküliek.
Univerzumunk térképének tárolására a Cachét nemcsak rugalmassága miatt választották, hanem azért is, mert képes nagyon gyorsan tárolni egy adatfolyamot, miközben egyidejűleg indexglobálisokat is létrehoz a gyors keresésekhez.
Ha visszatérünk a Földre, akkor térképészeti projektek jöttek létre a globálisokon és egy kis OpenStreetMap - .
Nemrég be térinformatikai indexeket valósítottak meg . Várjuk a szerzők cikkét a megvalósítás részleteivel.
Térbeli indexek megvalósítása globálisan az OpenStreetMap XAPI-ban
A képek innen származnak .
Az egész földgömb négyzetekre van osztva, majd résznégyzetekre, az alnégyzetek pedig alnégyzetekre, és így tovább. Általában egy hierarchikus struktúrát kapunk a létrejött globalok tárolására.
Bármelyik pillanatban szinte azonnal lekérhetjük vagy törölhetjük a kívánt négyzetet, és az összes résznégyzet is visszakerül vagy törlődik.
Egy hasonló sémát a globalokon többféleképpen is meg lehet valósítani.
Opció 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ВторойТочки
...Opció 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Mindkét esetben nem nehéz a COS/M segítségével bármilyen szintű négyzetben elhelyezkedő pontokat lekérni. Valamivel könnyebb lesz megtisztítani a négyzet alakú helydarabokat bármely szinten az első opcióban, de erre ritkán van szükség.
Példa az egyik alsó szintű négyzetre:
És itt van néhány globális az XAPI projektből: egy index ábrázolása a globalokon:
globális ^ módon pontok tárolására szolgál (utak, kis folyók stb.) és poligonok (zárt területek: épületek, erdők stb.).
A ritka tömbök használatának durva osztályozása globálisokon.
- Tároljuk egyes objektumok koordinátáit és állapotukat (leképezés, cellás automaták)
- Ritka mátrixokat tárolunk.
A 2) esetben, amikor egy adott koordinátát kérünk, ahol az elemhez nincs érték hozzárendelve, az alapértelmezett ritka tömbelem értékét kell megkapnunk.
Bónuszok, amelyeket akkor kapunk, ha többdimenziós mátrixokat tárolunk globálisokban
Gyorsan távolítsa el és/vagy válassza ki a sorok, síkok, kockák stb. többszörösei. Azokban az esetekben, amikor egész indexeket használnak, hasznos lehet a sorok, síkok, kockák stb. többszöröseinek gyors eltávolítása és/vagy lekérése.
Csapat törölhetünk akár egy elemet vagy egy sort, de akár egy egész síkot is. A globalok tulajdonságainak köszönhetően ez nagyon gyorsan megtörténik – ezerszer gyorsabban, mint az elemenkénti eltávolítás.
Az ábra egy háromdimenziós tömböt ábrázol globálisban ^a és különböző típusú törlések.
A térrészek ismert indexek használatával történő kiválasztásához használhatja a parancsot .
Mátrixoszlop kiválasztása az Oszlop változóba:
; Зададим трёхмерный разреженный массив 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
Következtetés:
Column(0)=1
Column(2)=1
Az oszlopváltozó érdekessége, hogy van egy ritka tömbünk is, amelyet szintén ezen keresztül kell elérni , mivel az alapértelmezett értékek nem tárolódnak benne.
A térrészek kijelölése egy kis programon keresztül is elvégezhető a funkció segítségével . Ez különösen kényelmes olyan tereken, amelyek indexei nincsenek kvantált (kartográfia).
Következtetés
A jelenlegi idők új, ambiciózus feladatok elé állítanak. A grafikonok több milliárd csúcsból, a térképek többmilliárd pontból állhatnak, és egyesek akár saját univerzumot is futtathatnak sejtautomatákon (, ).
Ha a ritka tömbökből származó adatok mennyisége már nem fér bele a RAM-ba, de dolgoznia kell velük, akkor érdemes megfontolni a hasonló projektek megvalósításának lehetőségét a globalokon és a COS-en.
Köszönöm a figyelmet! Kérdéseiket, kívánságaikat kommentben várjuk.
A felelősség megtagadása: Ez a cikk és a hozzá fűzött megjegyzéseim az én véleményem, és nincs összefüggésben az InterSystems Corporation hivatalos álláspontjával.
Forrás: will.com