data-structures - O que é a estrutura de dados mais eficiente para armazenar séries de tempo de mudança de matriz parcialmente? - CoreDump.pt
O que é a estrutura de dados mais eficiente para armazenar séries de tempo de mudança de matriz parcialmente?
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.
data-structurescore-datatimetime-seriesseries
Publicado 30/09/2010 em 07:13 2010-09-30 07:13
fonte usuário Dez Udezue
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 2010-10-03 15:43 share
fonte usuário jbapple
Método público swap (estáticos) () vs. redundantes (não-estáticos) os privados
escolher estrutura de dados direita
Como testar se uma fila livre-lock é implementado corretamente?
Rails: Estrutura de banco de dados CouchSurfing-Like
substituição Scala DoubleLinkedList
Eu preciso de uma ajuda para resolver desafio estrutura de dados do Hackerrank
Linkedlist- Inserir na posição Nth
JavaScript: tabela hash com lista ligada baldes não lidar com colisões
Qual estrutura de dados é melhor para apagar um elemento de uma determinada matriz posição ou linklist