Nas partes anteriores (, ) nós falamos sobre globais como árvores, nesta vamos considerar globais como arrays esparsos.
é um tipo de array onde a maioria dos valores assume o mesmo valor.
Na prática, muitas vezes encontramos arrays esparsos tão enormes que não faz sentido ocupar memória com elementos iguais. Portanto, é razoável implementar arrays esparsos de forma que a memória não seja consumida para armazenar valores iguais.
Em algumas linguagens de programação, arrays esparsos fazem parte da própria linguagem, , . Em outras linguagens de programação, existem bibliotecas especiais que permitem implementá-los. Para C++ — e outras.
Globais são bons candidatos para a implementação de arrays esparsos, porque:
- Armazenam valores apenas de certos nós e não armazenam valores indefinidos;
- A interface de acesso ao valor de um nó é extremamente semelhante a como o acesso a elementos de um array multidimensional é implementado em muitas linguagens de programação.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global é uma estrutura de nível relativamente baixo para armazenamento de dados, portanto, possui características de velocidade excepcionais (de centenas de milhares a dezenas de milhões de transações por segundo, dependendo do hardware, veja) )
Como global é uma estrutura persistente, então faz sentido implementar arrays esparsos sobre eles quando já sabemos que o volume de memória RAM será insuficiente.
Uma das propriedades das implementações de arrays esparsos é devolver um certo valor padrão se a referência for feita a uma célula indefinida.
Isso pode ser realizado utilizando a função no COS. Neste exemplo, um array tridimensional é considerado.
SET a = $GET(^a(x,y,z), defValue)Em quais problemas são necessários arrays esparsos e como os globais podem ajudar?
Matriz de adjacência (conexão)
são utilizadas para representar gráficos:
É evidente que quanto maior o gráfico, mais zeros haverá na matriz. Se, por exemplo, pegarmos o gráfico de uma rede social e o representarmos como uma matriz, ela quase toda será composta de zeros, ou seja, será um array esparso.
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, estamos salvando no global ^m a 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 exceder 29 milhões (este número é obtido como o produto de 8 * ), existe um método ainda mais econômico para armazenar tais matrizes — bitstrings, pois na sua implementação grandes lacunas são otimizadas de maneira especial.
As operações com bitstrings são realizadas pela função .
; definir um bit
SET $BIT(rowID, positionID) = 1
; obter um bit
Write $BIT(rowID, positionID)
Tabela de transições de um autômato finito
Como o gráfico de transições de um autômato finito é um gráfico comum, a tabela de transições de um autômato finito é a mesma matriz de adjacência mencionada acima.
Autômatos celulares
O autômato celular mais famoso é , que devido às suas regras (quando uma célula tem muitos vizinhos — ela morre) representa uma matriz esparsa.
Stephen Wolfram acredita que os autômatos celulares são uma . Em 2002, ele publica um livro de 1280 páginas intitulado 'A Nova Ciência', onde argumenta amplamente que as descobertas na área dos autômatos celulares não são isoladas, mas bastante robustas e têm grande significado para todas as áreas da ciência.
Foi provado que qualquer algoritmo executável em um computador pode ser implementado usando autômatos celulares. Autômatos celulares são usados para modelar ambientes dinâmicos e sistemas, para resolver problemas algorítmicos e outros propósitos.
Se temos um grande campo e precisamos registrar todos os estados intermediários do autômato celular, é razoável usar globais.
Cartografia
A primeira coisa que me vem à mente quando se fala sobre o uso de matrizes esparsas são os problemas cartográficos.
Normalmente, nos mapas há muito espaço vazio. Se o mapa for representado como grandes pixels, 71% dos pixels da Terra seriam ocupados pelo oceano. Matriz esparsa. E se considerarmos apenas as obras das mãos humanas, o espaço vazio seria mais de 95%.
Claro, ninguém armazena mapas como matrizes raster; utiliza-se a representação vetorial.
Mas o que são realmente os mapas vetoriais? É uma espécie de estrutura composta de pontos, polilinhas e polígonos.
Na verdade, é uma base de dados de pontos e suas conexões.
Uma das tarefas mais ambiciosas de cartografia é a missão de mapear nossa galáxia com o telescópio Gaia. Figurativamente, nossa galáxia, assim como todo o universo, é uma matriz dispersa: vastos espaços de vazios, onde existem pequenas pontuações raras — estrelas. O espaço vazio representa 99,999999…….%. Para armazenar o mapa de nossa galáxia, foi escolhida uma base de dados em globais — Caché.
Não conheço a estrutura exata dos globais neste projeto, posso supor que seja algo parecido com:
Set ^galaxy(b, l, d) = 1; Número da estrela no catálogo, se existir
Set ^galaxy(b, l, d, "name") = "Sol"
Set ^galaxy(b, l, d, "type") = "normal"; opções blackhole, quasar, anã vermelha, etc.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercúrio"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Onde b, l, d são e distância até o Sol.
A estrutura flexível dos globais permite armazenar quaisquer características necessárias de estrelas e planetas, já que as bases em globais não têm esquema (scheme-less).
A escolha do Caché para armazenar o mapa de nosso universo não se deve apenas à flexibilidade, mas também à capacidade de rapidamente salvar fluxos de dados, ao mesmo tempo em que cria globais indexados para uma busca rápida.
Se voltarmos à Terra, alguns projetos de mapeamento foram criados em globais e o fork do OpenStreetMap — .
Recentemente, no foram implementados índices geoespaciais . Ansiosos pelos detalhes da implementação por parte dos autores do artigo.
A implementação de índices espaciais em globais no OpenStreetMap XAPI
As imagens foram retiradas de .
Todo o globo terrestre é dividido em quadrados, depois em subquadrados, e os subquadrados em quadradinhos, e assim por diante. No geral, obtemos uma estrutura hierárquica para o armazenamento, para a qual foram criados globais.
A qualquer momento, podemos praticamente solicitar instantaneamente o quadrado necessário ou limpá-lo, e todos os subquadrados também serão retornados ou limpos.
Um esquema semelhante em globais pode ser implementado de várias maneiras.
Opção 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idPrimeiroPonto
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idSegundoPonto
...Opção 2:
Set ^m('abacdabcdabacdabcda', 1) = idPrimeiroPonto
Set ^m('abacdabcdabacdabcda', 2) = idSegundoPonto
...Em ambos os casos, não é difícil solicitar pontos localizados em um quadrado de qualquer nível no COS/M. Será um pouco mais fácil limpar pedaços quadrados de espaço de qualquer nível na primeira opção, mas isso raramente é necessário.
Exemplo de um dos quadrados do nível inferior:
Aqui estão alguns globais do projeto XAPI: representação do índice em globais:
Global ^way usado para armazenar pontos (estradas, rios pequenos, etc.) e polígonos (áreas fechadas: edifícios, florestas, etc.).
Classificação bruta do uso de matrizes esparsas em globais.
- Armazenamos as coordenadas de certos objetos e seus estados (mapeamento, autômatos celulares)
- Armazenamos matrizes esparsas.
No caso 2) ao solicitar uma coordenada específica, onde o elemento não tem valor atribuído, devemos obter o valor do elemento da matriz esparsa por padrão.
Os bônus que recebemos ao armazenar matrizes multidimensionais em globais
Remoção rápida e/ou amostragens de pedaços de espaço que são múltiplos de linhas, planos, cubos, etc. Para casos em que índices inteiros são utilizados, pode ser útil a capacidade de remoção rápida e/ou amostragens de pedaços de espaço que são múltiplos de linhas, planos, cubos, etc.
Comando podemos remover tanto um elemento individual, quanto uma linha, e 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 remoções.
Para amostrar pedaços de espaço por índices conhecidos, pode-se usar o comando .
Amostragem de uma coluna da matriz na variável Column:
; Vamos definir uma matriz esparsa tridimensional 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)
; Vamos exibir a variável Column
Zwrite Column
Conclusão:
Column(0)=1
Column(2)=1
O que é interessante é que a variável Column também resultou em uma matriz esparsa, a qual deve ser acessada também através de , uma vez que os valores padrão não são armazenados nela.
A amostragem de pedaços de espaço também pode ser feita através de um pequeno programa utilizando a função . Isso é especialmente conveniente em espaços cujos índices não são quantizados (cartografia).
Conclusão
Os tempos atuais impõem novas e ambiciosas tarefas. Os grafos podem conter bilhões de vértices, os mapas bilhões de pontos, e alguém pode até querer lançar seu próprio universo em autômatos celulares (, ).
Quando o volume de dados de matrizes esparsas não pode mais ser armazenado na memória RAM e é necessário trabalhar com eles, deve-se considerar a implementação de tais projetos em globais e COS.
Obrigado pela atenção! Aguardamos suas perguntas e sugestões nos comentários.
Aviso Legal: este artigo e meus comentários a ele são minha opinião e não têm relação com a posição oficial da corporação InterSystems.
Fonte: habr.com
