I tidigare delar (, ) vi pratade om globaler som träd, i den här kommer vi att titta på globaler som glesa arrayer.
är en typ av array där de flesta värdena har samma värde.
I praktiken är glesa arrayer ofta så enorma att det inte är någon idé att ockupera minnet med identiska element. Därför är det vettigt att implementera glesa arrayer på ett sådant sätt att minne inte slösas bort på att lagra identiska värden.
I vissa programmeringsspråk ingår glesa matriser i själva språket, , . Andra programmeringsspråk har speciella bibliotek som låter dig implementera dem. För C++ - etc.
Globaler är goda kandidater för att implementera glesa arrays eftersom:
- De lagrar endast värdena för vissa noder och lagrar inte värdena för odefinierade;
- Gränssnittet för att komma åt en nods värde är extremt likt hur många programmeringsspråk som implementerar åtkomst till ett flerdimensionellt arrayelement.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global är en struktur på ganska låg nivå för att lagra data, därför har den enastående hastighetsegenskaper (från hundratusentals till tiotals miljoner transaktioner per sekund, beroende på hårdvaran, se nedan). )
Eftersom det globala är en beständig struktur, är det vettigt att skapa glesa arrayer på dem när det är känt i förväg att mängden RAM inte kommer att räcka till.
En av egenskaperna hos glesa arrayimplementeringar är att returnera något standardvärde om en åtkomst görs till en odefinierad cell.
Detta kan implementeras med hjälp av funktionen i COS. Det här exemplet betraktar en 3-dimensionell array.
SET a = $GET(^a(x,y,z), defValue)Vilka uppgifter kräver glesa arrayer och hur kan globala hjälpa till?
Adjacency (anslutning) matris
används för att representera grafer:
Ju större grafen är, desto fler nollor kommer det att finnas i matrisen. Om vi till exempel tar en social nätverksgraf och presenterar den i form av en liknande matris, så kommer den nästan helt att bestå av nollor, d.v.s. kommer att vara en gles array.
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
....
I det här exemplet sparar vi globalt ^m anslutningsmatris, såväl som antalet kanter vid varje nod (vem som är vän med vem och antalet vänner).
Om antalet element i grafen inte är mer än 29 miljoner (detta antal tas som produkten av 8 * ), det vill säga ett ännu mer ekonomiskt sätt att lagra sådana matriser är bitsträngar, eftersom deras implementering optimerar stora luckor på ett speciellt sätt.
Manipulationer med bitsträngar utförs av funktionen .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Statsmaskinövergångstabell
Eftersom övergångsgrafen för en finit automat är en vanlig graf, är övergångstabellen för den finita automaten samma närliggande matris som diskuterats ovan.
Cellulära automater
Den mest kända cellulära automaten är , som på grund av sina regler (när en cell har många grannar dör den) är en gles array.
Stephen Wolfram tror att cellulära automater är det . 2002 publicerade han en bok på 1280 XNUMX sidor, A New Kind of Science, där han i stora drag hävdar att framsteg inom cellulära automater inte är isolerade, utan är bestående och har stora konsekvenser för alla vetenskapsområden.
Det har bevisats att vilken algoritm som helst som kan köras på en dator kan implementeras med hjälp av en cellulär automat. Cellulära automater används för att modellera dynamiska miljöer och system, för att lösa algoritmiska problem och för andra ändamål.
Om vi har ett enormt fält och vi behöver registrera alla mellantillstånd för en cellulär automat, så är det vettigt att använda globaler.
Kartografi
Det första jag tänker på när det gäller att använda glesa arrayer är kartläggningsuppgifter.
Som regel är det mycket tomt på kartor. Om kartan representeras som stora pixlar kommer 71 % av jordens pixlar att vara ockuperade av havet. Gles array. Och om du bara använder verk av mänskliga händer, kommer det tomma utrymmet att vara mer än 95%.
Naturligtvis lagrar ingen kartor i form av rastermatriser, en vektorrepresentation används.
Men vad är vektorkartor? Detta är en sorts ram och polylinjer och polygoner som består av punkter.
I huvudsak en databas med punkter och kopplingar mellan dem.
Ett av de mest ambitiösa kartuppdragen är Gaia Telescope-uppdraget för att kartlägga vår galax. Bildligt talat är vår galax, liksom hela universum, en kontinuerlig gles uppsättning: enorma tomhetsutrymmen där det finns sällsynta små punkter - stjärnor. Tomt utrymme är 99,999999…….%. För att lagra kartan över vår galax valdes en global databas - Caché.
Jag vet inte den exakta strukturen av globaler i det här projektet, jag kan anta att det är något som liknar:
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
...
Där b, l, d är och avstånd till solen.
Den flexibla strukturen hos globaler gör att du kan spara alla nödvändiga egenskaper hos stjärnor och planeter, eftersom baserna på globaler är schemalösa.
För att lagra kartan över vårt universum valdes Caché inte bara för sin flexibilitet, utan också för sin förmåga att lagra en dataström mycket snabbt, samtidigt som man skapar indexglobaler för snabba sökningar.
Om vi återvänder till jorden, skapades kartografiska projekt på globaler och en gaffel av OpenStreetMap - .
Nyligen på geospatiala index implementerades . Vi väntar på en artikel från författarna med implementeringsdetaljer.
Implementering av rumsliga index på en global i OpenStreetMap XAPI
Bilder tagna från .
Hela jordklotet är uppdelat i rutor, sedan underrutor och underrutor i underrutor och så vidare. Generellt får vi en hierarkisk struktur för att lagra vilka globaler som skapas.
När som helst kan vi nästan omedelbart begära önskad ruta eller rensa den, och alla delrutor kommer också att returneras eller rensas.
Ett liknande schema på globala kan implementeras på flera sätt.
Alternativ 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ВторойТочки
...Alternativ 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...I båda fallen är det inte svårt att använda COS/M för att begära poäng placerade i en kvadrat på vilken nivå som helst. Det kommer att vara något lättare att rengöra kvadratiska bitar av utrymme på vilken nivå som helst i det första alternativet, men det är sällan nödvändigt.
Ett exempel på en av rutorna på lägre nivå:
Och här är flera globaler från XAPI-projektet: representation av ett index på globaler:
global ^ sätt används för att lagra poäng (vägar, små floder etc.) och polygoner (stängda områden: byggnader, skogar etc.).
Grov klassificering av användningen av glesa arrayer på globaler.
- Vi lagrar koordinaterna för vissa objekt och deras tillstånd (mappning, cellulära automater)
- Vi lagrar glesa matriser.
För fall 2) när vi begär en specifik koordinat där elementet inte är tilldelat ett värde, måste vi få värdet för standard sparse array-elementet.
Bonusar som vi får när vi lagrar flerdimensionella matriser i globaler
Ta snabbt bort och/eller välj utrymmesbitar som är multiplar av rader, plan, kuber etc. För fall där heltalsindex används kan möjligheten att snabbt ta bort och/eller hämta utrymmesbitar som är multiplar av rader, plan, kuber etc. vara användbar.
Team vi kan ta bort antingen ett enda element eller en rad, eller till och med ett helt plan. Tack vare egenskaperna hos globaler sker detta väldigt snabbt - tusentals gånger snabbare än att ta bort element för element.
Figuren visar en tredimensionell array i en global ^a och olika typer av raderingar.
För att välja utrymmesbitar med hjälp av kända index kan du använda kommandot .
Välja en matriskolumn i kolumnvariabeln:
; Зададим трёхмерный разреженный массив 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
Slutsats:
Column(0)=1
Column(2)=1
Det som är intressant med kolumnvariabeln är att vi också har en sparsam array, som också måste nås via , eftersom standardvärden inte lagras i den.
Att välja utrymmesbitar kan också göras genom ett litet program med funktionen . Detta är särskilt praktiskt på utrymmen vars index inte är kvantiserade (kartografi).
Slutsats
Den nuvarande tiden innebär nya ambitiösa uppgifter. Grafer kan bestå av miljarder hörn, kartor av miljarder punkter, och vissa kanske till och med vill köra sitt eget universum på cellulära automater (, ).
När volymen av data från glesa arrayer inte längre kan passa in i RAM, men du måste arbeta med dem, är det värt att överväga möjligheten att implementera liknande projekt på globals och COS.
Tack för din uppmärksamhet! Vi väntar på dina frågor och önskemål i kommentarerna.
Villkor: Den här artikeln och mina kommentarer till den är min åsikt och har inget samband med InterSystems Corporations officiella position.
Källa: will.com