python - ¿Cuál es la forma preferida de implementar el ''rendimiento'' en Scala?

generator yield

Question

Estoy escribiendo código para la investigación de doctorado y estoy empezando a usar Scala. A menudo tengo que hacer el procesamiento de texto. Estoy acostumbrado a Python, cuya declaración de ''rendimiento'' es extremadamente útil para implementar iteradores complejos en archivos de texto grandes, a menudo de estructura irregular. Existen construcciones similares en otros idiomas (por ejemplo, C #), por una buena razón.

Sí, sé que ha habido hilos anteriores en esto. Pero parecen soluciones hackeadas (o al menos mal explicadas) que no funcionan claramente y que a menudo tienen limitaciones poco claras. Me gustaría escribir código algo como esto:

import generator._

def yield_values(file:String) = {
  generate {
    for (x <- Source.fromFile(file).getLines()) {
      # Scala is already using the ''yield'' keyword.
      give("something")
      for (field <- ":".r.split(x)) {
        if (field contains "/") {
          for (subfield <- "/".r.split(field)) { give(subfield) }
        } else {
          // Scala has no ''continue''.  IMO that should be considered
          // a bug in Scala.
          // Preferred: if (field.startsWith("#")) continue
          // Actual: Need to indent all following code
          if (!field.startsWith("#")) {
            val some_calculation = { ... do some more stuff here ... }
            if (some_calculation && field.startsWith("r")) {
              give("r")
              give(field.slice(1))
            } else {
              // Typically there will be a good deal more code here to handle different cases
              give(field)
            }
          }
        }
      }
    }
  }
}

Me gustaría ver el código que implementa generar () y give (). Por cierto, give () debe tener el nombre de rendimiento () pero Scala ya ha tomado esa palabra clave.

Supongo que, por razones que no entiendo, las continuaciones de Scala pueden no funcionar dentro de una declaración for. Si es así, genere () debería proporcionar una función equivalente que trabaje lo más cerca posible de una instrucción for, porque el código del iterador con un rendimiento casi inevitablemente se encuentra dentro de un bucle for.

Por favor, preferiría no obtener ninguna de las siguientes respuestas:

1. ''rendimiento'' apesta, las continuaciones son mejores. (Sí, en general, puede hacer más con continuaciones. Pero son muy difíciles de entender, y el 99% de las veces un iterador es todo lo que quiere o necesita. Si Scala ofrece muchas herramientas poderosas, pero son demasiado difíciles de usar En la práctica, el lenguaje no tendrá éxito.
2. Este es un duplicado. (Por favor vea mis comentarios arriba.)
3. Debería reescribir su código usando secuencias, continuaciones, recursiones, etc. etc. (Por favor vea el # 1. También agregaré, técnicamente, no necesita bucles tampoco. En realidad, técnicamente puede hacer absolutamente todo lo que necesita utilizando combinadores SKI .)
4. Tu función es demasiado larga. Divídalo en pedazos más pequeños y no necesitará "rendimiento". Tendrías que hacer esto en código de producción, de todos modos. (En primer lugar, "no necesitará" rendimiento "es dudoso. En segundo lugar, no es un código de producción. En tercer lugar, para el procesamiento de texto como este, muy a menudo, se rompe la función en partes más pequeñas, especialmente cuando el lenguaje te obliga a hacer esto porque carece de construcciones útiles, solo hace que el código sea más difícil de entender.)
5. Reescriba su código con una función pasada. (Técnicamente, sí, puede hacer esto. Pero el resultado ya no es un iterador, y encadenar iteradores es mucho más agradable que encadenar funciones. En general, un lenguaje no debería obligarme a escribir en un Estilo antinatural - ciertamente, los creadores de Scala creen esto en general, ya que proveen grandes cantidades de azúcar sintáctica.)
6. Reescriba su código en esto, aquello, o al revés, o alguna otra forma genial, impresionante que acabo de pensar.

Answer 1

''rendimiento'' apesta, las continuaciones son mejores

En realidad, el yield de Python es una continuación.

¿Qué es una continuación? Una continuación es guardar el punto actual de ejecución con todo su estado, de modo que uno pueda continuar en ese punto más adelante. Eso es precisamente el yield de Python y, también, cómo se implementa.

Sin embargo, tengo entendido que las continuaciones de Python no están delimitadas . No sé mucho sobre eso, podría estar equivocado, de hecho. Tampoco sé cuáles pueden ser las implicaciones de eso.

La continuación de Scala no funciona en tiempo de ejecución; de hecho, hay una biblioteca de continuaciones para Java que funciona haciendo cosas a bytecode en tiempo de ejecución, que está libre de las restricciones que tiene la continuación de Scala.

La continuación de Scala se realiza completamente en tiempo de compilación, lo que requiere bastante trabajo. También requiere que el compilador prepare el código que será "continuado" para hacerlo.

Y es por eso que las comprensiones no funcionan. Una declaración como esta:

for { x <- xs } proc(x)

Si traducido a

xs.foreach(x => proc(x))

Donde foreach es un método en la clase de xs . Desafortunadamente, la clase xs ha sido compilada durante mucho tiempo, por lo que no puede modificarse para que sea compatible con la continuación. Como nota al margen, también es por eso que Scala no tiene continue .

Aparte de eso, sí, esta es una pregunta duplicada y, sí, deberías encontrar una forma diferente de escribir tu código.

Answer 2

La implementación a continuación proporciona un generador tipo Python.

Observe que hay una función llamada _yield en el código a continuación, porque el yield ya es una palabra clave en Scala, que por cierto, no tiene nada que ver con el yield usted sabe de Python.

import scala.annotation.tailrec
import scala.collection.immutable.Stream
import scala.util.continuations._

object Generators {
  sealed trait Trampoline[+T]

  case object Done extends Trampoline[Nothing]
  case class Continue[T](result: T, next: Unit => Trampoline[T]) extends Trampoline[T]

  class Generator[T](var cont: Unit => Trampoline[T]) extends Iterator[T] {
    def next: T = {
      cont() match {
        case Continue(r, nextCont) => cont = nextCont; r
        case _ => sys.error("Generator exhausted")
      }
    }

    def hasNext = cont() != Done
  }

  type Gen[T] = cps[Trampoline[T]]

  def generator[T](body: => Unit @Gen[T]): Generator[T] = {
    new Generator((Unit) => reset { body; Done })
  }

  def _yield[T](t: T): Unit @Gen[T] =
    shift { (cont: Unit => Trampoline[T]) => Continue(t, cont) }
}


object TestCase {
  import Generators._

  def sectors = generator {
    def tailrec(seq: Seq[String]): Unit @Gen[String] = {
      if (!seq.isEmpty) {
        _yield(seq.head)
        tailrec(seq.tail)
      }
    }

    val list: Seq[String] = List("Financials", "Materials", "Technology", "Utilities")
    tailrec(list)
  }

  def main(args: Array[String]): Unit = {
    for (s <- sectors) { println(s) }
  }
}

Funciona bastante bien, incluso para el uso típico de bucles for.

Advertencia: debemos recordar que Python y Scala difieren en la forma en que se implementan las continuaciones. A continuación, vemos cómo los generadores se utilizan normalmente en Python y se comparan con la forma en que tenemos que usarlos en Scala. Luego, veremos por qué tiene que ser así en Scala.

Si estás acostumbrado a escribir código en Python, probablemente has usado generadores como este:

// This is Scala code that does not compile :(
// This code naively tries to mimic the way generators are used in Python

def myGenerator = generator {
  val list: Seq[String] = List("Financials", "Materials", "Technology", "Utilities")
  list foreach {s => _yield(s)}
}

Este código de arriba no se compila. Al omitir todos los aspectos teóricos complicados, la explicación es: no se compila porque "el tipo del bucle for" no coincide con el tipo involucrado como parte de la continuación. Me temo que esta explicación es un completo fracaso. Déjame intentar de nuevo:

Si hubieras codificado algo como el que se muestra a continuación, se compilaría bien:

def myGenerator = generator {
  _yield("Financials")
  _yield("Materials")
  _yield("Technology")
  _yield("Utilities")
}

Este código se compila porque el generador se puede descomponer en una secuencia de yield y, en este caso, un yield coincide con el tipo involucrado en la continuación. Para ser más precisos, el código se puede descomponer en bloques encadenados, donde cada bloque termina con un yield . Solo para aclarar, podemos pensar que la secuencia de yield s podría expresarse así:

{ some code here; _yield("Financials")
    { some other code here; _yield("Materials")
        { eventually even some more code here; _yield("Technology")
            { ok, fine, youve got the idea, right?; _yield("Utilities") }}}}

De nuevo, sin profundizar en la teoría complicada, el punto es que, después de un yield , debe proporcionar otro bloque que termine con un yield , o cerrar la cadena de otro modo. Esto es lo que estamos haciendo en el pseudocódigo anterior: después del yield , estamos abriendo otro bloque que a su vez termina con un yield seguido de otro yield que a su vez termina con otro yield , y así sucesivamente. Obviamente esto debe terminar en algún punto. Entonces lo único que podemos hacer es cerrar toda la cadena.

DE ACUERDO. Pero ... ¿cómo podemos yield múltiples piezas de información? La respuesta es un poco oscura pero tiene mucho sentido después de que conozca la respuesta: necesitamos emplear la recursión de la cola, y la última declaración de un bloque debe ser un yield .

  def myGenerator = generator {
    def tailrec(seq: Seq[String]): Unit @Gen[String] = {
      if (!seq.isEmpty) {
        _yield(seq.head)
        tailrec(seq.tail)
      }
    }

    val list = List("Financials", "Materials", "Technology", "Utilities")
    tailrec(list)
  }

Analicemos lo que está pasando aquí:

1. Nuestra función de generador myGenerator contiene alguna lógica que obtiene que genera información. En este ejemplo, simplemente utilizamos una secuencia de cadenas.

2. Nuestra función generadora myGenerator llama una función recursiva que es responsable de yield múltiples piezas de información, obtenida de nuestra secuencia de cadenas.

3. La función recursiva debe ser declarada antes de su uso , de lo contrario el compilador falla.

4. La función recursiva tailrec proporciona la recursión de la cola que necesitamos.

La regla de oro aquí es simple: sustituya un bucle for por una función recursiva, como se demostró anteriormente.

Observe que tailrec es solo un nombre conveniente que encontramos, por el bien de la aclaración. En particular, tailrec no necesita ser la última declaración de nuestra función de generador; no necesariamente. La única restricción es que debe proporcionar una secuencia de bloques que coincida con el tipo de yield , como se muestra a continuación:

  def myGenerator = generator {

    def tailrec(seq: Seq[String]): Unit @Gen[String] = {
      if (!seq.isEmpty) {
        _yield(seq.head)
        tailrec(seq.tail)
      }
    }

    _yield("Before the first call")
    _yield("OK... not yet...")
    _yield("Ready... steady... go")

    val list = List("Financials", "Materials", "Technology", "Utilities")
    tailrec(list)

    _yield("done")
    _yield("long life and prosperity")
  }

Un paso más allá, debe imaginarse cómo se ven las aplicaciones de la vida real, en particular si está empleando varios generadores. Sería una buena idea si encuentra una manera de estandarizar sus generadores en torno a un solo patrón que demuestre ser conveniente para la mayoría de las circunstancias.

Examinemos el siguiente ejemplo. Tenemos tres generadores: sectors , industries y companies . Por brevedad, solo se muestran los sectors completamente. Este generador emplea una función tailrec como se demostró anteriormente. El truco aquí es que la misma función tailrec también es empleada por otros generadores. Todo lo que tenemos que hacer es proporcionar una función body diferente.

type GenP = (NodeSeq, NodeSeq, NodeSeq)
type GenR = immutable.Map[String, String]

def tailrec(p: GenP)(body: GenP => GenR): Unit @Gen[GenR] = {
  val (stats, rows, header)  = p
  if (!stats.isEmpty && !rows.isEmpty) {
    val heads: GenP = (stats.head, rows.head, header)
    val tails: GenP = (stats.tail, rows.tail, header)
    _yield(body(heads))
    // tail recursion
    tailrec(tails)(body)
  }
}

def sectors = generator[GenR] {
  def body(p: GenP): GenR = {
      // unpack arguments
      val stat, row, header = p
      // obtain name and url
      val name = (row / "a").text
      val url  = (row / "a" / "@href").text
      // create map and populate fields: name and url
      var m = new scala.collection.mutable.HashMap[String, String]
      m.put("name", name)
      m.put("url",  url)
      // populate other fields
      (header, stat).zipped.foreach { (k, v) => m.put(k.text, v.text) }
      // returns a map
      m
  }

  val root  : scala.xml.NodeSeq = cache.loadHTML5(urlSectors) // obtain entire page
  val header: scala.xml.NodeSeq = ... // code is omitted
  val stats : scala.xml.NodeSeq = ... // code is omitted
  val rows  : scala.xml.NodeSeq = ... // code is omitted
  // tail recursion
  tailrec((stats, rows, header))(body)
} 

def industries(sector: String) = generator[GenR] {
  def body(p: GenP): GenR = {
      //++ similar to ''body'' demonstrated in "sectors"
      // returns a map
      m
  }

  //++ obtain NodeSeq variables, like demonstrated in "sectors" 
  // tail recursion
  tailrec((stats, rows, header))(body)
} 

def companies(sector: String) = generator[GenR] {
  def body(p: GenP): GenR = {
      //++ similar to ''body'' demonstrated in "sectors"
      // returns a map
      m
  }

  //++ obtain NodeSeq variables, like demonstrated in "sectors" 
  // tail recursion
  tailrec((stats, rows, header))(body)
} 

• Créditos a Rich Dougherty y huynhjl.
  Vea este subproceso SO: Implementando el rendimiento (rendimiento) usando las continuaciones de Scala *

• Créditos a Miles Sabin, por poner algunos de los códigos anteriores juntos
  http://github.com/milessabin/scala-cont-jvm-coro-talk/blob/master/src/continuations/Generators.scala

Answer 3

La premisa de tu pregunta parece ser que quieres exactamente el rendimiento de Python, y no quieres ninguna otra sugerencia razonable para hacer lo mismo de una manera diferente en Scala. Si esto es cierto y es tan importante para ti, ¿por qué no usar Python? Es un lenguaje bastante bueno. A menos que su Ph.D. está en informática y usar Scala es una parte importante de su disertación, si ya está familiarizado con Python y realmente le gustan algunas de sus características y opciones de diseño, ¿por qué no usarlo?

De todos modos, si realmente quieres aprender cómo resolver tu problema en Scala, resulta que para el código que tienes, las continuaciones delimitadas son excesivas. Todo lo que necesitas son iteradores planos.

Así es como lo haces.

// You want to write
for (x <- xs) { /* complex yield in here */ }
// Instead you write
xs.iterator.flatMap { /* Produce iterators in here */ }

// You want to write
yield(a)
yield(b)
// Instead you write
Iterator(a,b)

// You want to write
yield(a)
/* complex set of yields in here */
// Instead you write
Iterator(a) ++ /* produce complex iterator here */

¡Eso es! Todos sus casos pueden reducirse a uno de estos tres.

En tu caso, tu ejemplo se vería como

Source.fromFile(file).getLines().flatMap(x =>
  Iterator("something") ++
  ":".r.split(x).iterator.flatMap(field =>
    if (field contains "/") "/".r.split(field).iterator
    else {
      if (!field.startsWith("#")) {
        /* vals, whatever */
        if (some_calculation && field.startsWith("r")) Iterator("r",field.slice(1))
        else Iterator(field)
      }
      else Iterator.empty
    }
  )
)

PS Scala tiene continuar; se hace así (implementado lanzando excepciones sin apilamiento (peso ligero)):

import scala.util.control.Breaks._
for (blah) { breakable { ... break ... } }

pero eso no te dará lo que quieres porque Scala no tiene el rendimiento que deseas.