Haskell 中提供的最佳（可变）队列数据结构-解网

问：

亲爱的堆栈交换器，

我目前正在实现一些算法，这些算法需要访问“队列”（FIFO）的数据结构。我正在使用 ST monad ，因此正在寻找与 ST monad 的“内存互斥性”相辅相成的队列实现。在这一点上，我只是想在列表中使用（但同样，访问最后一个元素是 O（n）复杂性，我想尽可能避免这种情况）。我还考虑过使用 Data.Sequence，尽管我不确定如果在没有初始化的情况下在 ST monad 中使用它是否真的是“可变的”。newSTRefnewSTRef

Stack Exchange 的优秀成员能否指导 Haskell 的初学者了解在上述上下文中最好的数据结构（或模块）是什么？

哈斯克尔数据结构函数式编程队列可变

Data.STRef 说它是“（严格的）ST monad 中的可变引用”。引用是一个“指针”。一个 STRef 可以包含另一个 STRef。当保存的 STRef 更新时，我们稍后检索它，检索到的 STRef 也会更新。因此，它就像一个指针。你可以用它们重新实现列表，让“节点”保存指向其他“节点”的“指针”。---例如返回。runST $ do { x <- newSTRef 11; xr <- newSTRef x; z <- writeSTRef x 8; x2 <- readSTRef xr; y <- read STRef x2, return y }8

0赞 Will Ness 10/5/2021

hackage.haskell.org/packages/search?terms=queue

答：

3赞 Daniel Wagner 10/5/2021 #1

选项包括在 STArray 之上实现传统的环形缓冲区，或使用由 s 构建的可变单向链表，如：STRef

type CellRef s a = STRef s (Cell s a)
data Cell s a = End | Cell a (CellRef s a)
data Q s a = Q { readHead, writeHead :: CellRef s a }

如果你想要一个环形缓冲区的低指针开销，你可以通过让每个单元格有一个慢慢填满的单元格来获得一个中间地带。当它已满时，分配一个新单元格;当从中读取清空它时，前进到下一个单元格。你明白了。QSTArray

FIFO 队列的标准实现是两个 LIFO 堆栈，一个包含从队列前面开始的项目（下一个要删除的项目在顶部），另一个包含从后面开始的项目（最近推送的项目在顶部）。从队列中弹出时，如果前堆栈为空，则将其替换为后堆栈的反转。

如果两个堆栈都作为 Haskell 列表实现，则向队列添加一个值是 O（1），如果数据结构以单线程方式使用，则删除一个值将摊销为 O（1）。恒定因素还不错。您可以将整个数据结构放在 STRef 中（这保证了单线程使用）。实现只需几行代码。你绝对应该优先于你的 O（n）单列表想法来做这件事。

您还可以使用 .与双栈队列一样，它是一种纯函数式数据结构，即对它的操作返回新的数据结构并保持旧的数据结构不变。但是，就像双堆栈队列一样，您只需将新数据结构写入保存旧数据结构的 STRef 中即可使其可变。常数因素可能比双堆栈队列差一点，但作为交换，您可以获得更大的高效操作集。Data.SequenceData.Sequence

David Wagner 的答案中的可变列表可能效率较低，因为它需要队列中的每个项目有两个堆对象。在 GHC 中，您可以通过编写

Cell a {-# UNPACK #-} !(CellRef s a)

代替 .不过，我不确定这是否有效。如果是这样，这可能比其他基于列表的方法要快一些。Cell a (CellRef s a)

谢谢benrg！“但是，就像双栈队列一样，您可以通过简单地将新数据结构写入保存旧数据结构的 STRef 来使其可变。我确实理解您如何要求我使用堆栈实现队列。此外，我还必须仔细研究数据结构 David 如何具有“每个项目两个对象”，以及您的数据结构如何避免这种情况。非常感谢您的回复！

上一个：在 Haskell 中模拟全局列表以生成唯一的随机值

下一个：Haskell 中可变的多变非积分类型列表

Haskell 中提供的最佳（可变）队列数据结构

Best (mutable) queue data structure available in Haskell

评论

评论

评论