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

Question

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

18

我必须实现一种类似于数组、序列或列表的数据结构，支持元素最廉价的环形前进和后退。请看以下示例：

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的答案！

- noncom

这可能对你有用：https://dev59.com/XnA75IYBdhLWcg3wg5Vh - om-nom-nom

我认为“位移操作”可能比“循环操作”更能准确表达您的意图，这是一种更专业的术语。 - fortran

@fortran 我只知道这个术语是从逻辑电路中得来的。因此它是一种特定的实现方式。你确定这适用于移位操作吗？ - ziggystar

@ziggystar 我想你是对的，可能我把HW术语和循环移位弄混了... 无论如何，应该用动词shift，而不是circulate（这是我在标题中发现的奇怪之处）。干杯。 - fortran

11个回答

9

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)

- dhg

不错的想法！功能性的。高效吗？ - Peter Schmitz

1

我觉得“reorderings”的类型很奇怪。一个Stream的Iterator？ - notan3xit

5

我自己需要这样的操作，这就是方法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;
  }

- Petr

4

很棒的结合了@dhg和@Roman Zykov版本：

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

scala> val re = Stream continually (l ++ l.init sliding l.length) flatten
re: scala.collection.immutable.Stream[List[Int]] = Stream(List(1, 2, 3, 4, 5), ?)

scala> re take 10 foreach println
List(1, 2, 3, 4, 5)
List(2, 3, 4, 5, 1)
List(3, 4, 5, 1, 2)
List(4, 5, 1, 2, 3)
List(5, 1, 2, 3, 4)
List(1, 2, 3, 4, 5)
List(2, 3, 4, 5, 1)
List(3, 4, 5, 1, 2)
List(4, 5, 1, 2, 3)
List(5, 1, 2, 3, 4)

- dk14

4

我解决Scala问题的方式是先在Haskell中解决，然后再翻译过来。 :)

reorderings xs = take len . map (take len) . tails . cycle $ xs
  where len = length xs

这是我能想到的最简单的方法，通过不断地“向左移位”来生成所有可能的移位列表。

ghci> reorderings [1..5]
[[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2],[4,5,1,2,3],[5,1,2,3,4]]

概念相对简单（对于那些熟悉函数式编程的人来说）。首先，将原始列表循环（使用cycle），生成一个无限流。接下来，将该流分成一系列子流，其中每个后续流都删除了前一个流的第一个元素（使用tails）。接下来，将每个子流限制为原始列表的长度（使用map（take len））。最后，将子流的流限制为原始列表的长度，因为只有len种可能的重新排序（使用take len）。

现在让我们用Scala实现它。

def reorderings[A](xs: List[A]):List[List[A]] = {
  val len = xs.length
  Stream.continually(xs).flatten // cycle
    .tails
    .map(_.take(len).toList)
    .take(len)
    .toList
}

我们只需要对cycle进行小型的变通（不确定Scala标准库是否提供了cycle，但很惊喜地发现它们提供了tails），以及一些toList操作（Haskell中的lists是惰性流，而Scala的lists是严格的），除此之外，它与Haskell完全相同，在我看来，行为也完全相同。你几乎可以认为Scala中的.像Haskell中的那样工作，只是方向相反。

另外请注意，这与dhg的解决方案非常接近，但没有反转操作（优点是更高效，缺点是将cycles以“倒序”的方式提供，而不是“正向”顺序）。

- Dan Burton

一个有趣的想法！坦白地说，我现在正在努力掌握FP，我的最初学习语言选择是Scala和Haskell，最终是Clojure。到目前为止，我所知道的Haskell也让我认为这是一个好的实践-用它来制定解决方案，然后再翻译成Scala)))但我还远没有完美掌握FP，所以感谢您提到了一个并行的例子。这将使我更加意识到它！ - noncom

3

有一个非常简单的解决方案：

val orderings = List(1,2,3,4,5)
(orderings ++ orderings.dropRight(1)).sliding(orderings.length).toList

List(List(1, 2, 3, 4, 5), List(2, 3, 4, 5, 1), List(3, 4, 5, 1, 2), List(4, 5, 1, 2, 3), List(5, 1, 2, 3, 4))

- Roman Zykov

