首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >以循环方式移位序列的最佳实践

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

Stack Overflow用户
提问于 2012-01-16 15:10:58
回答 11查看 6.4K关注 0票数 18

我必须实现一种数组或序列或列表,它支持循环转发和回绕元素的最便宜的方式。请参阅此示例:

代码语言:javascript
复制
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的答案!

EN

回答 11

Stack Overflow用户

回答已采纳

发布于 2012-01-16 17:40:34

不可变的实现

ring buffer是一对指向此序列的IndexedSeqInt指针。我提供了一个不可变版本的代码。请注意,并不是所有可能有用的方法都实现了;比如更改IndexedSeq内容的赋值器。

通过这种实现,shifting只是创建了一个新对象。所以它是非常高效的。

示例代码

代码语言:javascript
复制
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)

输出

代码语言:javascript
复制
plain: Main(2, 3, 5, 7, 11)
sl: Main(3, 5, 7, 11, 2)
sr: Main(11, 2, 3, 5, 7)

与可变实现的性能比较

OP提到,如果你需要性能,你应该考虑可变的实现(例如this answer)。一般来说,这不是真的。一如既往:视情况而定。

不可变的

  • update:O(log n)基本上是底层O(log n) O(1)的更新复杂性,它还涉及创建一个新对象,这可能会耗费一些

周期

可变的

数组更新:O(1)

  • O(1) O(n),就像它更新一样快,你必须触摸每个元素一次;基元数组上的快速实现可能仍然会胜过小数组的不可变版本,因为恒定因子
票数 20
EN

Stack Overflow用户

发布于 2012-01-16 15:48:32

代码语言:javascript
复制
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)
票数 9
EN

Stack Overflow用户

发布于 2013-04-14 17:20:21

我自己也需要这样的手术,就是这样。方法rotate将给定的索引序列(数组)向右旋转(负值向左移动)。该过程是就地进行的,因此不需要额外的内存,并且修改了原始数组。

它不是特定于Scala的,也不是函数式的,它意味着非常快。

代码语言:javascript
复制
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;
  }
票数 5
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/8876769

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档