14

（s）で動作する関数を作成する場合Stream、再帰の概念は異なります。最初の単純な意味は、コンパイラレベルでは再帰的ではありません。テールが即座に評価されない場合、関数はすぐに返されますが、返されるストリームは再帰的です。

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

上記の再帰の概念は問題を引き起こしません。2つ目は、コンパイラレベルで本当に末尾再帰です。

@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を使用して、gcにはるかに優れているため、動作が悪くなく、実行速度が大幅に向上することを確認することです。たとえば、headの操作は必ずしも簡単ではありませんが、（）=> AではなくAではなく、エクストラクタなどはありませんが、すべてが1つの目的の信頼できるストリームの使用に合わせて調整されています。

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 に答える