Хороший выбор для функциональной структуры для вставки и поиска

Question

Мне нужна структура данных, которая поддерживает следующие операции как с памятью, так и с экономией времени, можно предположить, что значение имеет порядок.

• Добавить значение в структуру
• Узнайте, находится ли значение в структуре

Плюс, структура должна быть неизменной, потому что я хочу использовать Haskell.

Если бы я не сталПредположим, неизменность, возможно, фильтр Блума - мой выбор.

Я пишу свою проблему оптимизации, и поскольку я не могу быть уверен, что запись уже обработана, мне нужно искать.

Answer 1

Data.Set действительно самый простой выбор, но если вы можете проецировать свою структуру данных на Int, то вы можете использовать IntSet, чтобы получить большую эффективность, чем Data.Set.Если ваша проекция с потерями (то есть, это действительно хеш), то хеш-таблица с использованием базового IntSet (то есть HashSet) часто будет более эффективной.Именно такой пакет существует в Hackage и был оценен как чертовски хороший: http://hackage.haskell.org/package/hashmap.

Наконец, если вам нужна проверка членства, но не извлечение, и вы действительно хотите использовать минимальное пространство, тогда выможет проецировать вашу структуру данных в целое число (при условии, что это дает экономию пространства, что на самом деле зависит ...), а затем использовать HashSet из них.

Answer 2

Структура данных, обычно используемая в случаях, когда вам необходимо часто проверять членство, - Data.Set, это набор на основе дерева, который предлагает операции поиска и вставки за O(log n) время.

Тем не менее, поскольку вы упомянули фильтры Блума: * * * * * * * * * * * * * * * * * *. Так что в ситуации, когда вы выбрали бы фильтры Блума на других языках, вы все равно можете сделать это в Haskell.