14

在编写对Stream(s) 进行操作的函数时，有不同的递归概念。第一个简单的意义在编译器级别上不是递归的，因为如果没有立即评估尾部，那么函数会立即返回，但返回的流是递归的：

final def simpleRec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else someB(a.head) #:: simpleRec(a.tail)

上述递归概念不会引起任何问题。第二个在编译器级别上是真正的尾递归：

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              // A) degenerated
  else if (someCond) rec(a.tail)           // B) tail recursion
  else someB(a.head) #:: rec(a.tail)       // C) degenerated

这里的问题是C)编译器将这种情况检测为非tailrec调用，即使没有执行实际调用。这可以通过将流尾分解为辅助函数来避免：

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else if (someCond) rec(a.tail)          // B)
  else someB(a.head) #:: recHelp(a.tail)  

@tailrec
final def recHelp[A](as: Stream[A]): Stream[B] = 
  rec(as)

在编译时，这种方法最终会导致内存泄漏。由于尾递归rec最终是从recHelp函数中调用的，因此函数的堆栈帧recHelp持有对蒸汽头的引用，并且在调用返回之前不会让流被垃圾收集rec，这可能会很长（就递归步骤）取决于对B).

请注意，即使在无帮助的情况下，如果编译器允许 @tailrec，内存泄漏可能仍然存在，因为惰性流尾实际上会创建一个匿名对象，该对象持有对流头的引用。

4

2 回答 2

3

一种可能的解决方法是使该recHelp方法不保留对流头的引用。这可以通过将包装的流传递给它并改变包装器以从中删除引用来实现：

@tailrec
final def rec[A](as: Stream[A]): Stream[B] = 
  if (a.isEmpty) Stream.empty              
  else if (someCond) rec(a.tail)          
  else {
    // don't inline and don't define as def,
    // or anonymous lazy wrapper object would hold reference
    val tailRef = new AtomicReference(a.tail)
    someB(a.head) #:: recHelp(tailRef)  
  }

@tailrec
final def recHelp[A](asRef: AtomicReference[Stream[A]]): Stream[B] = 
  // Note: don't put the content of the holder into a local variable
  rec(asRef.getAndSet(null))

这AtomicReference只是方便，在这种情况下不需要原子性，任何简单的持有者对象都可以。

另请注意，由于recHelp被包装在流Cons尾中，因此它只会被评估一次，并且Cons还负责同步。

于 2012-09-21T11:32:34.907 回答
2

正如您所暗示的，问题在于您粘贴的代码中 filterHelp 函数保留了头部（因此您的解决方案将其删除）。

最好的答案是简单地避免这种令人惊讶的行为，使用 Scalaz EphemeralStream 并看到它既不是 oom 又运行得更快，因为它对 gc 更好。使用它并不总是那么简单，例如 head 是 () => A 而不是 A，没有提取器等，但它都面向一个目标、可靠的流使用。

您的 filterHelper 函数通常不必关心它是否保留引用：

import scalaz.EphemeralStream

@scala.annotation.tailrec
def filter[A](s: EphemeralStream[A], f: A => Boolean): EphemeralStream[A] = 
  if (s.isEmpty) 
    s
  else
    if (f(s.head())) 
      EphemeralStream.cons(s.head(), filterHelp(s.tail() , f) )
    else
      filter(s.tail(), f)

def filterHelp[A](s: EphemeralStream[A], f: A => Boolean) =
  filter(s, f)

def s1 = EphemeralStream.range(1, big)

我什至要说，除非您有令人信服的理由使用 Stream（其他库依赖项等）然后坚持使用 EphemeralStream，否则那里的惊喜要少得多。

于 2012-09-29T10:41:57.053 回答