Edellisissä osissa (, ) puhuimme globaaleista puista, tässä tarkastellaan globaaleja harvoina taulukoina.
on eräänlainen taulukko, jossa useimmat arvot ovat saman arvon.
Käytännössä harvat taulukot ovat usein niin suuria, ettei muistia ole mielekästä varata identtisillä elementeillä. Siksi on järkevää toteuttaa harvat taulukot siten, että muistia ei tuhlata identtisten arvojen tallentamiseen.
Joissakin ohjelmointikielissä harvat taulukot sisältyvät itse kieleen, , . Muilla ohjelmointikielillä on erityisiä kirjastoja, joiden avulla voit toteuttaa ne. C++:lle - jne.
Globaalit ovat hyviä ehdokkaita harvan taulukon toteuttamiseen, koska:
- Ne tallentavat vain tiettyjen solmujen arvot eivätkä määrittele määrittelemättömien solmujen arvoja;
- Solmun arvon käyttöliittymä on erittäin samanlainen kuin kuinka moni ohjelmointikieli toteuttaa pääsyn moniulotteiseen taulukkoelementtiin.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global on melko matalan tason rakenne tietojen tallentamiseen, joten sillä on erinomaiset nopeusominaisuudet (sadoista tuhansista kymmeniin miljooniin tapahtumiin sekunnissa, laitteistosta riippuen, katso alla). )
Koska globaali on pysyvä rakenne, on järkevää luoda niihin harvat taulukot, kun tiedetään etukäteen, että RAM-muistin määrä ei riitä.
Yksi harvan taulukon toteutusten ominaisuuksista on palauttaa jokin oletusarvo, jos määrittämättömään soluun päästään.
Tämä voidaan toteuttaa funktiolla COS:ssä. Tässä esimerkissä tarkastellaan 3-ulotteista taulukkoa.
SET a = $GET(^a(x,y,z), defValue)Mitkä tehtävät vaativat harvaa taulukkoa ja miten globaalit voivat auttaa?
Vierekkäisyys (liitettävyys) matriisi
käytetään kuvaamaan kaavioita:
Ilmeisesti mitä suurempi graafi on, sitä enemmän nollia matriisissa on. Jos esimerkiksi otamme sosiaalisen verkoston graafin ja esitämme sen samanlaisena matriisina, se koostuu melkein kokonaan nollista, ts. tulee harvakseltaan.
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
....
Tässä esimerkissä säästämme maailmanlaajuisesti ^m yhteysmatriisi sekä kunkin solmun reunojen lukumäärä (kuka on ystävä kenen kanssa ja ystävien määrä).
Jos kaavion elementtien määrä on enintään 29 miljoonaa (tämä luku otetaan 8 * tulona ), eli vielä edullisempi tapa tallentaa tällaisia matriiseja on bittijonot, koska niiden toteutus optimoi suuret aukot erikoisella tavalla.
Funktio suorittaa manipulaatiot bittijonoilla .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tilakoneen siirtymätaulukko
Koska äärellisen automaatin siirtymägraafi on tavallinen graafi, niin äärellisen automaatin siirtymätaulukko on sama viereisyysmatriisi, jota on käsitelty edellä.
Mobiiliautomaatit
Tunnetuin soluautomaatti on , joka sääntöjensä vuoksi (kun solulla on monia naapureita, se kuolee) on harva matriisi.
Stephen Wolfram uskoo, että soluautomaatit ovat . Vuonna 2002 hän julkaisi 1280 XNUMX-sivuisen kirjan A New Kind of Science, jossa hän väittää laajasti, että soluautomaattien edistys ei ole eristetty, vaan se on kestävää ja sillä on suuri merkitys kaikille tieteenaloille.
On todistettu, että mikä tahansa tietokoneella suoritettava algoritmi voidaan toteuttaa solukkoautomaatin avulla. Solukkoautomaatteja käytetään dynaamisten ympäristöjen ja järjestelmien mallintamiseen, algoritmisten ongelmien ratkaisemiseen ja muihin tarkoituksiin.
Jos meillä on valtava kenttä ja meidän on tallennettava kaikki soluautomaatin välitilat, on järkevää käyttää globaaleja.
Kartografia
Ensimmäinen asia, joka tulee mieleeni harvojen taulukoiden käytöstä, on kartoitustehtävät.
Yleensä kartoissa on paljon tyhjää tilaa. Jos kartta esitetään suurina pikseleinä, valtameri peittää 71 % maapallon pikseleistä. Harva joukko. Ja jos käytät vain ihmiskäsien töitä, tyhjä tila on yli 95%.
Kukaan ei tietenkään tallenna karttoja rasteritaulukoiden muodossa, vaan käytetään vektoriesitystä.
Mutta mitä ovat vektorikartat? Tämä on eräänlainen kehys ja pisteistä koostuvat moniviivat ja polygonit.
Pohjimmiltaan tietokanta pisteistä ja niiden välisistä yhteyksistä.
Yksi kunnianhimoisimmista kartoitustehtävistä on Gaia Telescope -tehtävä galaksimme kartoittamiseksi. Kuvaannollisesti sanottuna galaksimme, kuten koko maailmankaikkeus, on jatkuva harvalukuinen joukko: valtavia tyhjiöitä, joissa on harvinaisia pieniä pisteitä - tähtiä. Tyhjä tila on 99,999999……..%. Galaksimme kartan tallentamiseksi valittiin globaali tietokanta - Caché.
En tiedä tarkkaa globaalien rakennetta tässä projektissa, voin olettaa, että se on jotain vastaavaa:
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
...
Missä b, l, d ovat ja etäisyys Auringosta.
Globaalien joustava rakenne mahdollistaa tähtien ja planeettojen tarpeellisten ominaisuuksien tallentamisen, koska globaalien tukikohdat ovat kaavattomia.
Universumimme kartan tallentamiseen Caché valittiin paitsi sen joustavuuden vuoksi, myös sen kyvyn vuoksi tallentaa datavirta hyvin nopeasti ja samalla luoda indeksin globaaleja nopeita hakuja.
Jos palaamme Maahan, kartografiset projektit luotiin globaaleille ja haarukka OpenStreetMap - .
Äskettäin päällä geospatiaaliset indeksit otettiin käyttöön . Odotamme tekijöiltä artikkelia toteutuksen yksityiskohdista.
Tilaindeksien käyttöönotto globaalilla OpenStreetMap XAPI:lla
Kuvat otettu .
Koko maapallo on jaettu neliöihin, sitten osanelioihin ja osaneliöt osaneliöihin ja niin edelleen. Yleensä saamme hierarkkisen rakenteen luotujen globaalien tallentamiseen.
Voimme milloin tahansa lähes välittömästi pyytää halutun neliön tai tyhjentää sen, ja myös kaikki osaruudut palautetaan tai tyhjennetään.
Samanlainen järjestelmä globaaleilla voidaan toteuttaa useilla tavoilla.
Vaihtoehto 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ВторойТочки
...Vaihtoehto 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Molemmissa tapauksissa ei ole vaikeaa käyttää COS/M:tä minkä tahansa tason neliön pisteiden pyytämiseen. Ensimmäisessä vaihtoehdossa on jonkin verran helpompi puhdistaa neliömäisiä tilanosia millä tahansa tasolla, mutta tämä on harvoin välttämätöntä.
Esimerkki yhdestä alemman tason ruudusta:
Ja tässä on useita XAPI-projektin globaaleja: indeksin esitys globaaleilla:
maailmanlaajuisesti ^ tapa käytetään pisteiden tallentamiseen (tiet, pienet joet jne.) ja monikulmiot (suljetut alueet: rakennukset, metsät jne.).
Karkea luokittelu harvan taulukon käytöstä globaaleilla.
- Tallennamme tiettyjen kohteiden koordinaatit ja niiden tilat (kartoitus, soluautomaatit)
- Varastoimme harvat matriisit.
Tapauksessa 2) kun pyydetään tiettyä koordinaattia, jossa elementille ei ole annettu arvoa, meidän on saatava oletusarvoisen harvan taulukon elementin arvo.
Bonukset, joita saamme tallentamalla moniulotteisia matriiseja globaaleihin
Poista ja/tai valitse nopeasti tilan osia, jotka ovat rivien, tasojen, kuutioiden jne. kerrannaisia. Tapauksissa, joissa käytetään kokonaislukuindeksejä, kyky nopeasti poistaa ja/tai noutaa rivien, tasojen, kuutioiden jne. moninkertaisia tilan paloja voi olla hyödyllinen.
tiimi voimme poistaa joko yksittäisen elementin tai rivin tai jopa koko tason. Globaalien ominaisuuksien ansiosta tämä tapahtuu erittäin nopeasti - tuhansia kertoja nopeammin kuin elementtikohtainen poisto.
Kuvassa on kolmiulotteinen taulukko globaalissa muodossa ^a ja erilaiset poistotyypit.
Voit valita tilan osia tunnetuilla indekseillä käyttämällä komentoa .
Matriisisarakkeen valitseminen Column-muuttujaan:
; Зададим трёхмерный разреженный массив 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
Johtopäätös:
Column(0)=1
Column(2)=1
Mielenkiintoista Column-muuttujassa on se, että meillä on myös harva taulukko, johon on myös päästävä , koska oletusarvoja ei tallenneta siihen.
Tilan osien valinta voidaan tehdä myös pienen ohjelman avulla toimintoa käyttämällä . Tämä on erityisen kätevää tiloissa, joiden indeksejä ei ole kvantisoitu (kartografia).
Johtopäätös
Nykyinen aika asettaa uusia kunnianhimoisia tehtäviä. Graafit voivat koostua miljardeista pisteistä, kartat miljardeista pisteistä, ja jotkut saattavat jopa haluta ajaa omaa universumiaan soluautomaateilla (, ).
Kun harvojen taulukoiden datamäärä ei enää mahdu RAM-muistiin, mutta sinun on työskenneltävä niiden kanssa, kannattaa harkita mahdollisuutta toteuttaa vastaavia projekteja globaaleissa ja COS-järjestelmissä.
Kiitos huomiostasi! Odotamme kysymyksiäsi ja toiveitasi kommentteihin.
Vastuun kieltäminen: Tämä artikkeli ja siihen liittyvät kommentit ovat minun mielipiteitäni, eivätkä ne liity InterSystems Corporationin viralliseen kantaan.
Lähde: will.com