Quais classes de estruturas de dados podem ser feitas persistentes?

19

Estruturas de dados persistentes são estruturas de dados imutáveis. As operações neles retornam uma nova "cópia" da estrutura de dados, mas alterada pela operação; a estrutura de dados antiga permanece inalterada. A eficiência geralmente é alcançada compartilhando alguns dos dados subjacentes e evitando a cópia completa da estrutura de dados.

Questões:

  • Existem resultados sobre classes de estruturas de dados que podem ser persistentes (mantendo as complexidades iguais ou muito semelhantes)?

  • Podem todos estruturas de dados ser feita persistente (mantendo os mesmos ou muito semelhantes complexidades)?

  • Sabe-se que alguma estrutura de dados não pode ser tornada persistente (mantendo as mesmas complexidades ou muito semelhantes)?

Realz Slaw
fonte
1
Você não pode tornar um vetor persistente com complexidade O (1) preservada para acessar um elemento aleatório.
smossen
2
@smossen você pode provar isso?
Realz Slaw
1
Sua primeira pergunta é uma pergunta muito ampla. Existem muitos resultados no tópico de estruturas de dados que podem ser persistentes. Alguém poderia escrever um livro inteiro sobre o assunto, e algumas pessoas têm: por exemplo, o livro de Okasaki é um clássico sobre o assunto. Você já fez alguma pesquisa sobre esse tópico? Você pode refinar a pergunta? Tal como está, suspeito que possa ser amplo demais para ser um bom ajuste para este site. Talvez dividir a terceira pergunta em uma pergunta separada?
DW
@Realz Slaw: Não posso provar formalmente, mas acho que é bom senso. O (1) acesso a elementos em vetores (incluindo tabelas de hash) depende de tempo fixo para decodificação de endereço em um determinado hardware. A persistência adiciona uma ou duas dimensões, além do índice de vetores. Mas os endereços de hardware ainda são unidimensionais.
smossen

Respostas:

22

Resultado positivo: persistência não custa muito. Pode-se mostrar que toda estrutura de dados pode ser totalmente persistente, com no máximo uma desaceleração de .O(lgn)

Prova: você pode pegar uma matriz e torná-la persistente usando estruturas de dados padrão (por exemplo, uma árvore binária balanceada; veja o final desta resposta para um pouco mais detalhadamente). Isso gera uma desaceleração : cada acesso ao array leva tempo O ( lg n ) com a estrutura de dados persistente, em vez do tempo O ( 1 ) para o array não persistente. Agora pegue qualquer algoritmo imperativo cujo tempo de execução no modelo de RAM seja O ( f ( n ) ) , em que n indica a quantidade de memória usada. Representar toda a memória como uma grande matriz (comO(lgn)O(lgn)O(1)O(f(n))n elementos) e torne-o persistente usando um mapa persistente. Cada etapa do algoritmo imperativo acarreta no máximo umadesaceleração de O ( lg n ) , portanto o tempo total de execução é O ( f ( n ) lg n ) .nO(lgn)O(f(n)lgn)

Aparentemente, é possível melhorar um pouco: aparentemente, é possível reduzir o fator de desaceleração para (tempo esperado, amortizado), usando as técnicas do artigo de Demaine, citadas abaixo - mas não estou familiarizado com os detalhes desse trabalho, então eu não posso garantir isso sozinho. Obrigado a jbapple por esta observação.O(lglgn)


Resultado negativo: você não pode evitar uma desaceleração em algumas estruturas de dados. Para responder à sua terceira pergunta, existem estruturas de dados em que é sabido que torná-las persistentes introduz alguma desaceleração.

Em particular, considere uma matriz de elementos. Sem persistência, cada acesso à matriz leva O ( 1 ) tempo (no modelo de RAM). Com persistência, aparentemente foi demonstrado que não há como construir uma matriz persistente com O ( 1 ) pior complexidade para acessar um elemento aleatório. Em particular, aparentemente há um limite inferior mostrando que matrizes totalmente persistentes devem ter tempo de acesso Ω ( lg lg n ) . Esse limite inferior é afirmado na p.3 do seguinte artigo:nO(1)O(1)Ω(lglgn)

O limite inferior é atribuído a Mihai Patrascu, mas não há citação para uma fonte que fornece os detalhes da prova desse limite inferior declarado.


Uma área rica de pesquisa. Se usarmos uma estrutura de dados ou algoritmo arbitrário, é uma pergunta delicada se você pode torná-lo persistente com, no máximo, lentidão ou não. Não conheço nenhum teorema geral de classificação. No entanto, existem muitas pesquisas sobre maneiras de tornar persistentes estruturas de dados específicas, de maneira eficiente.O(1)

Há também uma forte conexão com linguagens de programação funcionais. Em particular, toda estrutura de dados que pode ser implementada de maneira puramente funcional (sem mutações) já é uma estrutura de dados persistente. (O inverso não é necessariamente o caso, infelizmente.) Se você quer olhar de soslaio, pode considerar isso como um tipo fraco de teorema de classificação parcial: se for implementável em uma linguagem de programação puramente funcional com os mesmos limites de tempo como em como uma linguagem imperativa, existe uma estrutura de dados persistente com os mesmos limites de tempo que a não persistente. Sei que isso provavelmente não é o que você estava procurando - é apenas uma reformulação trivial da situação.


O(lgn)

dd

nO(lgn)O(lgn)O(lgn)

Você pode encontrar mais explicações, com fotos bonitas, nos seguintes recursos:

Isso lhe dará a idéia principal. Há detalhes extras a serem resolvidos, mas os detalhes estão fora do escopo desta pergunta. Felizmente, tudo isso é padrão e há muita informação disponível na literatura sobre como construir essas estruturas de dados. Sinta-se à vontade para fazer uma pergunta separada se os recursos acima não forem suficientes e desejar obter mais informações sobre os detalhes da construção de uma estrutura de dados de matriz persistente.

DW
fonte
Eu realmente não entendo o primeiro parágrafo, como eu faria para tornar uma matriz persistente usando uma árvore vermelha-preta?
G. Bach
@ G.Bach, há uma boa explicação nas seções rotuladas "Árvores de pesquisa binária" e "Estruturas de acesso aleatório" (especificamente, o método de árvore) em toves.org/books/persist/index.html . Para outra boa descrição, consulte netcode.ru/dotnet/?artID=6592#BinaryTrees e algumas das seções subseqüentes. Isso lhe dará a idéia principal. Os detalhes estão fora do escopo desta pergunta, mas tudo isso é padrão; Convido você a fazer uma pergunta separada, se desejar obter mais informações sobre como criar essa estrutura de dados.
DW
4
O(lglgn)