以循环方式移动序列的最佳实践 [英] Best practice for shifting a sequence in a circular manner

问题描述

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

I have to implement a kind of an array or sequence or list, which supports the cheapest way of circulated forwarding and back winding of elements. See this example:

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 的任何明确答案.

Same but opposite is for the back winding. What would be the cheapest and most Scala-style way of implementing this? In Java I could use LinkedList and it would do great... However, I could not find any definite answer for Scala.

此外，它也必须很容易通过索引替换任何给定的元素，就像在 LinkedList 中一样.

Also, it also has to be easy to replace any given element by index, as in LinkedList.

更新:

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

For the fastest, but not-so-idiomatic variant of algorithm (you know when you need it), refer to the answer of Petr Pudlák!!!

推荐答案

Immutable implementation

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

Immutable implementation

A ring buffer is a pair of an IndexedSeq and an Int pointer into this sequence. I provide code for a immutable version. Note that not all methods that might be useful are implemented; like the mutators that change the content of the IndexedSeq.

通过这种实现，移位只是创建一个新对象.所以效率很高.

With this implementation, shifting is just creating one new object. So it's pretty efficient.

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).这在一般情况下是不正确的.一如既往:这取决于.

Performance comparison to mutable implementations

The OP mentions that you should look at the mutable implementations (e.g. this answer), if you need performance. This is not true in general. As always: It depends.

• update:O(log n)，基本就是底层IndexedSeq的更新复杂度；
• 移位:O(1)，还涉及创建一个新对象，这可能会花费一些周期

• update: O(log n), which is basically the update complexity of the underlying IndexedSeq;
• shifting: O(1), also involves creating a new object which may cost some cycles

• 更新:O(1)，数组更新，尽可能快
• shifting:O(n)，你必须触摸每个元素一次；由于常数因素，原始数组的快速实现可能仍然胜过小数组的不可变版本

• update: O(1), array update, as fast as it gets
• shifting: O(n), you have to touch every element once; fast implementations on primitive arrays might still win against the immutable version for small arrays, because of constant factor

这篇关于以循环方式移动序列的最佳实践的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！