Best practice for shifting a sequence in a circula

问题:

I have to implement a kind of an array or sequence or list, which supports the cheapest way of circulated forwarding and back winding of elements. See this example:

Original sequence: 1 2 3 4 5

Forwarded once: 5 1 2 3 4
Forwarded twice: 4 5 1 2 3

Same but opposite is for the back winding. What would be the cheapest and most Scala-style way of implementing this? In Java I could use LinkedList and it would do great... However, I could not find any definite answer for Scala.

Also, it also has to be easy to replace any given element by index, as in LinkedList.

UPDATE:

For the fastest, but not-so-idiomatic variant of algorithm (you know when you need it), refer to the answer of Petr Pudlák!!!

回答1:

Immutable implementation

A ring buffer is a pair of an IndexedSeq and an Int pointer into this sequence. I provide code for a immutable version. Note that not all methods that might be useful are implemented; like the mutators that change the content of the IndexedSeq.

With this implementation, shifting is just creating one new object. So it's pretty efficient.

Example code

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)

Output

plain: Main(2, 3, 5, 7, 11)
sl: Main(3, 5, 7, 11, 2)
sr: Main(11, 2, 3, 5, 7)

Performance comparison to mutable implementations

The OP mentions that you should look at the mutable implementations (e.g. this answer), if you need performance. This is not true in general. As always: It depends.

Immutable

• update: O(log n), which is basically the update complexity of the underlying IndexedSeq;
• shifting: O(1), also involves creating a new object which may cost some cycles

Mutable

• update: O(1), array update, as fast as it gets
• shifting: O(n), you have to touch every element once; fast implementations on primitive arrays might still win against the immutable version for small arrays, because of constant factor

回答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)

回答3:

I needed such an operation myself, here it is. Method rotate rotates the given indexed sequence (array) to the right (negative values shift to the left). The process is in-place, so no additional memory is required and the original array is modified.

It's not Scala-specific or functional at all, it's meant to be very fast.

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;
  }

回答4:

The way I solve Scala problems is solving them in Haskell first, and then translating. :)

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

This is the easiest way I could think of, which produces the list of all possible shifts, by "shifting left" repeatedly.

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]]

The concept is relatively simple (for those comfortable with functional programming, that is). First, cycle the original list, producing an infinite stream from which to draw from. Next, break that stream into a stream of streams, where each subsequent stream has dropped the first element of the previous stream (tails). Next, limit each substream to the length of the original list (map (take len)). Finally, limit the stream of streams to the length of the original list, since there are only len possible reorderings (take len).

So let's do that in Scala now.

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
}

We just had to use a small workaround for cycle (not sure if Scala standard libs provide cycle, though I was pleasantly surprised to find they provide tails), and a few toLists (Haskell lists are lazy streams, while Scala's are strict), but other than that, it's exactly the same as the Haskell, and as far as I can tell, behaves exactly the same. You can almost think of Scala's . as behaving like Haskell's, except flowing the opposite way.

Also note this is very nearly the same as dhg's solution, except without the reverses, which (on the upside) makes it more efficient, but (on the downside) provides the cycles in "backwinding" order, rather than "forward" order.

回答5:

Nice combination of @dhg and @Roman Zykov versions:

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)

回答6:

There is a very simple solution:

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))

回答7:

My take on it:

@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);
}

回答8:

Here is one possible solution for sequences

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
  }
} 

val initialSeq = ( 0 to 9 )

( initialSeq shiftLeft ) shiftRight
shift_n_Times(
  5,
  initialSeq,
  initialSeq => new ShiftWarper( initialSeq ).shiftRight )

回答9:

Here's another simple scala solution for shifting a Stream right or left by arbitrary amounts. "Cycle" repeats the stream infintely, then "shift" finds the correct slice. "posMod" allows you to shift by an index larger than xs.length but without actually straying more than xs.length elements in the infinite Stream:

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)

Then:

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)

回答10:

My proposition:

def circ[A]( L: List[A], times: Int ): List[A] = {
    if ( times == 0 || L.size < 2 ) L
    else circ(L.drop(1) :+ L.head , times-1)
}

val G = (1 to 10).toList
println( circ(G,1) ) //List(2, 3, 4, 5, 6, 7, 8, 9, 10, 1)
println( circ(G,2) ) //List(3, 4, 5, 6, 7, 8, 9, 10, 1, 2)
println( circ(G,3) ) //List(4, 5, 6, 7, 8, 9, 10, 1, 2, 3)
println( circ(G,4) ) //List(5, 6, 7, 8, 9, 10, 1, 2, 3, 4)

回答11:

You can instantiate a function that will include the Array(A) and the number of rotation steps that you need(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)