Implementação de estrutura de dados imutável (persistente) semelhante a uma matriz com indexação rápida, acréscimo, pré-acréscimo, iteração

11

Estou procurando uma estrutura de dados persistente semelhante à matriz (mas imutável), permitindo operações rápidas de indexação, acréscimo, pré-acréscimo e iteração (boa localidade).

O Clojure fornece Vector persistente, mas é apenas para anexação rápida. O vetor de Scala efetivamente anexa e pré-anexa em tempo constante, mas não consigo entender como ela é implementada, pois é baseada na mesma estrutura de dados (vetor trie com mapeamento de bits) que o vetor Clojure e, como eu entendo, vetor trie com mapeamento em bit não pode ter um prefixo rápido sem alguns truques.

Não estou interessado em estar pronto para usar a implementação, mas em uma descrição de como implementar essa estrutura de dados.

Tvaroh
fonte

Respostas:

13

O candidato óbvio é uma árvore binária equilibrada persistente . Todas as operações listadas podem ser executadas em ou O ( lg n ) , usando a cópia de caminho . Para mais detalhes sobre como atingir esse tempo de execução, consulte o livro de Chris Okasaki mencionado abaixo ou minha resposta aqui .O(1)O(lgn)

Obviamente, como uma variante, cada folha dessa árvore poderia conter uma matriz imutável (uma sequência de valores consecutivos). Isso torna a atualização de um valor menos eficiente, mas pode funcionar bem para a sua situação, se você nunca pretender modificar um valor existente, basta acrescentar e acrescentar. Dessa maneira, seu vetor é representado como uma sequência de sequências imutáveis, representada como uma árvore binária equilibrada com matrizes imutáveis ​​nas folhas. Isso permite indexação rápida (logarítmica no número de folhas), adição e pré-adição rápidas e iteração rápida. A pior complexidade assintótica não é melhor, mas o desempenho na prática pode ser significativamente melhor.

A referência padrão é o livro de Chris Okasaki, de 1998, "Estruturas de dados puramente funcionais".
Veja também

DW
fonte
Obrigado. Parece que as árvores RRB são boas candidatas e já possuem (não totalmente) a implementação do Clojure.
Tvaroh
Eu acho que Okasaki nos diz como atingir esses tempos de execução sob imutabilidade e persistência?
Raphael
1
@ Rafael, sim. Adicionei referências para explicar como você alcança o tempo de execução (no início da minha resposta).
DW
4

Descrevi uma implementação dessa estrutura de dados em meu artigo sobre correspondência incremental de expressões regulares - consulte http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation e o texto abaixo e acima dessa seção .

É uma variedade de árvores de altura constante (como árvores B ou 2-3 árvores). Basicamente, é uma (2,3) árvore, cujas folhas são (N, 2N-1) matrizes, para evitar sobrecarga por elemento. (Uma matriz (N, 2N-1) é uma matriz cujos comprimentos estão no intervalo N..2N-1.) N maior fornece uma sobrecarga menor, mas aumenta linearmente a complexidade da divisão e concatenação. Operações como indexação, divisão e concatenação são muito semelhantes à maneira como trabalham em 2-3 árvores, generalizando para (N, 2N-1) no nível da folha.

jkff
fonte
Links quebram; forneça uma referência adequada e robusta (que permita que as pessoas encontrem seu trabalho sem o link).
Raphael
Não publiquei o artigo em nenhum periódico, apenas no meu site pessoal. Provavelmente deveria colocá-lo em Arxiv, boa ideia.
JKFF
Eu estava pensando principalmente no (s) autor (es), título e ano - isso facilita o Google, se necessário. Colocá-lo no arXiv seria ainda melhor, é verdade!
Raphael