10

次のブログ記事は、F# でfoldBack継続渡しスタイルを使用して末尾再帰を行う方法を示しています。

Scala では、これは次のことを意味します。

def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
  l match {
    case x :: xs => f(x, foldBack(xs, acc)(f))
    case Nil => acc
  }
}

これを行うことで末尾再帰にすることができます：

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    l match {
      case x :: xs => loop(xs, (racc => k(f(x, racc))))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
}

残念ながら、長いリストではまだスタック オーバーフローが発生します。loop は末尾再帰的で最適化されていますが、スタックの蓄積は継続呼び出しに移動しただけだと思います。

これが F# の問題ではないのはなぜですか? Scalaでこれを回避する方法はありますか?

編集：スタックの深さを示すいくつかのコード：

def showDepth(s: Any) {
  println(s.toString + ": " + (new Exception).getStackTrace.size)
}

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    showDepth("loop")
    l match {
      case x :: xs => loop(xs, (racc => { showDepth("k"); k(f(x, racc)) }))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
} 

foldCont(List.fill(10)(1), 0)(_ + _)

これは以下を出力します:

loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
k: 51
k: 52
k: 53
k: 54
k: 55
k: 56
k: 57
k: 58
k: 59
k: 60
res2: Int = 10
4

4 に答える 4

6

ジョン、nm、答えてくれてありがとう。あなたのコメントに基づいて、トランポリンを試してみようと思いました。ちょっとした調査によると、Scala は .NET でトランポリンのライブラリをサポートしていTailCallsます。少しいじった後、私が思いついたのは次のとおりです。

def foldContTC[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  import scala.util.control.TailCalls._
  @annotation.tailrec
  def loop(l: List[T], k: (U) => TailRec[U]): TailRec[U] = {
    l match {
      case x :: xs => loop(xs, (racc => tailcall(k(f(x, racc)))))
      case Nil => k(acc)
    }
  }
  loop(list, u => done(u)).result
}

foldLeftこれが、トランポリンやデフォルトおよびfoldRight実装のないソリューションとどのように比較されるかに興味がありました。ベンチマーク コードといくつかの結果を次に示します。

val size = 1000
val list = List.fill(size)(1)
val warm = 10
val n = 1000
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldCont", warm, lots(n, foldCont(list, 0)(_ + _)))
bench("foldRight", warm, lots(n, list.foldRight(0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))

タイミングは次のとおりです。

foldContTC: warming...
Elapsed: 0.094
foldCont: warming...
Elapsed: 0.060
foldRight: warming...
Elapsed: 0.160
foldLeft: warming...
Elapsed: 0.076
foldLeft.reverse: warming...
Elapsed: 0.155

これに基づくと、トランポリンは実際にはかなりのパフォーマンスを発揮しているように思われます。ボックス化/ボックス化解除に加えてのペナルティは、それほど悪くないと思います。

編集: Jon のコメントで示唆されているように、リストが大きくなるとパフォーマンスが低下することを確認する 1M アイテムのタイミングを次に示します。また、ライブラリ List.foldLeft の実装がオーバーライドされていないことがわかったので、次の foldLeft2 で時間を計りました。

def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  list match {
    case x :: xs => foldLeft2(xs, f(x, acc))(f)
    case Nil => acc
  }
} 

val size = 1000000
val list = List.fill(size)(1)
val warm = 10
val n = 2
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft2", warm, lots(n, foldLeft2(list, 0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))
bench("foldLeft2.reverse", warm, lots(n, foldLeft2(list.reverse, 0)(_ + _)))

収量:

foldContTC: warming...
Elapsed: 0.801
foldLeft: warming...
Elapsed: 0.156
foldLeft2: warming...
Elapsed: 0.054
foldLeft.reverse: warming...
Elapsed: 0.808
foldLeft2.reverse: warming...
Elapsed: 0.221

したがって、foldLeft2.reverse が勝者です...

于 2011-12-18T20:36:34.427 に答える
4

問題は継続機能(racc => k(f(x, racc)))そのものです。このビジネス全体が機能するように最適化されている必要がありますが、そうではありません。

Scala は任意の末尾呼び出しに対して末尾呼び出しの最適化を行うことはできず、ループに変換できるもの (つまり、関数が他の関数ではなく、それ自体を呼び出す場合) に対してのみ最適化を行うことができます。

于 2011-12-18T04:34:06.187 に答える
3

この質問には遅れましたが、完全なトランポリンを使用せずに末尾再帰 FoldRight を作成する方法を示したかったのです。継続のリストを蓄積し (終了時に相互に呼び出してスタック オーバーフローを引き起こす代わりに)、最後にそれらを折りたたむことにより、スタックを保持するようなものですが、ヒープ上に:

object FoldRight {

  def apply[A, B](list: Seq[A])(init: B)(f: (A, B) => B): B = {
    @scala.annotation.tailrec
    def step(current: Seq[A], conts: List[B => B]): B = current match {
      case Seq(last) => conts.foldLeft(f(last, init)) { (acc, next) => next(acc) }
      case Seq(x, xs @ _*) => step(xs, { acc: B => f(x, acc) } +: conts)
      case Nil => init
    }
    step(list, Nil)
  }

}

最後に行われる折り畳みは、それ自体が末尾再帰です。ScalaFiddle で試してみる

パフォーマンスの面では、テール コール バージョンよりもわずかにパフォーマンスが低下します。

[info] Benchmark            (length)  Mode  Cnt   Score    Error  Units
[info] FoldRight.conts           100  avgt   30   0.003 ±  0.001  ms/op
[info] FoldRight.conts         10000  avgt   30   0.197 ±  0.004  ms/op
[info] FoldRight.conts       1000000  avgt   30  77.292 ±  9.327  ms/op
[info] FoldRight.standard        100  avgt   30   0.002 ±  0.001  ms/op
[info] FoldRight.standard      10000  avgt   30   0.154 ±  0.036  ms/op
[info] FoldRight.standard    1000000  avgt   30  18.796 ±  0.551  ms/op
[info] FoldRight.tailCalls       100  avgt   30   0.002 ±  0.001  ms/op
[info] FoldRight.tailCalls     10000  avgt   30   0.176 ±  0.004  ms/op
[info] FoldRight.tailCalls   1000000  avgt   30  33.525 ±  1.041  ms/op
于 2016-09-22T07:34:15.973 に答える