scala - cerebral - neuroplasticidad

Procesamiento funcional de flujos Scala sin errores OutOfMemory

Question

¿Es posible aplicar la programación funcional a las secuencias de Scala de modo que la secuencia se procese secuencialmente, pero la parte ya procesada de la secuencia se pueda recolectar como basura?

Por ejemplo, defino una Stream que contiene los números de start a end :

def fromToStream(start: Int, end: Int) : Stream[Int] = {
  if (end < start) Stream.empty
  else start #:: fromToStream(start+1, end)
}

Si sumo los valores en un estilo funcional:

println(fromToStream(1,10000000).reduceLeft(_+_))

Obtengo un OutOfMemoryError , tal vez porque el cuadro de la pila de la llamada a reduceLeft contiene una referencia a la cabecera de la secuencia. Pero si hago esto en estilo iterativo, funciona:

var sum = 0
for (i <- fromToStream(1,10000000)) {
  sum += i
}

¿Hay una manera de hacer esto en un estilo funcional sin obtener un OutOfMemory ?

ACTUALIZACIÓN : Este fue un error en Scala que se corrige ahora. Así que esto está más o menos desactualizado ahora.

Answer 1

Como resultado, este es un error en la implementación actual de reduceLeft. El problema es que reduceLeft call foldLeft y, por lo tanto, el cuadro de pila de reduceLeft contiene una referencia a la cabecera de la secuencia durante toda la llamada. foldLeft usa la recursión de cola para evitar este problema. Comparar:

(1 to 10000000).toStream.foldLeft(0)(_+_)
(1 to 10000000).toStream.reduceLeft(_+_)

Estos son semánticamente equivalentes. En la versión 2.8.0 de Scala, la llamada a foldLeft funciona, pero la llamada a reduceLeft lanza un OutOfMemory. Si reduceLeft haría su propio trabajo, este problema no se produciría.

Answer 2

Cuando empecé a aprender sobre Stream , pensé que esto era genial. Entonces me di cuenta de que Iterator es lo que quiero usar casi todo el tiempo.

En caso de que necesite Stream pero quiera hacer reduceLeft trabajo:

fromToStream(1,10000000).toIterator.reduceLeft(_ + _)

Si intentas la línea de arriba, la recolección de basura está bien. Descubrí que usar Stream es complicado, ya que es fácil agarrarse a la cabeza sin darse cuenta. A veces, la biblioteca estándar lo conservará para usted, de manera muy sutil.

Answer 3

Es posible que desee ver corrientes efímeras de Scalaz.

Answer 4

Sí tu puedes. El truco consiste en utilizar métodos recursivos de cola, de modo que el marco de pila local contenga la única referencia a la instancia de Stream . Dado que el método es de cola recursiva, la referencia local al encabezado de Stream anterior se borrará una vez que se llame a sí misma recursivamente, lo que permitirá al GC recopilar el inicio de Stream medida que avanza.

Welcome to Scala version 2.9.0.r23459-b20101108091606 (Java HotSpot(TM) Server VM, Java 1.6.0_20).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import collection.immutable.Stream
import collection.immutable.Stream

scala> import annotation.tailrec
import annotation.tailrec

scala> @tailrec def last(s: Stream[Int]): Int = if (s.tail.isEmpty) s.head else last(s.tail)
last: (s: scala.collection.immutable.Stream[Int])Int

scala> last(Stream.range(0, 100000000))                                                                             
res2: Int = 99999999

Además, debe asegurarse de que lo que pase al método anterior tenga solo una referencia en la pila. Si almacena un Stream en una variable o valor local, no se recogerá la basura cuando llame al last método, ya que su argumento no es la única referencia que queda de Stream . El código de abajo se queda sin memoria.

scala> val s = Stream.range(0, 100000000)                                                                           
s: scala.collection.immutable.Stream[Int] = Stream(0, ?)                                                            

scala> last(s)                                                                                                      
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space                                              
        at sun.net.www.ParseUtil.encodePath(ParseUtil.java:84)                                                      
        at sun.misc.URLClassPath$JarLoader.checkResource(URLClassPath.java:674)                                     
        at sun.misc.URLClassPath$JarLoader.getResource(URLClassPath.java:759)                                       
        at sun.misc.URLClassPath.getResource(URLClassPath.java:169)                                                 
        at java.net.URLClassLoader$1.run(URLClassLoader.java:194)                                                   
        at java.security.AccessController.doPrivileged(Native Method)                                               
        at java.net.URLClassLoader.findClass(URLClassLoader.java:190)                                               
        at java.lang.ClassLoader.loadClass(ClassLoader.java:307)                                                    
        at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:301)                                            
        at java.lang.ClassLoader.loadClass(ClassLoader.java:248)                                                    
        at scala.tools.nsc.Interpreter$Request$$anonfun$onErr$1$1.apply(Interpreter.scala:978)                      
        at scala.tools.nsc.Interpreter$Request$$anonfun$onErr$1$1.apply(Interpreter.scala:976)                      
        at scala.util.control.Exception$Catch.apply(Exception.scala:80)
        at scala.tools.nsc.Interpreter$Request.loadAndRun(Interpreter.scala:984)                                    
        at scala.tools.nsc.Interpreter.loadAndRunReq$1(Interpreter.scala:579)                                       
        at scala.tools.nsc.Interpreter.interpret(Interpreter.scala:599)                                             
        at scala.tools.nsc.Interpreter.interpret(Interpreter.scala:576)
        at scala.tools.nsc.InterpreterLoop.reallyInterpret$1(InterpreterLoop.scala:472)                             
        at scala.tools.nsc.InterpreterLoop.interpretStartingWith(InterpreterLoop.scala:515)                         
        at scala.tools.nsc.InterpreterLoop.command(InterpreterLoop.scala:362)
        at scala.tools.nsc.InterpreterLoop.processLine$1(InterpreterLoop.scala:243)
        at scala.tools.nsc.InterpreterLoop.repl(InterpreterLoop.scala:249)
        at scala.tools.nsc.InterpreterLoop.main(InterpreterLoop.scala:559)
        at scala.tools.nsc.MainGenericRunner$.process(MainGenericRunner.scala:75)
        at scala.tools.nsc.MainGenericRunner$.main(MainGenericRunner.scala:31)
        at scala.tools.nsc.MainGenericRunner.main(MainGenericRunner.scala)

Para resumir:

1. Utilizar métodos de cola recursiva.
2. Anótalos como cola recursiva.
3. Cuando los llame, asegúrese de que su argumento sea la única referencia al Stream

EDITAR:

Tenga en cuenta que esto también funciona y no produce un error de falta de memoria:

scala> def s = Stream.range(0, 100000000)                                                   
s: scala.collection.immutable.Stream[Int]

scala> last(s)                                                                              
res1: Int = 99999999

EDIT2:

Y en el caso de reduceLeft que necesite, tendría que definir un método auxiliar con un argumento acumulador para el resultado.

Para reducirLeft, necesita un argumento de acumulador, que puede establecer en un valor determinado utilizando argumentos predeterminados. Un ejemplo simplificado:

scala> @tailrec def rcl(s: Stream[Int], acc: Int = 0): Int = if (s.isEmpty) acc else rcl(s.tail, acc + s.head)
rcl: (s: scala.collection.immutable.Stream[Int],acc: Int)Int

scala> rcl(Stream.range(0, 10000000))
res6: Int = -2014260032