Haskell中优先队列实现的比较 [英] Comparison of Priority Queue implementations in Haskell

查看：125
本文介绍了Haskell中优先队列实现的比较的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

Haskell似乎有几个优先级队列实现可用。例如，有：



这两个似乎都是纯优先级队列数据结构。前者基于手指树，这是我不熟悉的数据结构;后者是Data.Map的一个包装。还有



定义了纯粹的函数堆数据结构从中可以轻松地制定优先级队列。 。还有



使用Brodal / Okasaki数据结构，我认为它类似于非纯功能土地中的二项堆数据结构。



（哦，还有


  • Data.PriorityQueue（在priority-队列-0.2.2上hackage）


其功能对我来说不清楚，但似乎与建立优先级队列有关monad，这似乎是建立在Data.Map之上的，在这个问题中，我关心的是纯粹的功能优先级队列，所以我认为priority-queue-0.2.2包是无关紧要的。 'm错了！）

我需要一个纯函数优先级队列数据结构，用于我正在构建的项目。我想知道是否有人可以提供任何智慧的话，因为我决定在hackage提供的财富的尴尬之间。特别是：


  1. 假设我想在传统的优先级队列插入和extract-min操作之外，使用纯功能/不可变的演示文稿。上面提到的软件包有什么优点和缺点？有没有人有经验使用他们中的任何一个'愤怒'？性能的折衷是什么？可靠性？其他人使用哪种更广泛？ （使用这些可能会使我的代码更容易被他人阅读，因为他们更可能熟悉该库。）在作出决定之前，我还需要了解其他任何事情吗？

  2. 如果我也希望高效地合并优先级队列，那么呢？ （我不想这个项目，但我认为增加这个，但会让未来的读者更有用。）

  3. 是否有任何其他优先级队列包在那里，我错过了


解决方案

在hackage上可以找到大量的优先级队列实现，以完成您的列表：





其中我发现PSQueue有一个非常好的界面。我想这是第一个实现之一，在 this纸由拉尔夫Hinze。它可能不是最高效和最完整的实现，但到目前为止它满足了我的所有需求。



MonadReader中有一篇非常好的文章（ issue 16 ），由Louis Wassermann撰写（他还写了 pqueue 包）。在他的文章中，路易给出了各种不同的优先级队列实现，并且还包括了每种优先级队列的算法复杂性。
作为一些优先级队列内部简单性的突出例子，他包含了一些很酷的小实现。我最喜欢的一篇（摘自他的文章）： 

  data SkewHeap a = Empty | SkewNode a（SkewHeap a）（SkewHeap a）派生（显示）
 
（+++）:: 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 
 |否则= SkewNode x2（heap1 +++ r2）l2 
空++ ++ heap =堆$ b $ heap +++空=堆
 
 extractMin空=无
 extractMin（SkewNode xlr）= Just（x，l +++ r）

一个简短的用法示例：

  test = foldl（\acc x-> acc +++ x）空节点
 where nodes = map（\x-> SkewNode x Empty Empty）[3,5,1,9,7,2]

优先级队列实现的一些基准可以在这里找到和haskell中一个非常有趣的线程。 org 此处。


There seem to be several priority queue implementations available off-the-shelf for Haskell. For instance, there's:

both of which appear to be pure priority queue data structures. The former is based on finger trees, a data structure with which I'm unfamiliar; the latter is a wrapper around Data.Map. There's also

which defines purely functional heap data structures from which one can trivially make priority queues. . There're also

which both implement purely functional meldable heaps using the Brodal/Okasaki data structure, which I believe is analogous to the binomial heap data structure in non-pure functional land.

(Oh, and there's also

  • Data.PriorityQueue (in priority-queue-0.2.2 on hackage)

whose function is unclear to me, but which seems to be related building priority queues attached to a monad, and which seems to be built on top of Data.Map anyhow. In this question, I'm concerned with purely functional priority queues, so I think the priority-queue-0.2.2 package is irrelevant. But correct me if I'm wrong!)

I need a pure functional priority queue data structure for a project I'm building. I was wondering if anyone could provide any words of wisdom as I decide between the embarrassment of riches provided by hackage. Specifically:

  1. Suppose I want do features apart from the traditional priority queue insert and extract-min operations, in a purely-functional/immutable presentation. What are the pros and cons of the packages mentioned above? Does anyone have experience using any of them 'in anger'? What are the tradeoffs in performance? Reliability? Which are used more widely by others? (Using those might make my code easier for others to read, since they will be more likely to be familiar with the library.) Are there any other things I should know before making a decision between them?
  2. If I also want efficient merging of priority queues, what then? (I don't for this project, but I thought adding this but would make the SO question more useful for future readers.)
  3. Are there any other priority queue packages out there that I missed out?

解决方案

There is an abundance of priority queue implementations to be found on hackage, just to complete your list:

Out of those I found that PSQueue has an especially nice interface. I guess it was one of the first implementations and is nicely covered in this paper by Ralf Hinze. It might not be the most efficient and complete implementation but so far it has served all my needs.

There is a very good article in the MonadReader (issue 16) by Louis Wassermann (who also wrote the pqueue package). In his article Louis gives a variety of different priority queue implementations and also includes algorithmic complexities for each.
As a striking example of the simplicity of some priority queue internals he includes some cool little implementations. My favorite one (taken from his article):

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 )

Cool little implementation...a short usage example:

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

Some benchmarks of priority queue implementations can be found here and in a rather interesting thread on haskell.org here.

这篇关于Haskell中优先队列实现的比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