In eerdere delen (, ) hebben we het over globals als bomen gehad, in dit deel bekijken we globals als spaarzame arrays.
is een variant van een array waarin de meeste waarden gelijk zijn.
In de praktijk komen we vaak zulke enorme spaarzame arrays tegen dat het geen zin heeft om geheugen te gebruiken voor gelijke elementen. Daarom is het zinvol om spaarzame arrays zodanig te implementeren dat geheugen niet wordt verspild aan het opslaan van gelijke waarden.
In sommige programmeertalen zijn spaarzame arrays geïntegreerd in de taal, , . In andere programmeertalen zijn er speciale bibliotheken die het mogelijk maken om ze te implementeren. Voor C++ is dat - enz.
Globals zijn goede kandidaten voor de implementatie van spaarzame arrays omdat:
- Ze waarden alleen van bepaalde knooppunten opslaan en geen waarden van ongedefinieerde;
- De interface voor toegang tot de waarde van een knooppunt lijkt enorm op hoe toegang tot elementen van een meerdimensionale array in veel programmeertalen is geïmplementeerd.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global is een vrij lage structuur voor gegevensopslag, waardoor ze uitstekende snelheidseigenschappen hebben (van enkele honderden duizenden tot tientallen miljoenen transacties per seconde, afhankelijk van de hardware, zie )
Aangezien een global een persistente structuur is, heeft het zin om spaarzame arrays daarop te maken wanneer van tevoren bekend is dat het volume van het RAM niet voldoende zal zijn.
Een van de eigenschappen van de implementatie van spaarzame arrays is dat er een standaardwaarde wordt geretourneerd als er toegang wordt verkregen tot een ongedefinieerde cel.
Dit kan worden gerealiseerd met behulp van de functie in COS. In dit voorbeeld wordt een 3-dimensionale array besproken.
SET a = $GET(^a(x,y,z), defValue)In welke taken zijn spaarzame arrays nodig en hoe kunnen globals helpen?
Adjacency matrix (connectiviteit)
worden gebruikt voor de representatie van grafen:
Het is duidelijk dat hoe groter de graaf, hoe meer nullen er in de matrix zullen zijn. Als we bijvoorbeeld een sociale netwerkgraaf nemen en deze in de vorm van een dergelijke matrix weergeven, zal het bijna helemaal uit nullen bestaan, dat wil zeggen, het zal een spaarzame 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 slaan we op in de global ^m de connectiviteitsmatrix, evenals het aantal verbindingen per knooppunt (wie met wie bevriend is en het aantal vrienden).
Als het aantal elementen in de grafiek niet meer dan 29 miljoen is (dit getal wordt genomen als het product van 8 * ), dan is er een nog economischer manier om zulke matrices op te slaan — bitstrings, omdat in hun implementatie grote gaten speciaal worden geoptimaliseerd.
Bewerkingen met bitstrings worden uitgevoerd met de functie .
; stel een bit in
SET $BIT(rowID, positionID) = 1
; verkrijg een bit
Write $BIT(rowID, positionID)
De overgangstabel van de eindige automaat
Aangezien de overgangsgrafiek van de eindige automaat een gewone grafiek is, is de overgangstabel van de eindige automaat dezelfde nabijheidsmatrix waar eerder over werd gesproken.
Celautomaten
De bekendste celautomaat is , dat vanwege zijn regels (wanneer een cel veel buren heeft — sterft deze) een spaarzaam array voorstelt.
Stephen Wolfram beschouwt celautomaten als een . In 2002 publiceerde hij een 1280 pagina's tellend boek 'A New Kind of Science', waarin hij uitgebreid argumenteert dat de prestaties op het gebied van celautomaten niet geïsoleerd zijn, maar zeer stabiel en van groot belang voor alle wetenschappen.
Het is bewezen dat elk algoritme dat op een computer uitvoerbaar is, kan worden gerealiseerd via een celautomaat. Celautomaten worden gebruikt voor het modelleren van dynamische omgevingen en systemen, voor het oplossen van algorithmische problemen en voor andere doeleinden.
Als we een enorm speelveld hebben en we moeten alle tussenliggende toestanden van de celautomaat registreren, is het heel redelijk om globalen te gebruiken.
Cartografie
Het eerste waar ik aan denk als het gaat om het gebruik van spaarzame arrays — zijn cartografische taken.
Over het algemeen is er veel lege ruimte op kaarten. Als we de kaart zouden voorstellen in de vorm van grote pixels, zou 71% van de pixels van de aarde worden bezet door de oceaan. Een spaarzaam array. En als we alleen de producten van menselijke handen in kaart zouden brengen, zou er meer dan 95% lege ruimte zijn.
Natuurlijk bewaart niemand kaarten als rasterarrays, een vectorrepresentatie wordt gebruikt.
Maar wat zijn vector kaarten? Dit is een soort kader, bestaande uit punten, poly-lijnen en polygonen.
Eigenlijk is de database van punten en de verbindingen daartussen.
Een van de meest ambitieuze kaartprojecten is de missie om onze melkweg in kaart te brengen met de Gaia-telescoop. Figuurlijk gesproken is onze melkweg, net als het hele universum, een allesomvattende spaarzame structuur: enorme lege ruimtes, waarin enkele kleine punten — sterren — te vinden zijn. De lege ruimte bedraagt 99,999999…….%. Voor het opslaan van de kaart van onze melkweg is gekozen voor een database op globals — Caché.
Ik weet de exacte structuur van de globals in dit project niet, ik kan me voorstellen dat het iets als volgt is:
Set ^galaxy(b, l, d) = 1; Het nummer van de ster in de catalogus, indien beschikbaar
Set ^galaxy(b, l, d, "name") = "Zon"
Set ^galaxy(b, l, d, "type") = "normaal" ; soorten blackhole, quasar, red_dwarf enz.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercurius"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Waarbij b, l, d — de en afstand tot de Zon.
De flexibele structuur van globals maakt het mogelijk om alle noodzakelijke kenmerken van sterren en planeten op te slaan, aangezien databases op globals schema-loos zijn.
Caché werd niet alleen gekozen voor het opslaan van de kaart van ons universum vanwege de flexibiliteit, maar ook vanwege de mogelijkheid om gegevensstromen zeer snel op te slaan, terwijl tevens indexglobals worden aangemaakt voor een snelle zoekactie.
Als we echter naar de aarde terugkeren, zijn er op globals cartografische projecten gecreëerd en de fork van OpenStreetMap — .
Onlangs zijn er op de geospatiale indexen . We wachten op details van de auteurs van het artikel over de implementatie.
Implementatie van ruimtelijke indexen op globals in OpenStreetMap XAPI
De afbeeldingen zijn genomen van .
De hele aarde wordt opgedeeld in vierkantjes, die vervolgens in kleinere vierkantjes worden verdeeld, en de kleinere vierkantjes weer in nog kleinere vierkantjes, enzovoorts. Uiteindelijk krijgen we een hiërarchische structuur waarvoor de globals zijn gemaakt.
Op elk moment kunnen we vrijwel onmiddellijk het benodigde vierkant opvragen of het verwijderen, terwijl ook alle kleinere vierkantjes zullen worden teruggegeven of verwijderd.
Een dergelijk schema op globals kan op verschillende manieren worden geïmplementeerd.
Option 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idEerstePunt
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idTweedePunt
...Option 2:
Set ^m('abacdabcdabacdabcda', 1) = idEerstePunt
Set ^m('abacdabcdabacdabcda', 2) = idTweedePunt
...In beide gevallen is het eenvoudig om op COS/M punten binnen een vierkant van elk niveau aan te vragen. Het zal iets gemakkelijker zijn om vierkante delen van ruimte van elk niveau in de eerste optie te wissen, maar dat is zelden nodig.
Voorbeeld van een van de vierkanten van het lagere niveau:
En hier zijn een paar globalen uit het XAPI-project: weergave van de index op de globalen:
Global ^way wordt gebruikt om punten op te slaan (wegen, kleine rivieren, enz.) en polygonen (afgesloten gebieden: gebouwen, bossen, enz.).
Ruwe classificatie van het gebruik van spaarzame matrices op de globalen.
- We slaan de coördinaten van bepaalde objecten en hun staten op (mapping, celautomata)
- We slaan spaarzame matrices op.
Voor geval 2) bij het opvragen van een bepaalde coördinaat, waar het element geen waarde heeft gekregen, moeten we de standaardwaarde van het spaarzame matrixelement krijgen.
De voordelen die we krijgen bij het opslaan van multidimensionale matrices in globalen
Snelle verwijdering en/of selectie van stukken ruimte, veelvouden van rijen, vlakken, kubussen, enz. Voor gevallen waarin gehele getallen als indexen worden gebruikt, kan een snelle verwijdering en/of selectie van stukken ruimte, veelvouden van rijen, vlakken, kubussen, enz., nuttig zijn.
Met het commando We kunnen zowel een afzonderlijk element als een rij en zelfs een heel vlak verwijderen. Dankzij de eigenschappen van globalen gebeurt dit zeer snel — duizenden keren sneller dan elementgewijze verwijdering.
De afbeelding toont een driedimensionale matrix in de globale ^a en verschillende soorten verwijderingen.
Om stukken ruimte op basis van bekende indexen te selecteren, kan de opdracht gebruikt worden .
Selectie van de kolom van de matrix in variabele Column:
; Laten we een driedimensionale spaarzame matrix 3x3x3 instellen
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)
; Laten we de variabele Column afdrukken
Zwrite Column
Uitvoer:
Column(0)=1
Column(2)=1
Wat interessant is, is dat we in de variabele Column ook een spaarzame matrix hebben gekregen, waar we ook via toegang moeten krijgen , aangezien de standaardwaarden daarin niet worden opgeslagen.
De selectie van stukken ruimte kan ook worden gedaan via een klein programma met de functie . Dit is vooral handig in ruimtes waarvan de indexen niet gekwantificeerd zijn (cartografie).
Conclusie
De huidige tijden stellen nieuwe ambitieuze doelen. Grafieken kunnen bestaan uit miljarden knopen, kaarten uit miljarden punten, en iemand kan zelfs de wens hebben om zijn eigen universum op cellulair niveau te lanceren., ).
Wanneer de hoeveelheid data van spaarzame arrays niet meer in het RAM-geheugen past en er toch mee gewerkt moet worden, is het de moeite waard om de mogelijkheid te overwegen om dergelijke projecten op globals en COS te implementeren.
Bedankt voor uw aandacht! We kijken uit naar uw vragen en opmerkingen in de reacties.
Disclaimer: Dit artikel en mijn opmerkingen hierover zijn mijn mening en hebben geen relatie met de officiële positie van de onderneming InterSystems.
Bron: habr.com
