Haskell中的高效队列

up9lanfz 于 2023-10-19 发布在其他

关注(0)|答案(4)|浏览(87)

我如何有效地实现一个列表数据结构，其中我可以有2个视图的头部和尾部的列表，总是指向一个头部和尾部的列表，而没有昂贵的调用逆转。即：

start x = []
end x = reverse start -- []
start1 = [1,2,3] ++ start
end start1 -- [3,2,1]

end应该能够在不调用“reverse”的情况下完成此操作，而只是从列表自动反向的Angular 查看给定列表。如果我从连接开始创建新列表，也应该如此。

haskell

来源：https://stackoverflow.com/questions/1739675/efficient-queue-in-haskell

4条答案

按热度按时间

lf5gs5x21#

您可以始终使用Data.Sequence。
或者，纯函数队列的一个众所周知的实现是使用两个列表。一个用于入队，另一个用于出队。Enqueue与enqueue list是等价的。出队占据出队列表的头部。当出队列表比入队列表短时，通过反转入队列表来重新填充它。Chris Okasaki的Purely Functional Datastructures.
即使这个实现使用了reverse，其分摊的时间成本也是渐进的。它的工作原理是，对于每一个入队，你都要为出队列表的重新填充承担Θ（1）的时间债务。因此，出队的预期时间最多是入队时间的两倍。这是一个常数因子，所以两个操作的最坏情况成本都是O（1）。

赞(0）回复(0）举报 2023-10-19

v8wbuo2f2#

这个问题出现在第一页的第三个结果，而我谷歌Haskell queue，但以前给出的信息是误导。因此，我觉得有必要澄清几件事。（第一个搜索结果是一篇博客文章，其中包含一个粗心的实现...）
下面的内容基本上来自Okasaki在1995年的论文Simple and efficient purely functional queues and deques或他的book。
好了，我们开始吧。
1.一个具有摊销 O（1） 时间复杂度的持久队列实现是可能的。诀窍是反转表示队列后部的列表，只要前部足够长，可以分摊reverse操作的成本。所以，当前面部分是空的时候，我们不是反转后面部分，而是在前面部分比后面部分短的时候反转它。下面的代码来自Okasaki的书的附录

data BQueue a = BQ !Int [a] !Int [a]

check :: Int -> [a] -> Int -> [a] -> BQueue a
check lenf fs lenr rs =
  if lenr <= lenf 
  then BQ lenf fs lenr rs 
  else BQ (lenr+lenf) (fs ++ reverse rs) 0 [] 

head :: BQueue a -> a
head (BQ _ []    _ _) = error "empty queue"
head (BQ _ (x:_) _ _) = x

(|>) :: BQueue a -> a -> BQueue a 
(BQ lenf fs lenr rs) |> x = check lenf fs (lenr + 1) (x:rs)

tail :: BQueue a -> BQueue a
tail (BQ lenf (x:fs) lenr rs) = check (lenf-1) fs lenr rs

1.为什么这个摊销的 O（1） 甚至持续使用 *？Haskell是懒惰的，所以reverse rs实际上不会发生，直到需要它。要强制执行reverse rs，必须执行 *| fs| * 到达reverse rs之前的步骤。如果我们在到达悬挂reverse rs之前重复tail，那么结果将被存储，所以第二次只需要 O（1）。另一方面，如果我们在放置悬挂fs ++ reverse rs之前使用版本，那么在达到reverse rs之前，它必须再次经过fs步骤。使用（修改后的）银行家方法的正式证明在Okasaki的书中。
1.作者：@Apocalisp
当出队列表为空时，通过反转入队列表来重新填充它
是他书中第5章的实现，
不幸的是，本章中提出的简单的摊销观点在持久性存在时会被打破
Okasaki在第6章中描述了他的摊销 O（1） 持久队列。
1.到目前为止，我们只讨论了摊销的时间复杂度。实际上，完全消除摊销以实现 * 持久队列 * 的最坏情况 O（1） 时间复杂度是可能的。诀窍在于，每次调用de/enqueue时，reverse都必须被强制递增。不过，实际的实现在这里有点难以解释。
再说一遍，他的报纸上已经写满了。