Исполняющая структура Хаскелла.

Я пишу программу, которая много ищет таблицы. Таким образом, я изучал документацию Haskell, когда я наткнулся на Data.Map (конечно), но также Data.HashMap и Data.Hashtable. Я не эксперт по алгоритмам хеширования, и после проверки пакетов все они кажутся очень похожими. Поэтому мне было интересно:

1: каковы основные отличия, если таковые имеются?

2: что было бы наиболее эффективным с большим объемом поиска на картах/таблицах из ~ 4000 пар ключ-значение?

Ответы

Ответ 1

1: Каковы основные отличия, если они есть?

  • Data.Map.Map является сбалансированным двоичным деревом внутри, поэтому его временная сложность для поиска - O (log n). Я считаю, что это " persistent" структура данных, что означает, что она реализована так, что мутационные операции дают новую копию только с соответствующими частями структуры обновлены.
  • Data.HashMap.Map является внутренним элементом Data.IntMap.IntMap, который, в свою очередь, реализуется как дерево Патрисии; его временной сложностью для поиска является O (min (n, W)), где W - количество бит в целых числах. Он также "настойчив".
  • Data.HashTable.HashTable - фактическая хеш-таблица с временной сложностью O (1) для поиска. Тем не менее, это изменяемая структура данных - операции выполняются на месте - поэтому вы застряли в монаде IO, если хотите ее использовать.

2: что было бы наиболее эффективным с большим объемом поиска на картах/таблицах из ~ 4000 пар ключ-значение?

Лучший ответ, который я могу вам дать, к сожалению, - "это зависит". Если вы берете асимптотические сложности буквально, вы получаете O (log 4000) = около 12 для Data.Map, O (min (4000, 64)) = 64 для Data.HashMap и O (1) = 1 для Data.HashTable. Но на самом деле это не так. Вы должны попробовать их в контексте вашего кода.

Ответ 2

Очевидное различие между Data.Map и Data.HashMap заключается в том, что для первого нужны ключи в Ord, последние Hashable ключи. Большинство общих ключей - оба, так что это не решающий критерий. У меня нет никакого опыта с Data.HashTable, поэтому я не могу прокомментировать это.

API-интерфейсы Data.HashMap и Data.Map очень похожи, но Data.Map экспортирует больше функций, некоторые, например, alter отсутствуют в Data.HashMap, другие предоставляются в строгих и нестрогих вариантах, тогда как Data.HashMap (я предполагаю, что вы имели в виду hashmap из unordered-containers) предоставляет ленивые и строгие API в отдельных модулях. Если вы используете только общую часть API, переключение действительно безболезненно.

Что касается производительности, Data.HashMap unordered-containers имеет довольно быстрый поиск, последний измеренный, он был явно быстрее, чем Data.IntMap или Data.Map, который выполняется, в частности, для (еще не выпущенной) ветки HAMT unordered-containers. Я думаю, что для вставок он был более или менее наравне с Data.IntMap и несколько быстрее, чем Data.Map, но я немного расплывчатый.

Оба являются достаточно эффективными для большинства задач, для тех задач, где они не являются, вам, вероятно, потребуется индивидуальное решение. Учитывая, что вы спрашиваете конкретно о поиске, я бы дал Data.HashMap ребро.

Ответ 3

Data.HashTable Документация теперь говорит: "Используйте hashtables package". Там хорошая запись в блоге, объясняющая, почему hashtables - хороший пакет здесь. Он использует монаду ST.