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

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中.

更新:

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

Answer 1

不可改变的实施

甲环缓冲器是一对的IndexedSeq和的Int指针插入此序列中.我提供了不可变版本的代码.请注意,并非所有可能有用的方法都已实现; 喜欢改变内容的变异者IndexedSeq.

通过这种实现,转移只是创建一个新对象.所以效率非常高.

示例代码

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提到你应该看看可变实现(例如这个答案),如果你需要性能的话.事实并非如此.一如既往:这取决于.

不可变

• 更新:O(log n),这基本上是底层的更新复杂性IndexedSeq;
• 转移:O(1)还涉及创建一个可能花费一些周期的新对象

易变的

• 更新:O(1),数组更新,尽可能快
• 转移:O(n)你必须触摸一次元素; 由于常数因素,原始数组上的快速实现仍可能胜过小数组的不可变版本

Answer 2

scala> val l = List(1,2,3,4,5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> val reorderings = Stream.continually(l.reverse).flatten.sliding(l.size).map(_.reverse)
reorderings: Iterator[scala.collection.immutable.Stream[Int]] = non-empty iterator

scala> reorderings.take(5).foreach(x => println(x.toList))
List(1, 2, 3, 4, 5)
List(5, 1, 2, 3, 4)
List(4, 5, 1, 2, 3)
List(3, 4, 5, 1, 2)
List(2, 3, 4, 5, 1)

Answer 3

我自己需要这样的操作,就在这里.方法rotate将给定的索引序列(数组)向右旋转(负值向左移动).该过程就位,因此不需要额外的内存,并且修改了原始数组.

它根本不是Scala特有的或功能性的,它意味着速度非常快.

import annotation.tailrec;
import scala.collection.mutable.IndexedSeq

// ...

  @tailrec
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a
    else gcd(b, a % b);

  @inline
  def swap[A](a: IndexedSeq[A], idx: Int, value: A): A = {
    val x = a(idx);
    a(idx) = value;
    return x;
  }

  /**
   * Time complexity: O(a.size).
   * Memory complexity: O(1).
   */
  def rotate[A](a: IndexedSeq[A], shift: Int): Unit =
    rotate(a, 0, a.size, shift);
  def rotate[A](a: IndexedSeq[A], start: Int, end: Int, shift: Int): Unit = {
    val len = end - start;
    if (len == 0)
      return;

    var s = shift % len;
    if (shift == 0)
      return;
    if (s < 0)
      s = len + s;

    val c = gcd(len, s);
    var i = 0;
    while (i < c) {
      var k = i;
      var x = a(start + len - s + k);
      do {
        x = swap(a, start + k, x);
        k = (k + s) % len;
      } while (k != i);
      i = i + 1;
    }
    return;
  }