我必须实现一种数组或序列或列表,它支持循环转发和回绕元素的最便宜的方式。请参阅此示例:
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的答案!
发布于 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)。一般来说,这不是真的。一如既往:视情况而定。
不可变的
O(log n)
基本上是底层O(log n)
O(1)
的更新复杂性,它还涉及创建一个新对象,这可能会耗费一些周期
可变的
数组更新:O(1)
,
O(1)
O(n)
,就像它更新一样快,你必须触摸每个元素一次;基元数组上的快速实现可能仍然会胜过小数组的不可变版本,因为恒定因子发布于 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)
发布于 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;
}
https://stackoverflow.com/questions/8876769
复制相似问题