Cómo convertir el algoritmo de retroceso a la transmisión?

¿Hay alguna manera de definir un stream con un algoritmo backtracking en Scala?Cómo convertir el algoritmo de retroceso a la transmisión?

Por ejemplo, el siguiente algoritmo backtracking imprime todas las cadenas "binarias" de un tamaño dado.

def binaries(s:String, n:Int) { 
    if (s.size == n) 
    println(s) 
    else { 
    binaries(s + '0', n) 
    binaries(s + '1', n) 
    } 
}

Creo que puedo definir un stream de cadenas "binario" de un tamaño determinado usando otro algoritmo iterativo. Sin embargo, me pregunto si puedo convertir el algoritmo de retroceso anterior en un stream.

Fuente

2011-12-24 Michael

Esto es bastante recta hacia adelante:

def binaries(s: String, n: Int): Stream[String] = 
    if (s.size == n) Stream(s) 
    else binaries(s + "0", n) append binaries(s + "1", n)

Nota el uso de append - este método no es estándar para la otra colecciones, que es un requisito porque tiene que tomar su parámetro por nombre.

Fuente

2011-12-24 21:55:53

Gracias, esto es exactamente lo que estoy buscando :) Parece más eficiente (en términos de consumo de memoria de pila) que la versión original de retroceso, ¿no? – Michael

@Michael Maybe. No me siento cómodo con la eficiencia de análisis del código con 'Stream'. Si considero que es necesario usarlos, me aseguro de probar el código en REPL para asegurarme de que no se desborde. –

@Michael, la versión de flujo es menos eficiente en términos de uso de marco de pila. Cada llamada recursiva usa 4 fotogramas de pila en comparación con solo uno en su versión. En la práctica, esto no debería ser un problema para este ejemplo. Con respecto al uso de la memoria de montón, la clase Stream es una de las menos eficaces de la colección scala en términos de uso de memoria por referencia almacenada, pero normalmente está bien si no se retiene accidentalmente en la cabecera de la secuencia ... – huynhjl

Se puede, pero no va a evaluar con pereza:

def bin(s: String, n: Int): Stream[String] = { 
    if (s.length == n) { 
    println("got " + s) // for figuring out when it's evaluated 
    Stream(s) 
    } else { 
    val s0 = s + '0' 
    val s1 = s + '1' 
    bin(s0, n) ++ bin(s1, n) 
    } 
}

Por ejemplo, al ejecutar bin("", 2).take(2).foreach(println), obtendrá el siguiente resultado:

scala> bin("", 2).take(2).foreach(println) 
got 00 
got 01 
got 10 
got 11 
00 
01

Si no le importa usando un TraversableView puede usar la conversión descrita aquí https://stackoverflow.com/a/3816012/257449. Con esto, el código se convierte en:

def toTraversable[T](func : (T => Unit) => Unit) = new Traversable[T] { 
    def foreach[X](f : T => X) = func(f(_) : Unit)      
} 

def bin2(str: String, n: Int) = { 
    def recurse[U](s: String, f: (String) => U) { 
    if (s.length == n) { 
     println("got " + s) // for figuring out when it's evaluated 
     f(s) 
    } else { 
     recurse(s + '0', f) 
     recurse(s + '1', f) 
    } 
    } 
    toTraversable[String](recurse(str, _)) view 
}

Entonces

scala> bin2("", 2).take(2).foreach(println) 
got 00 
00 
got 01 
01 
got 10

Fuente

2011-12-24 20:16:46 huynhjl

Un poco de scrounging ScalaDoc puede recorrer un largo camino ... :-) –

@ DanielC.Sobral, de hecho, nunca he usado o visto 'append' antes. – huynhjl

Cómo convertir el algoritmo de retroceso a la transmisión?

Respuesta

Cuestiones relacionadas