2

我的看法是：

@tailrec
 def shift(times:Int, data:Array[Int]):Array[Int] = times match {
        case t:Int if(t <= 0) => data;
        case t:Int if(t <= data.length) => shift(0, (data++data.take(times)).drop(times)) 
        case _ => shift(times % data.length, data);
}

- Ylli Prifti

1

这里有一个简单的Scala解决方案，可以将流向右或向左移动任意量。 "Cycle"无限重复流，然后"shift"找到正确的片段。 "posMod"允许您按大于xs.length的索引进行移位，但实际上不会偏离无限流中的超过xs.length个元素：

scala> def posMod(a:Int, b:Int) = (a % b + b) % b

scala> def cycle[T](xs : Stream[T]) : Stream[T] = xs #::: cycle(xs)

scala> def shift[T](xs:Stream[T], x: Int) = cycle(xs)
          .drop(posMod(x, xs.length))
          .take(xs.length)

然后：

scala> shift(Stream(1,2,3,4), 3).toList
--> List[Int] = List(4, 1, 2, 3)

scala> shift(Stream(1,2,3,4), -3).toList
--> List[Int] = List(2, 3, 4, 1)

scala>  shift(Stream(1,2,3,4), 30000001).toList
--> List[Int] = List(2, 3, 4, 1)

- mikebridge

我认为在使用正数进行左移和负数进行右移时，与问题措辞的相反，其中“前进”向右移动，但您已经了解了这个意思。 - mikebridge

1

这里是一种可能的序列解决方案。

// imports required for: `Scala 2.13.10 (OpenJDK 64-Bit Server VM, Java 1.8.0_292)`
import scala.language.implicitConversions
import scala.language.postfixOps

class ShiftWarper( seq: Seq[ Int ] ) {
  def shiftLeft: Seq[ Int ] = if ( seq.isEmpty ) {
      seq
    } else {
      seq.tail :+ seq.head
    }
  def shiftRight: Seq[ Int ] = if ( seq.isEmpty ) {
      seq
    } else {
      seq.last +: seq.init
    }
}
implicit def createShiftWarper( seq: Seq[ Int ] ) =
    new ShiftWarper( seq ) 

def shift_n_Times(
  times: Int,
  seq: Seq[ Int ],
  operation: Seq[ Int ] => Seq[ Int ] ): Seq[ Int ] = if ( times > 0 ) {
    shift_n_Times(
      times - 1,
      operation( seq ),
      operation )
  } else {
    seq
  }

// main: unit test
val initialSeq = ( 0 to 9 )
// > val initialSeq: scala.collection.immutable.Range.Inclusive = Range 0 to 9
( initialSeq shiftLeft ) shiftRight
// > val res1: Seq[Int] = Vector(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
shift_n_Times(
  5,
  initialSeq,
  initialSeq => new ShiftWarper( initialSeq ).shiftRight )
// > val res2: Seq[Int] = Vector(5, 6, 7, 8, 9, 0, 1, 2, 3, 4)

- Alex Glukhovtsev

1

你可以实例化一个函数，该函数将包括数组(A)和所需的旋转步数(S)：

def rotate(A: Array[Int], S: Int): Int = { (A drop A.size - (S % A.size)) ++ (A take A.size - (S % A.size)) }

rotate(Array(1, 2, 3, 4, 5), 1)

- Oleg Keystop

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ziggystar · Accepted Answer

不可变实现

环形缓冲区是一个由 IndexedSeq 和指向该序列的整数指针组成的对。我提供了一个不可变版本的代码。请注意，并非所有可能有用的方法都被实现，如改变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)

可变实现的性能比较

原帖提到，如果需要性能要考虑使用可变实现（例如这个回答），但这并不是普遍适用的。就像往常一样：具体情况具体分析。

不可变实现

更新操作：O(log n)，基本上是底层IndexedSeq的更新复杂度；
移位操作：O(1)，但也涉及创建新对象，可能会消耗一些时间

可变实现

更新操作：O(1)，数组更新，速度非常快
移位操作：O(n)，需要逐个访问每个元素；对于小型数组来说，基于原始数组的快速实现可能仍然比不可变版本更快，因为有恒定因素的影响