Подтвердить что ты не робот

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

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

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:

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

4b9b3361

ОТВЕТЫ

Ответ 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)

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

В OP упоминается, что вы должны посмотреть на изменяемые реализации (например, этот ответ), если вам нужна производительность. В общем, это не так. Как всегда: это зависит.

Неизменное

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

Mutable

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

Ответ 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

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

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

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

Ответ 5

Хорошая комбинация версий @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)

Ответ 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))

Ответ 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);
}

Ответ 8

Вот одно возможное решение для последовательностей

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

Здесь другое простое решение 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)

Ответ 10

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

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

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