arrays - 以循环方式移动序列的最佳实践

Question

我必须实现一种数组或序列或列表，它支持循环转发和回绕元素的最便宜方式。看这个例子:

Original sequence: 1 2 3 4 5

Forwarded once: 5 1 2 3 4
Forwarded twice: 4 5 1 2 3

相同但相反的是反向绕组。什么是最便宜和最具 Scala 风格的实现方式？在 Java 中，我可以使用 LinkedList，它会做得很好......但是，我找不到 Scala 的任何明确答案。

此外，它还必须易于通过索引替换任何给定元素，如 LinkedList。

更新:

对于最快但不那么惯用的算法变体(你知道什么时候需要它)，请参阅 Petr Pudlák 的答案!!!

Answer 1

不可变的实现

一个 ring buffer是一对 IndexedSeq和 Int指向这个序列的指针。我提供不可变版本的代码。请注意，并非所有可能有用的方法都已实现；就像改变 IndexedSeq 内容的突变器一样.

通过这个实现，shifting 只是创建一个新对象。所以它非常有效。

示例代码

class RingBuffer[A](val index: Int, val data: IndexedSeq[A]) extends IndexedSeq[A] {
  def shiftLeft = new RingBuffer((index + 1) % data.size, data)
  def shiftRight = new RingBuffer((index + data.size - 1) % data.size, data)
  def length = data.length
  def apply(i: Int) = data((index + i) % data.size)
}

val rb = new RingBuffer(0, IndexedSeq(2,3,5,7,11))

println("plain: " + rb)
println("sl: " + rb.shiftLeft)
println("sr: " + rb.shiftRight)

输出

plain: Main(2, 3, 5, 7, 11)
sl: Main(3, 5, 7, 11, 2)
sr: Main(11, 2, 3, 5, 7)

与可变实现的性能比较

OP 提到如果您需要性能，您应该查看可变实现(例如 this answer )。一般情况下这是不正确的。一如既往:这取决于。

不可变

更新:O(log n) ，基本就是底层IndexedSeq的更新复杂度;

换档:O(1) ，还涉及创建一个新对象，这可能会花费一些周期

可变的

更新:O(1) , 数组更新，尽快

换档:O(n) ，你必须触摸每个元素一次；由于常数因子

，原始数组的快速实现可能仍会胜过小型数组的不可变版本。