我能够编写流处理函数drop(n,s)
,它可以扩展到非常大的流。但是当我写另一个函数nth(n,s)
,它需要一个流s
并将它转发到drop(n,s)
时,似乎nth()
“保持在流的头部”。这导致OutOfMemoryError
为大n
。
这是代码:
import scala.annotation.tailrec
import scala.collection.immutable.Stream.cons
object Streams {
def iterate[A](start: A, f: A => A): Stream[A] =
cons(start, iterate(f(start), f))
def inc(n:Int) = n + 1
def naturals() =
iterate(1, inc)
@tailrec def drop[T](n : Int, s : Stream[T]) : Stream[T] =
if (n <= 0 || s.isEmpty) s
else drop(n-1, s.tail)
// @inline didn't seem to help
def nth[T](n : Int, s : Stream[T]) =
drop(n,s).head
def N = 1e7.toInt
def main(args: Array[String]) {
println(drop(N,naturals()).head) // works fine for large N
println(nth(N, naturals())) // results in OutOfMemoryError for N set to 1e7.toInt and -Xmx10m
}
}
我对这个Java问题的经验:why does this Java method leak—and why does inlining it fix the leak?让我相信,在调用nth()
之前,scala生成的s
代码在清除drop()
方面没有足够的积极性。 Clojure库技巧(Java技巧)(参见链接问题)在这里不起作用,因为所有Scala函数参数都是val
s(而不是var
s),因此无法分配它们(null
)。
如何根据nth()
编写可扩展的drop()
?
这是2009-2011相关的Scala编译器错误(reduceLeft()
实现的foldLeft()
):https://issues.scala-lang.org/browse/SI-2239
我无法从Scala bug票中看出,他们是如何修复它的。在票证中有一个建议,解决它的唯一方法是复制foldLeft()
中的reduceLeft()
代码。我真的希望这不是答案。
更新:Andrey Tyukin的回答https://stackoverflow.com/a/52209383/156550解决了这个问题。我现在有:
// have to call by name (s) here, otherwise we hold on to head!
def nth[T](n : Int, s : => Stream[T]) =
drop(n,s).head
并且nth(n,s)
很好。
这是一个快速而又脏的解决方案,只需要两个额外的字符:
def nth[T](n : Int, s: => Stream[T]) = drop(n,s).head
以下是没有=>
的情况:
s
作为参数传递给nth
时,它是对先前由naturals()
创建的已存在值的引用。.head
,drop(n, s)
必须将流返回到nth
的堆栈框架,因此nth
的堆栈框架不能被丢弃,因此nth
保持参考s
。s
的引用是由nth
的堆栈框架保存而drop
正在工作时,所有丢弃的前缀实际上都不能被垃圾收集(这是因为Stream
保证如果你保持头部并多次迭代它,它将返回相同的结果)。现在,如果你添加=>
,那么会发生以下情况:
nth
,.head
的堆栈框架仍然不能被丢弃nth
没有提到传递给drop
的溪流的头部。它仅包含对产生Stream
的thunk的引用。附加说明(迪马的测试案例):
请注意,如果thunk本身只返回对已存在的Stream
的引用,那么行为仍然与没有=>
的行为相同。例如,如果您的inc
定义如下:
def inc(i: Int): Int = {
println(System.currentTimeMillis())
i + 1
}
然后调用
val s = naturals()
nth(10, s)
nth(5, s)
将打印当前时间仅十次(而不是15次)。