Archivio dati in memoria in Haskell

Question

Archivio dati in memoria in Haskell

#1 da (1 voti)
#2 da (1 voti)

9

Voglio implementare un datastore in memoria per un servizio Web in Haskell. Voglio eseguire transazioni in STM monad.

Quando ho google hash table haskell ottengo solo questo: Data. BTree. HashTable. STM. Il nome e le complessità del modulo suggeriscono che questo è implementato come un albero. Penserei che un array dovrebbe essere più efficiente per le tabelle hash mutabili.

C'è un motivo per non utilizzare un array per un hash STM ? Guadagno qualcosa con questa tabella di hash del vapore o dovrei semplicemente usare un riferimento di vapore su un IntMap ?

data-structures haskell

posta Simon 16.07.2013 - 13:37
fonte

2 risposte

1

Il problema con un'implementazione della tabella hash basata direttamente su un array è che alcune operazioni su di esso richiedono inevitabilmente un ridimensionamento lineare degli array di tempo (cioè, creando un array più grande / più piccolo e copiando tutti i dati su di esso). Esistono più algoritmi standard che si avvicinano a questo problema, come Linear Hashing o Cuckoo Hashing .

Non molto tempo fa è emerso un altro algoritmo denominato Hash Array Mapped Trie , che ha ottenuto una grande popolarità tra i linguaggi funzionali come Clojure , Scala e, ovviamente, Haskell (con le librerie "unordered-containers" e "hamtmap") grazie al supporto di strutture dati persistenti.

Non molto tempo fa ho rilasciato una libreria di contenitori specializzati STM basata su quell'algoritmo chiamato "stm-containers" , che dovrebbe adattarsi perfettamente al tuo compito. Puoi anche consultare un post sul blog introduttivo , che copre una motivazione dietro la biblioteca e fornisce punti di riferimento.

risposta data 01.09.2014 - 17:09
fonte

1

L'implementazione che tu fai riferimento fa parte di un pacchetto per l'implementazione di un B-Tree simultaneo. Lo stesso HashTable è implementato come una serie di TVars di oggetti Data.Map.

I valori di complessità indicati sono worst-case . Ricorda che gli hashtables sono generalmente O (N) nel caso peggiore per la ricerca, l'inserimento e la cancellazione. L'uso di Map per the bucket lo riporta a O (log (N)).

risposta data 02.07.2014 - 16:24
fonte

Leggi altre domande sui tag data-structures haskell

Cos'è questo dominio di studio? Buone pratiche per il confezionamento di programmi Python

score 1 · Accepted Answer

Il problema con un'implementazione della tabella hash basata direttamente su un array è che alcune operazioni su di esso richiedono inevitabilmente un ridimensionamento lineare degli array di tempo (cioè, creando un array più grande / più piccolo e copiando tutti i dati su di esso). Esistono più algoritmi standard che si avvicinano a questo problema, come Linear Hashing o Cuckoo Hashing .

Non molto tempo fa è emerso un altro algoritmo denominato Hash Array Mapped Trie , che ha ottenuto una grande popolarità tra i linguaggi funzionali come Clojure , Scala e, ovviamente, Haskell (con le librerie "unordered-containers" e "hamtmap") grazie al supporto di strutture dati persistenti.

Non molto tempo fa ho rilasciato una libreria di contenitori specializzati STM basata su quell'algoritmo chiamato "stm-containers" , che dovrebbe adattarsi perfettamente al tuo compito. Puoi anche consultare un post sul blog introduttivo , che copre una motivazione dietro la biblioteca e fornisce punti di riferimento.