以循环方式移位序列的最佳实践
以循环方式移位序列的最佳实践
提问于 2012-01-16 15:10:58
我必须实现一种数组或序列或列表，它支持循环转发和回绕元素的最便宜的方式。请参阅此示例：
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的答案！
回答 11
Stack Overflow用户
回答已采纳
发布于 2012-01-16 17:40:34
不可变的实现
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)。一般来说，这不是真的。一如既往:视情况而定。
不可变的
- update：
O(log n)基本上是底层O(log n)O(1)的更新复杂性，它还涉及创建一个新对象，这可能会耗费一些
周期
可变的
数组更新：O(1)，
- ，
O(1)O(n)，就像它更新一样快，你必须触摸每个元素一次；基元数组上的快速实现可能仍然会胜过小数组的不可变版本，因为恒定因子
Stack Overflow用户
发布于 2012-01-16 15:48:32
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)Stack Overflow用户
发布于 2013-04-14 17:20:21
我自己也需要这样的手术，就是这样。方法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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8876769
复制相关文章
相似问题
腾讯云开发者
