我希望能够维护一个不可变的有界FIFO队列,可以在一定时间后移除最旧的值。在Scala中,immutable.Queue适用于大小有限的队列(.size似乎是基于List进行的,因此其复杂度为O(N),但我可以单独维护大小),但好像没有一种便宜的方法来访问头元素以测试最旧值的年龄,而且任何比O(N)更便宜的方式来测试最旧条目的过期状态都似乎不存在。有指针指向纯函数(不可变)的实现吗?
我希望能够维护一个不可变的有界FIFO队列,可以在一定时间后移除最旧的值。在Scala中,immutable.Queue适用于大小有限的队列(.size似乎是基于List进行的,因此其复杂度为O(N),但我可以单独维护大小),但好像没有一种便宜的方法来访问头元素以测试最旧值的年龄,而且任何比O(N)更便宜的方式来测试最旧条目的过期状态都似乎不存在。有指针指向纯函数(不可变)的实现吗?
编辑: Okasaki的论文 描述了一种优雅的、纯函数式的队列和双端队列(deque)实现。Deque允许从任一端添加或删除元素。所有这些操作都是O(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) { }
}
如果我理解问题正确的话,您正在寻找双端队列(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的页面上说它比他的其他实现更慢。如果您正在寻找双端队列(deque),Scala 1.13(2019年6月,八年后)现在有ArrayDeque
。
这是一个使用可调整大小的循环缓冲区内部实现的双向队列。
附加,前置,删除第一个,删除最后一个和随机访问(索引查找和索引替换)需要均摊常数时间。
一般来说,在i索引处的删除和插入是O(min(i,n-i)),因此从末尾/开头插入和删除速度较快。
这来自于scala/collection-strawman
PR 490,合并到Scala中的commit c0129af。