Сравнение реализаций Приоритетной очереди в Haskell

Кажется, есть несколько приоритетных реализаций очереди, доступных для Haskell. Например, есть:

оба из которых кажутся структурами данных очереди с чистым приоритетом. Первый основан на пальцах, структуре данных, с которой я незнаком; последний является оберткой вокруг Data.Map. Есть также

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

которые оба реализуют чисто функциональные складываемые кучи, используя структуру данных Brodal/Okasaki, которая, как я полагаю, аналогична структуре данных биномиальной кучи в не чистых функциональных областях.

(О, и есть также

  • Data.PriorityQueue (в priority-queue-0.2.2 при взломе)

чья функция мне не ясна, но которая, кажется, связана с очередями построения приоритетов, прикрепленными к монаде, и которая, похоже, в любом случае построена поверх Data.Map. В этом вопросе меня интересуют чисто функциональные очереди с приоритетами, поэтому я считаю, что пакет priority-queue-0.2.2 не имеет значения. Но поправьте меня, если я ошибаюсь!)

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

  1. Предположим, я хочу делать функции, помимо традиционных операций вставки в очередь с приоритетами и извлечения минут, в чисто функциональной / неизменной презентации. Каковы плюсы и минусы упомянутых выше пакетов? У кого-нибудь есть опыт использования любого из них "в гневе"? Каковы компромиссы в производительности? Надежность? Какие из них более широко используются другими? (Их использование может упростить чтение моего кода для других, поскольку они с большей вероятностью будут знакомы с библиотекой.) Есть ли еще какие-то вещи, которые я должен знать, прежде чем принимать решение между ними?
  2. Если я также хочу эффективное объединение приоритетных очередей, что тогда? (Я не для этого проекта, но я думал добавить это, но сделал бы вопрос SO более полезным для будущих читателей.)
  3. Существуют ли какие-либо другие пакеты очередей с приоритетами, которые я пропустил?
Источник

1 ответ

Решение

Существует множество реализаций очереди с приоритетами, которые можно найти на hackage, просто чтобы завершить ваш список:

Из них я обнаружил, что у PSQueue особенно приятный интерфейс. Я предполагаю, что это была одна из первых реализаций, и она хорошо освещена в этой статье Ральфа Хинце. Возможно, это не самая эффективная и полная реализация, но пока она удовлетворяет все мои потребности.

В MonadReader есть очень хорошая статья ( выпуск 16) Луиса Вассермана (который также написал пакет pqueue). В своей статье Луи дает множество различных реализаций очереди приоритетов, а также включает алгоритмические сложности для каждой из них.
В качестве яркого примера простоты некоторых внутренних объектов приоритетной очереди он включает в себя несколько интересных маленьких реализаций. Мой любимый (взят из его статьи):

data SkewHeap a = Empty | SkewNode a (SkewHeap a) (SkewHeap a) deriving (Show)

(+++) :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
heap1@(SkewNode x1 l1 r1) +++ heap2@(SkewNode x2 l2 r2) 
  | x1 <= x2    = SkewNode x1 (heap2 +++ r1) l1 
  | otherwise = SkewNode x2 (heap1 +++ r2) l2
Empty +++ heap = heap
heap +++ Empty = heap

extractMin Empty = Nothing
extractMin (SkewNode x l r ) = Just (x , l +++ r )

Крутая маленькая реализация... краткий пример использования:

test = foldl (\acc x->acc +++ x) Empty nodes
  where nodes = map (\x-> SkewNode x Empty Empty) [3,5,1,9,7,2]

Некоторые тесты реализации приоритетных очередей можно найти здесь и в довольно интересном потоке на haskell.org здесь.

Источник
Другие вопросы по тегам