In eerdere delen (, ) spraken we over globalen als bomen, in deze zullen we globalen beschouwen als schaarse arrays.
is een type array waarin de meeste waarden dezelfde waarde hebben.
In de praktijk zijn schaarse arrays vaak zo groot dat het geen zin heeft om geheugen met identieke elementen in beslag te nemen. Daarom is het zinvol om spaarse arrays zo te implementeren dat er geen geheugen wordt verspild aan het opslaan van identieke waarden.
In sommige programmeertalen zijn schaarse arrays in de taal zelf opgenomen, , . Andere programmeertalen hebben speciale bibliotheken waarmee u ze kunt implementeren. Voor C++ - и др.
Globals zijn goede kandidaten voor het implementeren van sparse arrays omdat:
- Ze slaan de waarden van alleen bepaalde knooppunten op en slaan niet de waarden van ongedefinieerde knooppunten op;
- De interface voor toegang tot de waarde van een knooppunt lijkt sterk op het aantal programmeertalen dat toegang tot een multidimensionaal array-element implementeert.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global is een structuur op een vrij laag niveau voor het opslaan van gegevens en heeft daarom uitstekende snelheidskenmerken (van honderdduizenden tot tientallen miljoenen transacties per seconde, afhankelijk van de hardware, zie hieronder). )
Omdat de globale structuur een persistente structuur is, is het zinvol om er spaarzame arrays op te maken als van tevoren bekend is dat de hoeveelheid RAM niet voldoende zal zijn.
Een van de eigenschappen van sparse array-implementaties is het retourneren van een standaardwaarde als toegang wordt verkregen tot een ongedefinieerde cel.
Dit kan worden geïmplementeerd met behulp van de functie in COS. In dit voorbeeld wordt rekening gehouden met een driedimensionale array.
SET a = $GET(^a(x,y,z), defValue)Voor welke taken zijn schaarse arrays nodig en hoe kunnen globals hierbij helpen?
Nabijheidsmatrix (connectiviteit).
gebruikt om grafieken weer te geven:
Het is duidelijk dat hoe groter de grafiek is, hoe meer nullen er in de matrix zullen voorkomen. Als we bijvoorbeeld een sociale netwerkgrafiek nemen en deze presenteren in de vorm van een vergelijkbare matrix, dan zal deze bijna volledig uit nullen bestaan, d.w.z. zal een schaarse array zijn.
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
....
In dit voorbeeld sparen we wereldwijd ^m connectiviteitsmatrix, evenals het aantal randen op elk knooppunt (wie is bevriend met wie en het aantal vrienden).
Als het aantal elementen in de grafiek niet meer dan 29 miljoen bedraagt (dit aantal wordt genomen als het product van 8 * ), dat wil zeggen dat een nog economischere manier om dergelijke matrices op te slaan bitstrings zijn, omdat hun implementatie grote gaten op een speciale manier optimaliseert.
Manipulaties met bitstrings worden door de functie uitgevoerd .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Overgangstabel voor staatsmachines
Omdat de overgangsgrafiek van een eindige automaat een gewone grafiek is, is de overgangstabel van de eindige automaat dezelfde aangrenzende matrix die hierboven is besproken.
Cellulaire automaten
De bekendste cellulaire automaat is , wat vanwege zijn regels (wanneer een cel veel buren heeft, sterft) een schaarse array is.
Stephen Wolfram gelooft dat cellulaire automaten dat wel zijn . In 2002 publiceerde hij een 1280 pagina's tellend boek, A New Kind of Science, waarin hij in grote lijnen betoogt dat de vooruitgang op het gebied van cellulaire automaten niet op zichzelf staat, maar duurzaam is en grote gevolgen heeft voor alle wetenschapsgebieden.
Het is bewezen dat elk algoritme dat op een computer kan worden uitgevoerd, kan worden geïmplementeerd met behulp van een cellulaire automaat. Cellulaire automaten worden gebruikt om dynamische omgevingen en systemen te modelleren, om algoritmische problemen op te lossen en voor andere doeleinden.
Als we een enorm veld hebben en we alle tussenliggende toestanden van een cellulaire automaat moeten registreren, dan is het logisch om globale waarden te gebruiken.
Cartografie
Het eerste waar ik aan denk als het gaat om het gebruik van sparse arrays, zijn het in kaart brengen van taken.
In de regel is er veel lege ruimte op kaarten. Als de kaart wordt weergegeven als grote pixels, wordt 71% van de pixels op aarde ingenomen door de oceaan. Schaarse array. En als je alleen werken van mensenhanden toepast, dan zal de lege ruimte meer dan 95% zijn.
Natuurlijk slaat niemand kaarten op in de vorm van rasterarrays; er wordt gebruik gemaakt van een vectorrepresentatie.
Maar wat zijn vectorkaarten? Dit is een soort frame en polylijnen en polygonen bestaande uit punten.
In wezen een database met punten en verbindingen daartussen.
Een van de meest ambitieuze karteringsmissies is de Gaia Telescope-missie om onze Melkweg in kaart te brengen. Figuurlijk gesproken is ons sterrenstelsel, net als het hele universum, een continue schaarse reeks: enorme ruimtes van leegte waarin zich zeldzame kleine punten bevinden: sterren. Lege ruimte is 99,999999…….%. Om de kaart van onze Melkweg op te slaan, werd gekozen voor een wereldwijde database: Caché.
Ik ken de exacte structuur van globalen in dit project niet, ik kan aannemen dat het iets is dat lijkt op:
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
...
Waar b, l, d zijn en afstand tot de zon.
Dankzij de flexibele structuur van globals kun je alle noodzakelijke kenmerken van sterren en planeten opslaan, omdat de bases op globals geen schema's bevatten.
Om de kaart van ons universum op te slaan, werd Caché niet alleen gekozen vanwege zijn flexibiliteit, maar ook vanwege zijn vermogen om zeer snel een stroom gegevens op te slaan en tegelijkertijd globale indexen te creëren voor snelle zoekopdrachten.
Als we terugkeren naar de aarde, werden er cartografische projecten op de werelden gecreëerd en een vork van OpenStreetMap - .
Onlangs op georuimtelijke indexen werden geïmplementeerd . We wachten op een artikel van de auteurs met implementatiedetails.
Implementatie van ruimtelijke indexen op een globale in OpenStreetMap XAPI
Foto's genomen van .
De hele wereldbol is verdeeld in vierkanten, vervolgens in subvierkanten, en subvierkanten in sub-subvierkanten, enzovoort. Over het algemeen krijgen we een hiërarchische structuur voor het opslaan van de globale gegevens die zijn gemaakt.
Wij kunnen op ieder moment vrijwel direct het gewenste vierkant opvragen of ontruimen, waarbij ook alle subvierkanten worden teruggegeven of ontruimd.
Een soortgelijk plan voor globals kan op verschillende manieren worden geïmplementeerd.
Optie 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ВторойТочки
...Optie 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...In beide gevallen is het niet moeilijk om COS/M te gebruiken om punten op te vragen die zich in een vierkant van elk niveau bevinden. Bij de eerste optie zal het iets eenvoudiger zijn om vierkante stukken ruimte op elk niveau schoon te maken, maar dit is zelden nodig.
Een voorbeeld van een van de vierkanten op een lager niveau:
En hier zijn verschillende globals uit het XAPI-project: weergave van een index op globals:
globaal ^ manier gebruikt om punten op te slaan (wegen, kleine rivieren, etc.) en polygonen (gesloten gebieden: gebouwen, bossen, etc.).
Ruwe classificatie van het gebruik van schaarse arrays op globals.
- We slaan de coördinaten van bepaalde objecten en hun toestanden op (mapping, cellulaire automaten)
- We slaan schaarse matrices op.
Voor geval 2) moeten we bij het aanvragen van een specifieke coördinaat waarbij aan het element geen waarde is toegewezen, de waarde van het standaard sparse array-element verkrijgen.
Bonussen die we ontvangen bij het opslaan van multidimensionale matrices in globalen
Verwijder en/of selecteer snel stukken ruimte die veelvouden zijn van rijen, vlakken, kubussen, enz. Voor gevallen waarin gehele indexen worden gebruikt, kan de mogelijkheid om snel stukjes ruimte te verwijderen en/of op te halen die veelvouden zijn van rijen, vlakken, kubussen, enz. nuttig zijn.
team we kunnen een enkel element of een rij verwijderen, of zelfs een heel vlak. Dankzij de eigenschappen van globalen gebeurt dit zeer snel - duizenden keren sneller dan verwijdering per element.
De figuur toont een driedimensionale array in een globale ^a en verschillende soorten verwijderingen.
Om stukjes ruimte te selecteren met behulp van bekende indexen, kunt u de opdracht gebruiken .
Een matrixkolom selecteren in de kolomvariabele:
; Зададим трёхмерный разреженный массив 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
Conclusie:
Column(0)=1
Column(2)=1
Het interessante aan de variabele Column is dat we ook een beperkte array hebben, waartoe ook toegang moet worden verkregen , omdat er geen standaardwaarden in worden opgeslagen.
Het selecteren van stukken ruimte kan ook via een klein programma met behulp van de functie . Dit is vooral handig voor ruimtes waarvan de indexen niet gekwantificeerd zijn (cartografie).
Conclusie
De huidige tijd brengt nieuwe ambitieuze opgaven met zich mee. Grafieken kunnen uit miljarden hoekpunten bestaan, kaarten uit miljarden punten, en sommige willen misschien zelfs hun eigen universum op cellulaire automaten laten draaien (, ).
Wanneer het gegevensvolume van schaarse arrays niet langer in het RAM past, maar u ermee moet werken, dan is het de moeite waard om de mogelijkheid te overwegen om soortgelijke projecten op globals en COS te implementeren.
Bedankt voor uw aandacht! We wachten op uw vragen en wensen in de opmerkingen.
Disclaimer: Dit artikel en mijn commentaar daarop zijn mijn mening en hebben geen betrekking op het officiële standpunt van InterSystems Corporation.
Bron: www.habr.com