函数转发Stream参数到另一个函数保留引用

问题描述 投票:2回答:1

我能够编写流处理函数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函数参数都是vals(而不是vars),因此无法分配它们(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)很好。

scala memory-management clojure garbage-collection sequence
1个回答
2
投票

这是一个快速而又脏的解决方案,只需要两个额外的字符:

def nth[T](n : Int, s: => Stream[T]) = drop(n,s).head

以下是没有=>的情况:

  • 当流s作为参数传递给nth时,它是对先前由naturals()创建的已存在值的引用。
  • 由于.headdrop(n, s)必须将流返回到nth的堆栈框架,因此nth的堆栈框架不能被丢弃,因此nth保持参考s
  • 因为参数s的引用是由nth的堆栈框架保存而drop正在工作时,所有丢弃的前缀实际上都不能被垃圾收集(这是因为Stream保证如果你保持头部并多次迭代它,它将返回相同的结果)。

现在,如果你添加=>,那么会发生以下情况:

  • 由于nth.head的堆栈框架仍然不能被丢弃
  • 但是:nth没有提到传递给drop的溪流的头部。它仅包含对产生Stream的thunk的引用。
  • thunk本身不占用任何大量内存,并且它不保存对创建的流的头部的任何引用,因此,流的前缀可以被垃圾收集。

附加说明(迪马的测试案例):

请注意,如果thunk本身只返回对已存在的Stream的引用,那么行为仍然与没有=>的行为相同。例如,如果您的inc定义如下:

def inc(i: Int): Int = {
  println(System.currentTimeMillis())
  i + 1
}

然后调用

val s = naturals()
nth(10, s)
nth(5, s)

将打印当前时间仅十次(而不是15次)。

© www.soinside.com 2019 - 2024. All rights reserved.