O que é a estrutura de dados mais eficiente para armazenar séries de tempo de mudança de matriz parcialmente?

votos
4

Meu problema é que eu tenho uma matriz de objetos de tamanho N. depois de cada tempo (t + 1), alguns dos valores do array pode ou não mudar. Então, digamos que t + 1 índice de 15 mudanças, mas tudo o resto permanece o mesmo.

Qual é a maneira mais eficiente para armazenar algo como isto (em memória) para além de apenas ter uma matriz de matrizes de curso? Eu quero ser capaz de obter todos os valores da matriz para qualquer momento, dizer getValues ​​(longo tempo) da forma mais eficiente possível.

Digamos, por 4 matrizes

tempo de 1 null null null xyz

tempo 2 nula xyz abc nula

(Note que apenas abc mudou aqui) mas nós ainda manter os valores do último índice de tempos 1.

Publicado 30/09/2010 em 07:13
fonte usuário
Em outras línguas...                            


1 respostas

votos
3

O que você está pedindo é conhecido no campo CS acadêmica como "matrizes parcialmente persistentes". Para mais informações sobre a persistência, consulte o levantamento de Kaplan .

Uma solução simples é usar árvores de busca ao invés de arrays. Você pode usar árvores de busca equilibradas puramente funcionais para garantir que cada leitura ou escrita leva O (lg n) no pior caso (onde n é o tamanho da matriz), em vez de O (1) tempo. (Se você manter as versões com carimbo de tempo em uma matriz extensível, acrescentando uma nova versão é O (1) amortizado e acessar uma versão antiga é O (1) no pior caso.)

Se você não estiver familiarizado com árvores de busca puramente funcionais, que você pode ler esta introdução para matrizes persistentes do Clojure . Eles são puramente funcionais árvores indexados de largura fixa inteiros (sob a forma de um trie), e, assim, ter fixado profundidade. Esta poderia ser a solução mais rápida para o seu problema, tanto pior caso e no mundo real.

As únicas outras matrizes parcialmente persistentes que estou ciente de pode levar mais tempo no pior caso. Alguns têm complexidade melhor amortizado e alguns têm complexidade melhor esperado se matrizes são acessados ​​de várias maneiras restritos.

Respondeu 03/10/2010 em 15:43
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more