Оперативное хранилище данных в Haskell

9

Я хочу реализовать хранилище данных в памяти для веб-службы в Haskell. Я хочу запускать транзакции в STMмонаде.

Когда я использую хэш-таблицу Steam Haskell, я получаю только следующее: Data. BTree. HashTable. STM.имя модуля и его сложности предполагают, что это реализовано в виде дерева. Я думаю, что массив должен быть более эффективным для изменяемых хеш-таблиц.

Есть ли причина избегать использования массива для STMхеш-таблицы? Получу ли я что-нибудь с этой паровой хэш-таблицей или я должен просто использовать ссылку на пар IntMap?

Саймон Бергот
источник
Обратите внимание, если вы используете `TVar IntMap
Daniel Gratzer
@jozefg что ты имеешь ввиду?
Саймон Бергот
Извините, очевидно, я потерял все остальное, я собирался сказать, что вы получите дерьмовый параллелизм, потому что модификация Store ! blahи Store ! bazдолжна быть последовательной
Даниэль Гратцер
Когда вы говорите «хранилище данных в памяти», вы имеете в виду что-то вроде кислотного состояния ?
Пламя Птариена
@ Ptharien'sFlame Я ищу что-то более простое, чем это. На самом деле я ищу простую изменяемую карту, которая работает в монаде STM. Я знаю, что у меня есть несколько вариантов для этого, и я пытаюсь оценить, какой из них лучше.
Саймон Бергот

Ответы:

1

Проблема с реализацией хеш-таблицы, основанной непосредственно на массиве, состоит в том, что некоторые операции с ней неизбежно потребуют линейного изменения размера массива (т. Е. Создания массива большего или меньшего размера и копирования всех данных в него). Есть несколько стандартных алгоритмов, которые подходят к этой проблеме, например, Linear Hashing или Cuckoo Hashing .

Не так давно появился еще один алгоритм с именем Hash Array Mapped Trie , который приобрел большую популярность среди функциональных языков, таких как Clojure, Scala и, конечно же, Haskell (с библиотеками "unordered-container" и "hamtmap") благодаря поддержке постоянных структуры данных.

Недавно я выпустил специализированную библиотеку контейнеров на основе этого алгоритма под названием «stm-Containers», которая должна идеально соответствовать вашей задаче. Вы также можете ознакомиться со вступительным сообщением в блоге , в котором рассказывается о мотивах работы библиотеки и указываются контрольные показатели.

Никита Волков
источник
Спасибо за ответ! Я не проверял вашу посылку, но она выглядит интересно. Я проверю это позже, но, основываясь на вашем посте, я готов поверить, что он соответствует моей первоначальной цели.
Саймон Бергот
1

Реализация, на которую вы ссылаетесь, является частью пакета для реализации параллельного B-Tree. Сам HashTable реализован как массив TVars объектов Data.Map.

Указанные значения сложности являются наихудшими . Помните, что хеш-таблицы обычно O (N) наихудший случай для поиска, вставки и удаления. Использование Map для блоков приводит к O (log (N)).

user2313838
источник