Xử lý chức năng luồng Scala mà không có lỗi OutOfMemory

Question

Có thể áp dụng lập trình hàm cho luồng Scala sao cho luồng được xử lý tuần tự, nhưng phần đã xử lý của luồng có thể được thu gom rác không?

Ví dụ, tôi xác định một Stream có chứa các số từ start để end:

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

Nếu tôi tổng hợp các giá trị trong một phong cách chức năng:

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

tôi nhận được một OutOfMemoryError - có lẽ vì ngăn xếp của cuộc gọi đến số reduceLeft giữ tham chiếu đến phần đầu của luồng. Nhưng nếu tôi làm điều này theo kiểu lặp lại, nó hoạt động:

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

Có cách nào để thực hiện điều này theo kiểu chức năng mà không nhận được OutOfMemory không?

CẬP NHẬT: Đây là a bug in scala hiện đã được sửa. Vì vậy, đây là nhiều hơn hoặc ít hơn trong ngày nay.

Answer 1

Có, bạn có thể. Bí quyết là sử dụng các phương thức đệ quy đuôi, để khung ngăn xếp cục bộ chứa tham chiếu duy nhất cho cá thể Stream. Vì phương pháp này là đệ quy đuôi, tham chiếu cục bộ cho đầu Stream trước đó sẽ bị xóa khi nó đệ quy gọi chính nó, do đó cho phép GC thu thập sự bắt đầu của số Stream khi bạn thực hiện.

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 

Ngoài ra, bạn phải đảm bảo rằng điều bạn chuyển đến phương thức last ở trên chỉ có một tham chiếu trên chồng. Nếu bạn lưu trữ Stream vào biến hoặc giá trị cục bộ, nó sẽ không được thu thập rác khi bạn gọi phương thức last, vì đối số của nó không phải là tham chiếu duy nhất còn lại đến Stream. Mã bên dưới hết bộ nhớ.

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) 

Để tóm tắt:

1. Sử dụng phương pháp đuôi-đệ quy
2. Chú thích chúng như đuôi-đệ quy
3. Khi bạn gọi cho họ, đảm bảo rằng lập luận của họ là tham khảo đến Stream

EDIT:

Lưu ý rằng điều này cũng làm việc và không dẫn đến một trong số lỗi bộ nhớ:

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

scala> last(s)                    
res1: Int = 99999999 

EDIT2:

Và trong trường hợp của reduceLeft mà bạn yêu cầu, bạn sẽ phải xác định một phương pháp helper với một tham số tích lũy cho kết quả.

Để giảmLeft, bạn cần một đối số tích lũy, mà bạn có thể đặt thành một giá trị nhất định bằng cách sử dụng đối số mặc định. Ví dụ đơn giản:

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

Bạn có thể muốn xem số ephemeral streams của Scalaz.

Answer 3

Khi tôi bắt đầu tìm hiểu về Stream Tôi nghĩ điều này thật tuyệt. Sau đó, tôi nhận ra Iterator là những gì tôi muốn sử dụng gần như mọi lúc.

Trong trường hợp bạn cần Stream nhưng muốn thực hiện reduceLeft công việc:

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

Nếu bạn cố gắng dòng ở trên, nó sẽ thu thập rác tốt. Tôi đã thấy rằng việc sử dụng Luồng rất khó khăn vì dễ dàng nắm giữ đầu mà không nhận ra. Đôi khi lib chuẩn sẽ giữ nó cho bạn - theo những cách rất tinh tế.

Answer 4

Khi nó xuất hiện, đây là a bug trong việc triển khai reduceLeft hiện tại. Vấn đề là reduceLeft gọi foldLeft, và do đó stackframe của reduceLeft giữ một tham chiếu đến phần đầu của luồng trong suốt toàn bộ cuộc gọi. foldLeft sử dụng đệ quy đuôi để tránh vấn đề này. So sánh:

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

Đây là tương đương ngữ nghĩa. Trong phiên bản Scala 2.8.0, lệnh gọi hàm foldLeft hoạt động, nhưng lời gọi hàm reduceLeft ném OutOfMemory. Nếu reduceLeft sẽ làm công việc riêng của mình, vấn đề này sẽ không xảy ra.