#data-structures #haskell #hashtable
#структуры данных #haskell #хэш-таблица
Вопрос:
Я ищу структуру данных, которая работает немного похоже Data.HashTable , но которая не обременена монадой ввода-вывода. На данный момент я использую [(ключ, val)]. Я хотел бы структуру, которая равна O (log n), где n — количество пар ключ-значение.
Структура создается нечасто по сравнению с тем, как часто ее нужно читать, и когда она построена, у меня есть все пары ключ-значение, доступные одновременно. Ключи — это String s, если это имеет значение.
Также было бы неплохо узнать, при каком размере стоит отказаться от [(key,val)].
Комментарии:
1. Черт возьми, я бы посоветовал вам никогда не использовать
[(key,val)]. Интерфейс кData.Mapнамного более полный, и производительность будет заметно выше для всех, кроме самых маленьких коллекций (возможно, < 10 элементов?)2. Джон Л. Я унаследовал эту структуру в виде «Напишите себе схему за 48 часов».
3. Джон Ф. Миллер: Это иногда возникает, потому что есть предварительные функции для работы с этим (например,
lookup), и это может быть очень удобно. Мне всегда кажется, что в конечном итоге я получаю длинные композиции функций с большим количествомfsts иsnds, которые гораздо более удобочитаемы с надлежащимMapинтерфейсом.
Ответ №1:
Вы могли бы рассмотреть:
или альтернативно,
Первая является стандартным контейнером для хранения и поиска элементов по ключам в Haskell. Последняя представляет собой новую библиотеку, специально оптимизированную для хэширования ключей.
В недавнем докладе Йохана Тибелла «Более быстрые постоянные структуры данных за счет хеширования» дается общий обзор, в то время как в недавнем документе симпозиума Haskell Милана Страки конкретно описывается Data.Map структура и пакет hashmap.
Ответ №2:
Если у вас есть все пары ключ-значение заранее, вы можете рассмотреть идеальную хэш-функцию.
Сравнительный анализ подскажет вам, когда следует переключиться с простого списка.