Armazenamento de dados na memória em Haskell

9

Quero implementar um armazenamento de dados na memória para um serviço da Web em Haskell. Eu quero executar transações na STMmônada.

Quando eu coloco no Google o haskell da tabela de hash, recebo apenas isso: Data. BTree. HashTable. STM.O nome e as complexidades do módulo sugerem que isso é implementado como uma árvore. Eu pensaria que uma matriz deveria ser mais eficiente para tabelas de hash mutáveis.

Existe um motivo para evitar o uso de uma matriz para uma STMhashtable? Ganho alguma coisa com esta tabela de hash de vapor ou devo apenas usar uma referência de vapor para uma IntMap?

data-structures haskell Simon Bergot
fonte
Note, se você usar o `TVar IntMap
Daniel Gratzer
@jozefg o que você quer dizer?
Simon Bergot
Oh, desculpe, aparentemente, eu perdi o resto disso, eu ia dizer que você vai ter paralelismo de baixa qualidade porque modifing Store ! blahe Store ! bazterá de ser sequenciais
Daniel Gratzer
Quando você diz "um armazenamento de dados na memória", você quer dizer algo como estado ácido ?
Chama de Ptharien
@ Ptharien'sFlame Estou procurando algo realmente mais simples do que isso. Na verdade, estou procurando um mapa mutável simples que roda na mônada stm. Sei que tenho várias opções para isso e estou tentando avaliar qual é a melhor.
21813 Simon Bergot

Respostas:

1

O problema com uma implementação de tabela de hash baseada diretamente em uma matriz é que algumas das operações nela exigirão inevitavelmente redimensionamento linear da matriz de tempo (ou seja, criar uma matriz maior / menor e copiar todos os dados para ela). Existem vários algoritmos padrão que abordam esse problema, como Linear Hashing ou Cuckoo Hashing .

Há pouco tempo , surgiu outro algoritmo chamado Hash Array Mapped Trie , que ganhou grande popularidade em linguagens funcionais como Clojure, Scala e, é claro, Haskell (com as bibliotecas "unordered-containers" e "hamtmap") devido ao suporte a persistentes estruturas de dados.

Há pouco tempo, lancei uma biblioteca de contêineres especializada em STM, com base nesse algoritmo chamado "stm-containers", que deve se encaixar perfeitamente na sua tarefa. Você também pode conferir uma postagem introdutória do blog , cobrindo uma motivação por trás da biblioteca e fornecendo referências.

Nikita Volkov
fonte
Obrigado por responder! Não testei seu pacote, mas parece interessante. Verificarei mais tarde, mas com base no seu post, estou pronto para acreditar que ele se encaixa no meu objetivo inicial.
Simon Bergot
1

A implementação que você faz referência faz parte de um pacote para implementar uma B-Tree simultânea. O próprio HashTable é implementado como uma matriz de TVars de objetos Data.Map.

Os valores de complexidade citados são os piores casos . Lembre-se de que as hashtables geralmente são O (N) o pior caso para pesquisa, inserção e exclusão. Usar o Mapa para os buckets reduz para O (log (N)).

user2313838
fonte