代码之家 › 专栏 › 技术社区 › Dr. Hans-Peter Störr

无内存不足错误的scala流的功能处理

functional-programming scala

Dr. Hans-Peter Störr · 技术社区 · 14 年前

是否可以将函数编程应用于scala流,以便按顺序处理流,但流中已处理的部分可以被垃圾收集?

例如,我定义了 Stream 包含的数字来自 start 到 end :

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

如果我以函数样式总结这些值:

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

我得到了一个 OutOfMemoryError -可能是因为stackframe的调用 reduceLeft 保存对流头的引用。但是如果我用迭代的方式来做,它会工作:

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

有没有一种方法可以在不使用 OutOfMemory ?

更新这是 a bug in scala 现在就修好了。所以这或多或少已经过时了。

4 回复 | 直到 8 年前

axel22 13 年前

是的,你可以。诀窍是使用尾部递归方法,以便本地堆栈帧只包含对 Stream 实例。由于该方法是尾递归的,因此对前一个方法的本地引用 河流 一旦头递归地调用自身,它将被擦除,从而使GC能够收集 河流 随你去。

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

此外,必须确保传递给方法的内容 last 上面只有一个关于堆栈的引用。如果你存储了 河流 在本地变量或值中,当调用 最后的 方法,因为它的参数不是 河流 . 下面的代码内存不足。

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)

总结:

使用尾部递归方法
将它们注释为尾部递归
当您调用它们时,请确保它们的参数是对 河流

编辑:

请注意,这同样有效,不会导致内存不足错误:

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

scala> last(s)                                                                              
res1: Int = 99999999

编辑2:

~~如果是 reduceLeft 如果需要,则必须使用结果的accumulator参数定义一个helper方法。~~

对于reduceCleft,需要一个accumulator参数,可以使用默认参数将其设置为某个值。一个简单的例子:

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

huynhjl bhericher 14 年前

当我开始了解 Stream 我觉得这很酷。然后我意识到 Iterator 是我几乎一直想要使用的。

万一你真的需要 河流 但是想做 reduceLeft 工作:

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

如果你试试上面的那一行,它会很好地收集垃圾。我发现使用流是很难的,因为它很容易抓住头部而不意识到它。有时标准库会以非常微妙的方式为您保留它。

Alexey Romanov 14 年前

你可能想看看斯卡拉兹的 ephemeral streams .

Dr. Hans-Peter Störr 14 年前

事实证明,这是 a bug 在目前实施的裁员。问题是ReduceCeleft调用foldLeft,因此ReduceCeleft的stackFrame在整个调用过程中保持对流头的引用。foldleft使用tail递归来避免这个问题。比较:

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

它们在语义上是等价的。在scala版本2.8.0中,对foldLeft的调用可以工作,但是对reduceCleft的调用抛出了一个内存不足的地方。如果减速器能自己工作,这个问题就不会发生。