Scala中Fibonacci流中的OutOfMemoryError

Question

当我这样定义时fib(1):

def fib(n: Int) = {
  lazy val fibs: Stream[BigInt] = 0 #:: 1 #:: fibs.zip(fibs.tail).map{n => n._1 + n._2}
  fibs.drop(n).head
}

我收到一个错误:

scala> fib(1000000)
java.lang.OutOfMemoryError: Java heap space

另一方面,这很好(2):

def fib = {
  lazy val fibs: Stream[BigInt] = 0 #:: 1 #:: fibs.zip(fibs.tail).map{n => n._1 + n._2}
  fibs
}

scala> fib.drop(1000000).head
res17: BigInt = 195328212...

此外,如果我按以下方式更改流定义,我可以drop(n).head在函数内调用,也不会得到任何错误(3):

def fib(n: Int) = {
  lazy val fibs: (BigInt, BigInt) => Stream[BigInt] = (a, b) => a #:: fibs(b, a+b)
  fibs(0, 1).drop(n).head
}

scala> fib(1000000)
res18: BigInt = 195328212...

你能解释(1),(2)和(3)之间的相关差异吗？为什么(2)工作,而(1)不工作？为什么我们不需要drop(n).head退出(3)中的功能？

Answer 1

在第一种情况下,fibs当n计算元素数时,存在对流的开始的引用- 因此,必须将所有0到1000000的值保存在存储器中.这是源头OutOfMemoryError.

在第二种情况下,对流的开头的引用不会保留在任何地方,因此可以对项进行垃圾回收(一次只有一个项必须保留在内存中).

在第三种情况下,对流的开始的引用在任何地方都不显式存在(它可以在删除下一个值时进行垃圾收集).但是,如果我们将其更改为:

def fib(n: Int) = {
  lazy val fibs: (BigInt, BigInt) => Stream[BigInt] = (a, b) => a #:: fibs(b, a+b)
  val beg = fibs(0, 1)
  beg.drop(n).head
}

然后OutOfMemoryError会再次发生.