OutOfMemory hataları olmadan Scala akışlarının işlevsel işlenmesi

Question

Akım sıralı olarak işlenecek şekilde, Scala akışlarına işlevsel programlama uygulamak mümkün mü, ancak akışın zaten işlenmiş kısmı çöp toplanabilir mi?

Mesela ben end için start numaraları içeren bir Stream tanımlayın:

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

Ben işlevsel bir tarzda değerleri Özetle edin:

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

alıyorum bir OutOfMemoryError - Belki de reduceLeft numaralı aramanın stackframe'i, akışın başına bir referansa sahip olduğundan. Ben iteratif bir tarzda bunu Ama eğer çalışır: Bir OutOfMemory almadan fonksiyonel bir tarzda bunu yapmanın bir yolu

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

var mı?

UPDATE: Bu, şu anda giderilen a bug in scala idi. Yani bu şimdi daha az veya çok güncel.

Answer 1

Evet, yapabilirsiniz. Hile kuyruk özyinelemeli yöntemleri kullanmaktır, böylece yerel yığın çerçevesi Stream örneğine yalnızca başvuru içerir. Metod, kuyruk özyinelemeli olduğundan, bir önceki Stream kafasına yapılan yerel referans, özyinelemeli olarak kendisini çağırana dek silinir ve böylece GC'nin, Stream'un başlangıcını başlatmasını sağlar.

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 

Ayrıca, yönteme last geçirmek şey yığın üzerinde sadece tek bir referans vardır sağlamalıdır. Stream yerel bir değişken veya değere depolarsanız, last yöntemini çağırdığınızda, Stream'a kalan tek başvuru olmadığı için çöp toplanmaz. Aşağıdaki kod bellek bitti.

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) 

Özetlemek gerekirse:

olarak ek açıklama

1. Kullanım kuyruk özyinelemeli yöntemler kuyruk özyinelemeli
2. onları aradığınızda, onların argüman Stream
için tek referans olmasını sağlamak

DÜZENLEME:

Bu da çalışır ve bu

Not bellek hatası dışı bir yol açmaz:

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

scala> last(s)                    
res1: Int = 99999999 

EDIT2:

Ve gerektiren reduceLeft durumunda

, bir yardımcı yöntemini tanımlamak zorunda kalacak Sonuç için bir akümülatör argümanı ile.

reduceLeft için, varsayılan argümanları kullanarak belirli bir değere ayarlayabileceğiniz bir akümülatör argümanına ihtiyacınız vardır. Bir basitleştirilmiş bir örnek: Sonradan anlaşıldı ki

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 

Answer 2

Scalaz ephemeral streams'a bakmak isteyebilirsiniz.

Answer 3

Stream'u öğrenmeye başladığımda bunun harika olduğunu düşündüm. Sonra neredeyse her zaman kullanmak istediğimi Iterator fark ettim. durumda

Eğer Stream gerekiyor ama reduceLeft işi yapmak istiyorum: Yukarıdaki satır çalışırsanız

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

, çöp gayet toplayacaktır. Akışı kullanmanın, fark etmeden kafasına tutması kolay olduğu için çok zor olduğunu anladım. Bazen standart lib, sizin için - çok ince yollarla - sizin için tutacaktır.

Answer 4

, bu reduceLeft mevcut uygulamasında a bug olduğunu. Problem, lowerLeft'in foldLeft olarak adlandırılmasıdır ve bu nedenle, lowLeft'in stackframe'i, tüm çağrı sırasında akımın başlığına bir referans tutmaktadır. foldLeft, bu sorunu önlemek için kuyruk geri çekmeyi kullanır. Karşılaştırma:

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

Bunlar semantik olarak eşdeğerdir. Scala sürüm 2.8.0'da foldLeft çağrısı çalışır, ancak azaltma çağrısı bir OutOfMemory atar. ReduceLeft kendi işini yaparsa, bu sorun oluşmaz.