arrays - trigonometricas - Las mejores prácticas para cambiar una secuencia de manera circular

resta en r

Question

Tengo que implementar un tipo de matriz, secuencia o lista, que admita la forma más económica de reenvío y devanado de elementos. Vea este ejemplo:

Original sequence: 1 2 3 4 5

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

Lo mismo pero opuesto es para el devanado trasero. ¿Cuál sería la forma más económica y más al estilo de Scala de implementar esto? En Java podría usar LinkedList y sería genial ... Sin embargo, no pude encontrar ninguna respuesta definitiva para Scala.

Además, también debe ser fácil reemplazar cualquier elemento dado por el índice, como en LinkedList.

ACTUALIZAR:

Para la variante más rápida, pero no tan idiomática del algoritmo (¡sabe cuándo la necesita), refiérase a la respuesta de Petr Pudlák!

Answer 1

Implementación inmutable

Un búfer de anillo es un par de un IndexedSeq y un puntero Int en esta secuencia. Proporciono código para una versión inmutable. Tenga en cuenta que no se implementan todos los métodos que podrían ser útiles; como los mutadores que cambian el contenido del IndexedSeq .

Con esta implementación, el cambio es solo crear un nuevo objeto. Así que es bastante eficiente.

Código de ejemplo

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)

Salida

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

Comparación de rendimiento a implementaciones mutables

El OP menciona que debe ver las implementaciones mutables (por ejemplo, esta respuesta ), si necesita rendimiento. Esto no es cierto en general. Como siempre: depende.

Inmutable

• actualización: O(log n) , que es básicamente la complejidad de actualización del IndexedSeq subyacente;
• shifting: O(1) , también implica crear un nuevo objeto que puede costar algunos ciclos

Mudable

• actualización: O(1) , actualización de matriz, tan rápido como llega
• desplazamiento: O(n) , debes tocar cada elemento una vez; Las implementaciones rápidas en matrices primitivas aún podrían ganar contra la versión inmutable para matrices pequeñas, debido al factor constante

Answer 2

Aquí hay otra solución simple de Scala para desplazar un Stream hacia la derecha o hacia la izquierda en cantidades arbitrarias. "Ciclo" repite la secuencia de manera infintada, luego "shift" encuentra la porción correcta. "posMod" le permite desplazarse en un índice mayor que xs.length pero sin desviar realmente más que xs.length elementos en la Corriente infinita:

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)

Entonces:

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)

Answer 3

Aquí hay una posible solución para las secuencias.

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 )

Answer 4

Buena combinación de las versiones @dhg y @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

Hay una solución muy simple:

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 6

La forma en que resuelvo los problemas de Scala es resolverlos en Haskell primero, y luego traducir. :)

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

Esta es la forma más fácil en la que puedo pensar, que produce la lista de todos los cambios posibles, "girando a la izquierda" repetidamente.

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

El concepto es relativamente simple (para quienes están cómodos con la programación funcional, eso es). Primero, cycle un cycle la lista original, produciendo un flujo infinito desde el cual extraer. A continuación, divida esa secuencia en una secuencia de secuencias, donde cada secuencia subsiguiente haya eliminado el primer elemento de la secuencia anterior ( tails ). A continuación, limite cada secuencia secundaria a la longitud de la lista original ( map (take len) ). Finalmente, limite el flujo de flujos a la longitud de la lista original, ya que solo hay len posibles reordenaciones ( take len ).

Así que hagamos eso en Scala ahora.

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
}

Solo tuvimos que usar una pequeña solución para el cycle (no estoy seguro de si las bibliotecas estándar de Scala proporcionan el ciclo, aunque me sorprendió gratamente al descubrir que proporcionan tails ), y algunas toList (las listas de Haskell son corrientes perezosas, mientras que las de Scala son estrictas) pero aparte de eso, es exactamente lo mismo que el Haskell, y por lo que puedo decir, se comporta exactamente igual. Casi se puede pensar en la de Scala . como comportarse como el de Haskell, excepto fluir en sentido contrario.

También tenga en cuenta que esto es casi lo mismo que la solución de dhg, excepto sin los reveses, lo que (en el lado positivo) lo hace más eficiente, pero (en el lado negativo) proporciona los ciclos en el orden de "retroceso", en lugar del orden "hacia adelante".

Answer 7

Mi opinión sobre esto:

@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

Mi proposición:

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 9

Puede crear una instancia de una función que incluirá el Array (A) y el número de pasos de rotación que necesita (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 10

Yo necesitaba tal operación, aquí está. El método de rotate gira la secuencia indexada dada (matriz) hacia la derecha (los valores negativos se desplazan hacia la izquierda). El proceso está en el lugar, por lo que no se requiere memoria adicional y se modifica la matriz original.

No es específico de Scala o funcional en absoluto, está destinado a ser muy rápido.

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 11

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)