Почему Haskell Maps реализован как сбалансированные бинарные деревья вместо традиционных хеш-таблиц?

Ответ 1

Хэш-таблицы не могут быть эффективно реализованы без изменяемого состояния, поскольку они основаны на поиске массива. Ключ хэшируется, и хеш определяет индекс в массив ведер. Без изменяемого состояния вставка элементов в хэш-таблицу становится O (n), потому что весь массив должен быть скопирован (альтернативные варианты копирования, такие как DiffArray, представляют значительную производительность штраф). Реализации бинарного дерева могут совместно использовать большую часть их структуры, поэтому только несколько указателей необходимо скопировать на вставках.

Haskell, безусловно, может поддерживать традиционные хэш-таблицы, при условии, что обновления находятся в подходящей монаде. hashtables package, вероятно, является наиболее широко используемой реализацией.

Одно из преимуществ двоичных деревьев и других неперемещающихся структур заключается в том, что они постоянны: возможно сохранить старые копии данных без дополнительного учета. Это может быть полезно, например, для своего рода алгоритма транзакций. Они также автоматически потокобезопасны (хотя обновления не будут отображаться в других потоках).

Ответ 2

Традиционные хеш-таблицы полагаются на мутацию памяти при их реализации. Mutable memory и ссылочная прозрачность находятся на концах, так что переопределяет хэш-таблицы для мозаик IO или ST. Деревья могут быть реализованы настойчиво и эффективно, оставив старые листья в памяти и возвращая новые корневые узлы, которые указывают на обновленные деревья. Это позволяет нам иметь чистые Map s.

Квинтэссенцией является Крис Окасаки Чисто функциональные структуры данных.

Ответ 3

Почему это? Использование двоичного дерева уменьшает время поиска до O (log (n)) в отличие от O (1)

Поиск - это только одна из операций; включение/модификация может быть более важным во многих случаях; есть также соображения памяти. Основная причина, по которой было выбрано древовидное представление, вероятно, что она больше подходит для чистого функционального языка. Как "Real World Haskell" ставит его:

Карты предоставляют нам те же возможности, что и хэш-таблицы на других языках. Внутри карта реализована как сбалансированное двоичное дерево. По сравнению с хэш-таблицей это гораздо более эффективное представление на языке с неизменяемыми данными. Это самое наглядный пример того, как глубоко чисто функциональное программирование влияет как мы пишем код: мы выбираем структуры данных и алгоритмы, которые мы можем выразить чисто и эффективно выполнять, но наш выбор для конкретных задач, которые часто отличаются их коллеги в императивных языках

Это:

и требует, чтобы элементы находились в Ord.

не кажется большим недостатком. В конце концов, с хэш-картой вам нужны клавиши Hashable, которые кажутся более ограничительными.

В каких приложениях бинарное дерево будет намного хуже, чем хэш-таблица? А как насчет другого пути? Много ли случаев, когда было бы намного предпочтительнее другого? Есть ли традиционная хэш-таблица в Haskell?

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

Ответ 4

Мой ответ на то, что преимущество использования бинарных деревьев, будет: запросы диапазона. Они требуют, семантически, полного предзаказа и получают прибыль от сбалансированной организации дерева поиска алгоритмически. Для простого поиска я боюсь, что могут быть только хорошие ответы, относящиеся к Haskell, но не хорошие ответы как таковые: Lookup (и действительно хеширование) требует только setoid (равенство/эквивалентность по типу ключа), которое поддерживает эффективное хеширование указатели (которые по уважительным причинам не упорядочены в Haskell). Как и различные формы попыток (например, тройные попытки для элементарного обновления, другие для массовых обновлений) хеширование в массивы (открытые или закрытые), как правило, значительно более эффективны, чем поиск по элементам в бинарных деревьях, как пространственных, так и временных. Хеширование и попытки могут быть определены в общих чертах, хотя это должно быть сделано вручную - GHC не выводит его (пока?). Структуры данных, такие как Data.Map, как правило, хороши для прототипирования и для кода вне горячих точек, но там, где они горячие, они легко становятся узким местом производительности. К счастью, программистам Haskell не нужно беспокоиться о производительности, только их менеджеры. (По какой-то причине я в настоящее время не могу найти способ получить доступ к ключевой функции выкупа деревьев поиска среди 80+ функций Data.Map: интерфейс запроса диапазона. Я ищу неправильное место?)