有没有一个纯函数式实现的有界队列，其中peek()的时间复杂度为O(1)？

Question

有没有一个纯函数式实现的有界队列，其中peek()的时间复杂度为O(1)？

9

我希望能够维护一个不可变的有界FIFO队列，可以在一定时间后移除最旧的值。在Scala中，immutable.Queue适用于大小有限的队列（.size似乎是基于List进行的，因此其复杂度为O(N)，但我可以单独维护大小），但好像没有一种便宜的方法来访问头元素以测试最旧值的年龄，而且任何比O(N)更便宜的方式来测试最旧条目的过期状态都似乎不存在。有指针指向纯函数（不可变）的实现吗？

- Alex B Dunlop

4个回答

1

在Scala中，标准的immutable.Queue可以被适应为具有分摊复杂度的工作方式。但请注意，peek操作将返回一个新队列，否则，连续调用peek可能会以O(n)的时间完成。

您可以扩展Queue或创建一个完全新的适配类。这里是一个扩展它的版本：

import scala.collection._
import generic._
import immutable.Queue
import mutable.{ Builder, ListBuffer }

class MyQueue[+A] protected(in0: List[A], out0: List[A]) extends scala.collection.immutable.Queue[A](in0, out0) with GenericTraversableTemplate[A, MyQueue] with LinearSeqLike[A, MyQueue[A]] {
  override def companion: GenericCompanion[MyQueue] = MyQueue

  def peek: (A, MyQueue[A]) = out match {
    case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new MyQueue(Nil, rev))
    case x :: xs            => (x, this)
    case _                  => throw new NoSuchElementException("dequeue on empty queue")
  }

  override def tail: MyQueue[A] =
    if (out.nonEmpty) new MyQueue(in, out.tail)
    else if (in.nonEmpty) new MyQueue(Nil, in.reverse.tail)
    else throw new NoSuchElementException("tail on empty queue")

  override def enqueue[B >: A](elem: B) = new MyQueue(elem :: in, out)

  // This ought to be override, but scalac doesn't think so!
  def enqueue[B >: A](iter: Iterable[B]) =
    new MyQueue(iter.toList.reverse ::: in, out)

  override def dequeue: (A, MyQueue[A]) = out match {
    case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new MyQueue(Nil, rev.tail))
    case x :: xs            => (x, new MyQueue(in, xs))
    case _                  => throw new NoSuchElementException("dequeue on empty queue")
  }

  override def toString() = mkString("MyQueue(", ", ", ")")
}

object MyQueue extends SeqFactory[MyQueue] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyQueue[A]] = new GenericCanBuildFrom[A]
  def newBuilder[A]: Builder[A, MyQueue[A]] = new ListBuffer[A] mapResult (x => new MyQueue[A](Nil, x.toList))
  override def empty[A]: MyQueue[A] = EmptyQueue.asInstanceOf[MyQueue[A]]
  override def apply[A](xs: A*): MyQueue[A] = new MyQueue[A](Nil, xs.toList)

  private object EmptyQueue extends MyQueue[Nothing](Nil, Nil) { }
}

- Daniel C. Sobral

0

如果我理解问题正确的话，您正在寻找双端队列（deque）。Okasaki、Kaplan和Tarjan有关纯函数deque的论文。至于实现，最简单的方法我认为是采用collection.immutable.IndexedSeq的默认实现，即collection.immutable.Vector，根据this table估计常数成本为head和last（它说tail，但我猜last也是O(1)）。

Okasaki/Kaplan/Tarjan的那个看起来已经由Henry Ware实现了。

另一种我想到的实现是由Hintze设计的FingerTree，Scala中有不同的实现。Scalaz 中也有一个实现，一段时间前我将其放入了一个单独的包，因为我经常使用它。根据Daniel Spiewak的演示（我忘记在哪里看到的），FingerTree在常数时间因素上相当慢 - 而且Henry Ware的页面上说它比他的其他实现更慢。

- 0__

0

如果您正在寻找双端队列（deque），Scala 1.13（2019年6月，八年后）现在有ArrayDeque。

这是一个使用可调整大小的循环缓冲区内部实现的双向队列。

附加，前置，删除第一个，删除最后一个和随机访问（索引查找和索引替换）需要均摊常数时间。

一般来说，在i索引处的删除和插入是O（min（i，n-i）），因此从末尾/开头插入和删除速度较快。

这来自于scala/collection-strawman PR 490，合并到Scala中的commit c0129af。

- VonC

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kipton Barros · Accepted Answer

这篇文章，Haskell: Queues without pointers，介绍了一种纯函数队列，其添加和删除元素的平摊成本为O(1)（编辑）。我认为这个数据结构来自Chris Okasaki，更多细节可以在他的书中找到。

基本思路是将队列分解为两个列表，一个用于前端，一个用于后端。新元素添加到“front”，“back”以相反的顺序存储，以便弹出元素。当“back”的所有元素都消失时，“front”被翻转并重新标识为“back”。这个数据结构对这些操作具有O(1)的平摊成本，但显然通过一些工作，它可以降低到O(1)。

编辑: Okasaki的论文描述了一种优雅的、纯函数式的队列和双端队列（deque）实现。Deque允许从任一端添加或删除元素。所有这些操作都是O(1)，最坏情况下。