Перформант Хаскелл хешировал структуру. - PullRequest
Новая
       4

Перформант Хаскелл хешировал структуру.

43 голосов
/ 25 октября 2011

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

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

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

Ответы [ 3 ]

50 голосов
/ 26 октября 2011

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. Но на самом деле это не работает ... Вы должны попробовать их в контексте своего кода.

11 голосов
/ 26 октября 2011

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

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

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

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

2 голосов
/ 08 августа 2013
Документация

Data.HashTable теперь гласит «используйте пакет hashtables ». Есть хороший пост в блоге, объясняющий, почему hashtables - хороший пакет здесь . Использует монаду ST.

...