En partes anteriores (, ) falamos dos globais como árbores, neste miraremos os globais como matrices dispersas.
é un tipo de matriz no que a maioría dos valores toman o mesmo valor.
Na práctica, as matrices dispersas adoitan ser tan grandes que non ten sentido ocupar memoria con elementos idénticos. Polo tanto, ten sentido implementar matrices dispersas de tal forma que non se desperdicie memoria en almacenar valores idénticos.
Nalgunhas linguaxes de programación, inclúense matrices escasas na propia linguaxe, , . Outras linguaxes de programación teñen bibliotecas especiais que che permiten implementalas. Para C++ - etc
Os globais son bos candidatos para implementar matrices dispersas porque:
- Almacenan os valores de só certos nodos e non almacenan os valores indefinidos;
- A interface para acceder ao valor dun nodo é moi similar a cantas linguaxes de programación implementan o acceso a un elemento de matriz multidimensional.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global é unha estrutura de baixo nivel para almacenar datos, polo que ten unhas características de velocidade excelentes (de centos de miles a decenas de millóns de transaccións por segundo, dependendo do hardware, ver máis abaixo). )
Dado que o global é unha estrutura persistente, ten sentido crear matrices escasas nelas cando se sabe de antemán que a cantidade de RAM non será suficiente.
Unha das propiedades das implementacións de matrices dispersas é devolver algún valor predeterminado se se accede a unha cela sen definir.
Isto pódese implementar mediante a función en COS. Este exemplo considera unha matriz tridimensional.
SET a = $GET(^a(x,y,z), defValue)Que tarefas requiren matrices dispersas e como poden axudar os globais?
Matriz de adxacencia (conectividade).
usado para representar gráficos:
Obviamente, canto maior sexa a gráfica, máis ceros haberá na matriz. Se, por exemplo, tomamos un gráfico de rede social e o presentamos en forma de matriz similar, entón consistirá case na súa totalidade en ceros, é dicir. será unha matriz escasa.
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
....
Neste exemplo, aforramos globalmente ^m matriz de conectividade, así como o número de bordos en cada nodo (quen é amigo de quen e o número de amigos).
Se o número de elementos do gráfico non supera os 29 millóns (este número tómase como o produto de 8 * ), é dicir, unha forma aínda máis económica de almacenar este tipo de matrices son as cadeas de bits, xa que a súa implementación optimiza grandes lagoas dun xeito especial.
As manipulacións con cadeas de bits son realizadas pola función .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Táboa de transición da máquina de estado
Dado que a gráfica de transición dun autómata finito é unha gráfica ordinaria, entón a táboa de transición do autómata finito é a mesma matriz de adxacencia comentada anteriormente.
Autómatas celulares
O autómata celular máis famoso é , que, debido ás súas regras (cando unha cela ten moitos veciños, morre) é unha matriz escasa.
Stephen Wolfram cre que os autómatas celulares son . En 2002, publicou un libro de 1280 páxinas, A New Kind of Science, no que argumenta en liñas xerais que os avances nos autómatas celulares non están illados, senón que son perdurables e teñen grandes implicacións para todas as áreas da ciencia.
Probouse que calquera algoritmo executable nun ordenador pode implementarse mediante un autómata móbil. Os autómatas móbiles utilízanse para modelar contornas e sistemas dinámicos, para resolver problemas algorítmicos e para outros fins.
Se temos un campo enorme e necesitamos rexistrar todos os estados intermedios dun autómata celular, entón ten sentido usar globais.
Cartografía
O primeiro que se me ocorre cando se trata de usar matrices dispersas é a asignación de tarefas.
Como regra xeral, hai moito espazo baleiro nos mapas. Se o mapa se representa como píxeles grandes, entón o 71% dos píxeles da Terra estarán ocupados polo océano. Matriz escasa. E se aplicas só obras de mans humanas, entón o espazo baleiro será superior ao 95%.
Por suposto, ninguén almacena mapas en forma de matrices ráster; utilízase unha representación vectorial.
Pero que son os mapas vectoriais? Este é unha especie de marco e poliliñas e polígonos formados por puntos.
Esencialmente unha base de datos de puntos e conexións entre eles.
Unha das misións cartográficas máis ambiciosas é a misión do Telescopio Gaia para mapear a nosa galaxia. En sentido figurado, a nosa galaxia, como o universo enteiro, é unha matriz escasa continua: enormes espazos de baleiro nos que hai puntos pequenos raros: estrelas. O espazo baleiro é 99,999999…….%. Para almacenar o mapa da nosa galaxia, escolleuse unha base de datos global: Caché.
Non sei a estrutura exacta dos globais neste proxecto, podo asumir que é algo semellante 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
...
Onde están b, l, d e a distancia ao Sol.
A estrutura flexible dos globais permítelle gardar as características necesarias das estrelas e dos planetas, xa que as bases dos globais non teñen esquemas.
Para almacenar o mapa do noso universo, Caché foi escollido non só pola súa flexibilidade, senón tamén pola súa capacidade para almacenar un fluxo de datos moi rapidamente, ao tempo que creaba índices globais para buscas rápidas.
Se volvemos á Terra, entón creáronse proxectos cartográficos sobre globais e unha bifurcación de OpenStreetMap - .
Encendido recentemente Implementáronse índices xeoespaciais . Estamos á espera dun artigo dos autores con detalles de implementación.
Implementación de índices espaciais nun global en OpenStreetMap XAPI
Imaxes tomadas de .
Todo o globo está dividido en cadrados, despois subcadrados e subcadrados en subcadrados, etc. En xeral, obtemos unha estrutura xerárquica para almacenar cales globais se crean.
En calquera momento, podemos solicitar case ao instante o cadrado desexado ou borralo, e tamén se devolverán ou borrarán todos os subcadrados.
Un esquema similar sobre globais pódese implementar de varias maneiras.
Opción 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ón 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...En ambos os casos, non é difícil utilizar COS/M para solicitar puntos situados nunha praza de calquera nivel. Será algo máis fácil limpar pezas cadradas de espazo a calquera nivel na primeira opción, pero isto raramente é necesario.
Un exemplo dun dos cadrados de nivel inferior:
E aquí están varios globais do proxecto XAPI: representación dun índice sobre globais:
global ^ camiño usado para almacenar puntos (estradas, pequenos ríos, etc.) e polígonos (zonas pechadas: edificios, bosques, etc.).
Clasificación aproximada do uso de matrices dispersas en globais.
- Almacenamos as coordenadas de certos obxectos e os seus estados (mapeamento, autómatas celulares)
- Almacenamos matrices escasas.
Para o caso 2) ao solicitar unha coordenada específica onde ao elemento non se lle asigna un valor, debemos obter o valor do elemento de matriz disperso predeterminado.
Bonos que recibimos ao almacenar matrices multidimensionais en globais
Elimina e/ou selecciona rapidamente pezas de espazo que sexan múltiplos de filas, planos, cubos, etc. Para os casos nos que se usan índices enteiros, pode ser útil a capacidade de eliminar e/ou buscar rapidamente anacos de espazo que sexan múltiplos de filas, planos, cubos, etc.
equipo podemos eliminar un só elemento ou unha fila, ou mesmo un plano enteiro. Grazas ás propiedades dos globais, isto ocorre moi rápido, miles de veces máis rápido que a eliminación elemento por elemento.
A figura mostra unha matriz tridimensional nun global ^a e diferentes tipos de eliminacións.
Para seleccionar pezas de espazo usando índices coñecidos, pode usar o comando .
Seleccionando unha columna matricial na 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ón:
Column(0)=1
Column(2)=1
O interesante da variable Columna é que tamén temos unha matriz escasa, á que tamén hai que acceder a través de , xa que os valores predeterminados non se almacenan nel.
A selección de pezas de espazo tamén se pode facer a través dun pequeno programa usando a función . Isto é especialmente conveniente en espazos cuxos índices non están cuantizados (cartografía).
Conclusión
Os tempos actuais plantexan novas tarefas ambiciosas. Os gráficos poden estar formados por miles de millóns de vértices, os mapas por miles de millóns de puntos e algúns mesmo poden querer executar o seu propio universo en autómatas móbiles (, ).
Cando o volume de datos de matrices dispersas xa non pode caber na RAM, pero cómpre traballar con eles, paga a pena considerar a posibilidade de implementar proxectos similares en globais e COS.
Grazas pola súa atención! Agardamos as vosas preguntas e desexos nos comentarios.
retratação: Este artigo e os meus comentarios ao mesmo son a miña opinión e non teñen relación coa posición oficial de InterSystems Corporation.
Fonte: www.habr.com