Nas partes anteriores (, ) falamos sobre globais como árvores, neste artigo veremos globais como matrizes esparsas.
é um tipo de array em que a maioria dos valores assume o mesmo valor.
Na prática, arrays esparsos costumam ser tão grandes que não faz sentido ocupar memória com elementos idênticos. Portanto, faz sentido implementar arrays esparsos de tal forma que a memória não seja desperdiçada no armazenamento de valores idênticos.
Em algumas linguagens de programação, arrays esparsos são incluídos na própria linguagem, , . Outras linguagens de programação possuem bibliotecas especiais que permitem implementá-las. Para C++ - etc
Os globais são bons candidatos para implementar matrizes esparsas porque:
- Eles armazenam os valores de apenas alguns nós e não armazenam os valores dos indefinidos;
- A interface para acessar o valor de um nó é extremamente semelhante a quantas linguagens de programação implementam o acesso a um elemento de array multidimensional.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global é uma estrutura de armazenamento de dados de nível bastante baixo, portanto possui excelentes características de velocidade (de centenas de milhares a dezenas de milhões de transações por segundo, dependendo do hardware, veja abaixo). )
Como o global é uma estrutura persistente, faz sentido criar arrays esparsos neles quando se sabe de antemão que a quantidade de RAM não será suficiente.
Uma das propriedades das implementações de arrays esparsos é retornar algum valor padrão se um acesso for feito a uma célula indefinida.
Isso pode ser implementado usando a função no COS. Este exemplo considera uma matriz tridimensional.
SET a = $GET(^a(x,y,z), defValue)Quais tarefas exigem matrizes esparsas e como os globais podem ajudar?
Matriz de adjacência (conectividade)
usado para representar gráficos:
Obviamente, quanto maior o gráfico, mais zeros haverá na matriz. Se, por exemplo, pegarmos um gráfico de uma rede social e apresentá-lo na forma de uma matriz semelhante, então ele consistirá quase inteiramente de zeros, ou seja, será uma matriz esparsa.
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, economizamos globalmente ^m matriz de conectividade, bem como o número de arestas em cada nó (quem é amigo de quem e o número de amigos).
Se o número de elementos no gráfico não for superior a 29 milhões (este número é considerado o produto de 8 * ), ou seja, uma forma ainda mais econômica de armazenar tais matrizes são as strings de bits, pois sua implementação otimiza grandes intervalos de maneira especial.
Manipulações com sequências de bits são realizadas pela função .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabela de transição de máquina de estado
Como o grafo de transição de um autômato finito é um grafo comum, então a tabela de transição do autômato finito é a mesma matriz de adjacência discutida acima.
Autômatos celulares
O autômato celular mais famoso é , que, devido às suas regras (quando uma célula tem muitos vizinhos, ela morre) é um array esparso.
Stephen Wolfram acredita que os autômatos celulares são . Em 2002, publicou um livro de 1280 páginas, A New Kind of Science, no qual defende amplamente que os avanços nos autómatos celulares não são isolados, mas são duradouros e têm grandes implicações para todas as áreas da ciência.
Está comprovado que qualquer algoritmo executável em um computador pode ser implementado por meio de um autômato celular. Autômatos celulares são usados para modelar ambientes e sistemas dinâmicos, para resolver problemas algorítmicos e para outros fins.
Se tivermos um campo enorme e precisarmos registrar todos os estados intermediários de um autômato celular, então faz sentido usar globais.
Cartografia
A primeira coisa que me vem à mente quando se trata de usar arrays esparsos é mapear tarefas.
Via de regra, há muito espaço vazio nos mapas. Se o mapa for representado como pixels grandes, 71% dos pixels da Terra serão ocupados pelo oceano. Matriz esparsa. E se você aplicar apenas obras de mãos humanas, o espaço vazio será superior a 95%.
É claro que ninguém armazena mapas na forma de matrizes raster; é usada uma representação vetorial.
Mas o que são mapas vetoriais? Este é um tipo de quadro e polilinhas e polígonos que consistem em pontos.
Essencialmente, um banco de dados de pontos e conexões entre eles.
Uma das missões de mapeamento mais ambiciosas é a missão do Telescópio Gaia para mapear a nossa galáxia. Falando figurativamente, nossa galáxia, como todo o universo, é uma matriz contínua e esparsa: enormes espaços de vazio nos quais existem raros pequenos pontos - estrelas. O espaço vazio é 99,999999…….%. Para armazenar o mapa da nossa galáxia, foi escolhida uma base de dados global - Caché.
Não sei a estrutura exata dos globais neste projeto, posso assumir que é algo semelhante 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 b, l, d estão e distância ao Sol.
A estrutura flexível dos globais permite salvar quaisquer características necessárias de estrelas e planetas, uma vez que as bases dos globais não têm esquema.
Para armazenar o mapa do nosso universo, o Caché foi escolhido não só pela sua flexibilidade, mas também pela sua capacidade de armazenar um fluxo de dados muito rapidamente, ao mesmo tempo que cria índices globais para pesquisas rápidas.
Se voltarmos à Terra, então foram criados projetos cartográficos em globais e um fork do OpenStreetMap - .
Recentemente em índices geoespaciais foram implementados . Estamos aguardando um artigo dos autores com detalhes de implementação.
Implementação de índices espaciais em um global no OpenStreetMap XAPI
Fotos tiradas de .
O globo inteiro é dividido em quadrados, depois em subquadrados, e os subquadrados em subquadrados e assim por diante. Em geral, obtemos uma estrutura hierárquica para armazenar quais globais são criados.
A qualquer momento, podemos solicitar quase instantaneamente o quadrado desejado ou limpá-lo, e todos os subquadrados também serão devolvidos ou apagados.
Um esquema semelhante em globais pode ser implementado de várias maneiras.
1 opção:
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ВторойТочки
...2 opção:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Em ambos os casos, não é difícil utilizar o COS/M para solicitar pontos localizados em um quadrado de qualquer nível. Será um pouco mais fácil limpar espaços quadrados em qualquer nível na primeira opção, mas isso raramente é necessário.
Um exemplo de um dos quadrados de nível inferior:
E aqui estão vários globais do projeto XAPI: representação de um índice em globais:
global ^ caminho usado para armazenar pontos (estradas, pequenos rios, etc.) e polígonos (áreas fechadas: edifícios, florestas, etc.).
Classificação aproximada do uso de matrizes esparsas em globais.
- Armazenamos as coordenadas de certos objetos e seus estados (mapeamento, autômatos celulares)
- Armazenamos matrizes esparsas.
Para o caso 2) ao solicitar uma coordenada específica onde o elemento não recebe um valor, devemos obter o valor do elemento da matriz esparsa padrão.
Bônus que recebemos ao armazenar matrizes multidimensionais em globais
Remova e/ou selecione rapidamente pedaços de espaço que sejam múltiplos de linhas, planos, cubos, etc. Para casos em que índices inteiros são usados, a capacidade de remover e/ou buscar rapidamente pedaços de espaço que são múltiplos de linhas, planos, cubos, etc. pode ser útil.
equipe podemos excluir um único elemento ou uma linha, ou até mesmo um plano inteiro. Graças às propriedades dos globais, isso acontece muito rapidamente - milhares de vezes mais rápido do que a remoção elemento por elemento.
A figura mostra uma matriz tridimensional em um global ^a e diferentes tipos de exclusões.
Para selecionar partes do espaço usando índices conhecidos, você pode usar o comando .
Selecionando uma coluna de matriz na variável Coluna:
; Зададим трёхмерный разреженный массив 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
Conclusão:
Column(0)=1
Column(2)=1
O interessante da variável Column é que também temos um array esparso, que também deve ser acessado através , uma vez que os valores padrão não são armazenados nele.
A seleção de pedaços de espaço também pode ser feita através de um pequeno programa usando a função . Isto é especialmente conveniente em espaços cujos índices não são quantizados (cartografia).
Conclusão
Os tempos atuais colocam novas tarefas ambiciosas. Os gráficos podem ser compostos por bilhões de vértices, os mapas podem ser compostos por bilhões de pontos, e alguns podem até querer executar seu próprio universo em autômatos celulares (, ).
Quando o volume de dados de arrays esparsos não cabe mais na RAM, mas você precisa trabalhar com eles, vale a pena considerar a possibilidade de implementar projetos semelhantes em globais e COS.
Obrigado pela sua atenção! Aguardamos suas dúvidas e desejos nos comentários.
Aviso Legal: Este artigo e meus comentários são minha opinião e não têm relação com a posição oficial da InterSystems Corporation.
Fonte: habr.com