In-Memory-Datenspeicher in Haskell

9

Ich möchte einen In-Memory-Datenspeicher für einen Webdienst in Haskell implementieren. Ich möchte Transaktionen in der STMMonade ausführen .

Wenn ich die Hash-Tabelle Steam Haskell google, erhalte ich nur Folgendes: Data. BTree. HashTable. STM.Der Modulname und die Komplexität legen nahe, dass dies als Baum implementiert ist. Ich würde denken, dass ein Array für veränderbare Hash-Tabellen effizienter sein sollte.

Gibt es einen Grund, die Verwendung eines Arrays für eine STMHashtabelle zu vermeiden ? Erhalte ich mit dieser Steam-Hash-Tabelle etwas oder sollte ich nur einen Steam-Ref zu einem verwenden IntMap?

data-structures haskell Simon Bergot
quelle
Beachten Sie, wenn Sie `TVar IntMap
Daniel Gratzer
@jozefg was meinst du?
Simon Bergot
Oh, tut mir leid, anscheinend habe ich den Rest verloren. Ich wollte sagen, dass Sie beschissene Parallelität bekommen, weil Sie modifizieren Store ! blahund Store ! bazsequentiell sein müssen
Daniel Gratzer
Wenn Sie auf „einen speicherinternen Datenspeicher“ sagen, meinst du so etwas wie Säure-Zustand ?
Ptharien Flamme
@ Ptharien'sFlame Ich suche etwas wirklich Einfacheres als das. Eigentlich suche ich nach einer einfachen veränderlichen Karte, die in der stm-Monade läuft. Ich weiß, dass ich dafür mehrere Optionen habe, und ich versuche zu bewerten, welche besser ist.
Simon Bergot

Antworten:

1

Das Problem bei einer Hash-Tabellen-Implementierung, die direkt auf einem Array basiert, besteht darin, dass für einige Operationen zwangsläufig eine lineare Größenänderung des Zeit-Arrays erforderlich ist (dh ein größeres / kleineres Array erstellt und alle Daten darauf kopiert werden). Es gibt mehrere Standardalgorithmen, die sich diesem Problem nähern, wie z. B. lineares Hashing oder Cuckoo Hashing .

Vor nicht allzu langer Zeit ist ein weiterer Algorithmus namens Hash Array Mapped Trie aufgetaucht, der aufgrund der Unterstützung von Persistent in funktionalen Sprachen wie Clojure, Scala und natürlich Haskell (mit den Bibliotheken "unordered-container" und "hamtmap") große Popularität erlangt hat Datenstrukturen.

Vor kurzem habe ich eine STM-spezialisierte Containerbibliothek veröffentlicht, die auf dem Algorithmus "stm-container" basiert und perfekt zu Ihrer Aufgabe passen sollte. Sie können auch einen einführenden Blog-Beitrag lesen, in dem eine Motivation hinter der Bibliothek behandelt und Benchmarks bereitgestellt werden.

Nikita Volkov
quelle
Danke für Ihre Antwort! Ich habe Ihr Paket nicht getestet, aber es sieht interessant aus. Ich werde es später überprüfen, aber basierend auf Ihrem Beitrag bin ich bereit zu glauben, dass es zu meinem ursprünglichen Ziel passt.
Simon Bergot
1

Die Implementierung, auf die Sie verweisen, ist Teil eines Pakets zum Implementieren eines gleichzeitigen B-Tree. Die HashTable selbst ist als Array von TVars von Data.Map-Objekten implementiert.

Die angegebenen Komplexitätswerte sind im ungünstigsten Fall . Denken Sie daran, dass Hashtabellen normalerweise O (N) Worst Case für das Nachschlagen, Einfügen und Löschen sind. Wenn Sie Map für die Buckets verwenden, wird es auf O (log (N)) reduziert.

user2313838
quelle