En parts anteriors (, ) vam parlar dels globals com a arbres, en aquest veurem els globals com a matrius dispersos.
és un tipus de matriu en què la majoria dels valors prenen el mateix valor.
A la pràctica, les matrius disperses solen ser tan grans que no té sentit ocupar la memòria amb elements idèntics. Per tant, té sentit implementar matrius escasses de manera que no es malgasti la memòria per emmagatzemar valors idèntics.
En alguns llenguatges de programació, les matrius escasses s'inclouen en el propi llenguatge, , . Altres llenguatges de programació tenen biblioteques especials que permeten implementar-los. Per a C++ - etcètera
Els globals són bons candidats per implementar matrius escasses perquè:
- Emmagatzemen els valors de determinats nodes només i no emmagatzemen els valors dels no definits;
- La interfície per accedir al valor d'un node és molt similar a quants llenguatges de programació implementen l'accés a un element de matriu multidimensional.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global és una estructura de nivell bastant baix per emmagatzemar dades, per tant té unes característiques de velocitat excepcionals (des de centenars de milers fins a desenes de milions de transaccions per segon, depenent del maquinari, vegeu més avall). )
Com que el global és una estructura persistent, té sentit crear-hi matrius escasses quan se sap per endavant que la quantitat de memòria RAM no serà suficient.
Una de les propietats de les implementacions de matriu escassa és retornar algun valor predeterminat si es fa un accés a una cel·la no definida.
Això es pot implementar mitjançant la funció en COS. Aquest exemple considera una matriu tridimensional.
SET a = $GET(^a(x,y,z), defValue)Quines tasques requereixen matrius disperses i com poden ajudar els globals?
Matriu d'adjacència (connectivitat).
S'utilitza per representar gràfics:
Òbviament, com més gran sigui el gràfic, més zeros hi haurà a la matriu. Si, per exemple, agafem un gràfic de xarxa social i el presentem en forma de matriu semblant, aleshores constarà gairebé completament de zeros, és a dir. serà una matriu escassa.
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
....
En aquest exemple, estalviem globalment ^m matriu de connectivitat, així com el nombre d'arestes a cada node (qui és amic amb qui i el nombre d'amics).
Si el nombre d'elements del gràfic no supera els 29 milions (aquest nombre es pren com el producte de 8 * ), és a dir, una manera encara més econòmica d'emmagatzemar aquestes matrius són les cadenes de bits, ja que la seva implementació optimitza grans buits d'una manera especial.
Les manipulacions amb cadenes de bits les realitza la funció .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Taula de transició de la màquina d'estat
Com que el gràfic de transició d'un autòmat finit és un gràfic ordinari, aleshores la taula de transició de l'autòmat finit és la mateixa matriu d'adjacència discutida anteriorment.
Autòmats cel·lulars
L'autòmat cel·lular més famós és , que, a causa de les seves regles (quan una cel·la té molts veïns, mor) és una matriu escassa.
Stephen Wolfram creu que els autòmats cel·lulars ho són . L'any 2002, va publicar un llibre de 1280 pàgines, A New Kind of Science, en què argumenta a grans trets que els avenços en els autòmats cel·lulars no estan aïllats, sinó que són perdurables i tenen grans implicacions per a totes les àrees de la ciència.
S'ha comprovat que qualsevol algorisme executable en un ordinador es pot implementar mitjançant un autòmat cel·lular. Els autòmats cel·lulars s'utilitzen per modelar entorns i sistemes dinàmics, per resoldre problemes algorísmics i per a altres finalitats.
Si tenim un camp enorme i necessitem registrar tots els estats intermedis d'un autòmat cel·lular, llavors té sentit utilitzar globals.
Cartografia
El primer que em ve al cap quan es tracta d'utilitzar matrius disperses és mapejar tasques.
Per regla general, hi ha molt espai buit als mapes. Si el mapa es representa com a píxels grans, el 71% dels píxels de la Terra estaran ocupats per l'oceà. Matriu escassa. I si apliqueu només obres de mans humanes, l'espai buit serà superior al 95%.
Per descomptat, ningú emmagatzema mapes en forma de matrius ràster s'utilitza una representació vectorial.
Però què són els mapes vectorials? Es tracta d'una mena de marc i polilínies i polígons formats per punts.
Bàsicament una base de dades de punts i connexions entre ells.
Una de les missions de cartografia més ambicioses és la missió del Telescopi Gaia per cartografiar la nostra galàxia. En sentit figurat, la nostra galàxia, com l'univers sencer, és una matriu dispersa contínua: enormes espais de buit en els quals hi ha petits punts rars: estrelles. L'espai buit és 99,999999…….%. Per emmagatzemar el mapa de la nostra galàxia, es va triar una base de dades global: Caché.
No conec l'estructura exacta dels globals en aquest projecte, puc suposar que és una cosa semblant a:
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
...
On són b, l, d i la distància al Sol.
L'estructura flexible dels globals us permet desar qualsevol característiques necessàries d'estrelles i planetes, ja que les bases dels globals no tenen esquema.
Per emmagatzemar el mapa del nostre univers, Caché va ser escollit no només per la seva flexibilitat, sinó també per la seva capacitat d'emmagatzemar un flux de dades molt ràpidament, alhora que creava globals d'índexs per a cerques ràpides.
Si tornem a la Terra, es van crear projectes cartogràfics sobre globals i una bifurcació d'OpenStreetMap - .
Fa poc S'han implementat índexs geoespacials . Estem esperant un article dels autors amb els detalls de la implementació.
Implementació d'índexs espacials en un global a OpenStreetMap XAPI
Imatges extretes de .
El globus sencer es divideix en quadrats, després subquadrats, i subquadrats en subquadrats, etc. En general, obtenim una estructura jeràrquica per emmagatzemar quins globals es creen.
En qualsevol moment, podem sol·licitar gairebé a l'instant el quadrat desitjat o esborrar-lo, i també es retornaran o esborraran tots els subquadrats.
Un esquema similar sobre globals es pot implementar de diverses maneres.
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ВторойТочки
...En ambdós casos, no és difícil utilitzar COS/M per demanar punts situats en una plaça de qualsevol nivell. Serà una mica més fàcil netejar trossos quadrats d'espai a qualsevol nivell a la primera opció, però això rarament és necessari.
Un exemple d'un dels quadrats de nivell inferior:
I aquí hi ha diversos globals del projecte XAPI: representació d'un índex sobre globals:
global ^manera utilitzat per emmagatzemar punts (carreteres, petits rius, etc.) i polígons (zones tancades: edificis, boscos, etc.).
Classificació aproximada de l'ús de matrius dispersos en globals.
- Emmagatzemem les coordenades de determinats objectes i els seus estats (cartografia, autòmats cel·lulars)
- Emmagatzemem matrius escasses.
Per al cas 2) quan sol·licitem una coordenada específica on l'element no té assignat un valor, hem d'obtenir el valor de l'element de matriu dispers predeterminat.
Bonificacions que rebem en emmagatzemar matrius multidimensionals en globals
Elimineu i/o seleccioneu ràpidament peces d'espai que siguin múltiples de files, plans, cubs, etc. Per als casos en què s'utilitzen índexs enters, pot ser útil la possibilitat d'eliminar i/o recuperar ràpidament trossos d'espai que són múltiples de files, plans, cubs, etc.
equip podem esborrar un únic element o una fila, o fins i tot un pla sencer. Gràcies a les propietats dels globals, això passa molt ràpidament, milers de vegades més ràpid que l'eliminació element per element.
La figura mostra una matriu tridimensional en un global ^a i diferents tipus d'eliminacions.
Per seleccionar trossos d'espai mitjançant índexs coneguts, podeu utilitzar l'ordre .
Seleccionant una columna de matriu a la variable Columna:
; Зададим трёхмерный разреженный массив 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
Conclusió:
Column(0)=1
Column(2)=1
El que és interessant de la variable Column és que també tenim una matriu escassa, a la qual també s'ha d'accedir mitjançant , ja que els valors predeterminats no s'emmagatzemen en ell.
La selecció de peces d'espai també es pot fer mitjançant un petit programa mitjançant la funció . Això és especialment convenient en espais els índexs dels quals no estan quantificats (cartografia).
Conclusió
Els temps actuals plantegen noves tasques ambicioses. Els gràfics poden estar formats per milers de milions de vèrtexs, mapes per milers de milions de punts i alguns fins i tot poden voler executar el seu propi univers amb autòmats cel·lulars (, ).
Quan el volum de dades de les matrius disperses ja no pot cabre a la memòria RAM, però cal treballar-hi, val la pena considerar la possibilitat d'implementar projectes similars en globals i COS.
Gràcies per la vostra atenció! Esperem les vostres preguntes i desitjos als comentaris.
renúncia: Aquest article i els meus comentaris al respecte són la meva opinió i no representen la posició oficial d'InterSystems Corporation.
Font: www.habr.com