Я хочу реализовать хранилище данных в памяти для веб-службы в Haskell. Я хочу запускать транзакции в STM
монаде.
Когда я использую хэш-таблицу Steam Haskell, я получаю только следующее: Data. BTree. HashTable. STM.
имя модуля и его сложности предполагают, что это реализовано в виде дерева. Я думаю, что массив должен быть более эффективным для изменяемых хеш-таблиц.
Есть ли причина избегать использования массива для STM
хеш-таблицы? Получу ли я что-нибудь с этой паровой хэш-таблицей или я должен просто использовать ссылку на пар IntMap
?
data-structures
haskell
Саймон Бергот
источник
источник
Store ! blah
иStore ! baz
должна быть последовательнойОтветы:
Проблема с реализацией хеш-таблицы, основанной непосредственно на массиве, состоит в том, что некоторые операции с ней неизбежно потребуют линейного изменения размера массива (т. Е. Создания массива большего или меньшего размера и копирования всех данных в него). Есть несколько стандартных алгоритмов, которые подходят к этой проблеме, например, Linear Hashing или Cuckoo Hashing .
Не так давно появился еще один алгоритм с именем Hash Array Mapped Trie , который приобрел большую популярность среди функциональных языков, таких как Clojure, Scala и, конечно же, Haskell (с библиотеками "unordered-container" и "hamtmap") благодаря поддержке постоянных структуры данных.
Недавно я выпустил специализированную библиотеку контейнеров на основе этого алгоритма под названием «stm-Containers», которая должна идеально соответствовать вашей задаче. Вы также можете ознакомиться со вступительным сообщением в блоге , в котором рассказывается о мотивах работы библиотеки и указываются контрольные показатели.
источник
Реализация, на которую вы ссылаетесь, является частью пакета для реализации параллельного B-Tree. Сам HashTable реализован как массив TVars объектов Data.Map.
Указанные значения сложности являются наихудшими . Помните, что хеш-таблицы обычно O (N) наихудший случай для поиска, вставки и удаления. Использование Map для блоков приводит к O (log (N)).
источник