Лучшая практика для смещения последовательности по кругу

Question

Я должен реализовать своего рода массив, последовательность или список, который поддерживает самый дешевый способ пересылки и обратной обмотки элементов. Смотрите этот пример:

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.

UPDATE:

Для самого быстрого, но не очень идиоматического варианта алгоритма (вы знаете, когда он вам нужен), обратитесь к ответу Петра Пудлака !!!

Answer 1

Неизменная реализация

A кольцевой буфер представляет собой пару указателей IndexedSeq и Int в этой последовательности. Я предоставляю код для неизменяемой версии. Обратите внимание, что не все методы, которые могут быть полезны, реализованы; как мутаторы, которые изменяют содержание 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)

Сравнение производительности с изменяемыми реализациями

ОП упоминает, что вы должны посмотреть на изменчивые реализации (например, этот ответ ), если вам нужна производительность. Это не совсем так. Как всегда: это зависит.

Неизменное

• update: O(log n), что в основном является сложностью обновления базового IndexedSeq;
• shifting: O(1), также включает создание нового объекта, который может стоить несколько циклов

Mutable

• обновление: O(1), обновление массива, так быстро, как он получает
• shift: O(n), вы должны касаться каждого элемента один раз; быстрые реализации на примитивных массивах могут по-прежнему выигрывать у неизменяемой версии для небольших массивов из-за постоянного фактора

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

Answer 3

Мне нужна была такая операция, вот она.Метод 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;
  }

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

Answer 5

Я решаю проблемы с 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 обеспечивают цикл, хотя я был приятно удивлен, обнаружив, что они предоставляют tails), и несколько toList s (списки на Haskell *)1020 * - это ленивые потоки, в то время как Scala - строгие), но в остальном он точно такой же, как Haskell, и, насколько я могу судить, ведет себя точно так же.Вы можете почти думать о . Скалы как о поведении, похожем на поведение Хаскелла, за исключением того, что он движется в противоположном направлении.

Также обратите внимание, что это почти то же самое, что и решение dhg, за исключением случаев, когда нет обращений, которые (с другой стороны) делаютон более эффективен, но (с другой стороны) обеспечивает циклы в «обратном» порядке, а не «прямом».

Answer 6

Существует очень простое решение:

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

Answer 7

Мое мнение:

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

Answer 8

Вы можете создать экземпляр функции, которая будет включать массив (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)

Answer 9

Мое предложение:

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)

Answer 10

Вот еще одно простое решение scala для смещения потока вправо или влево на произвольные величины.«Цикл» повторяет поток бесконечно, затем «сдвиг» находит правильный срез.«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)