たらいまわし問題

Haskell本（ふつける）の読書会に参加。
遅延評価の項で、たらいまわし問題の処理速度をC,Javaと比較して遅延評価偉い！となっていたが、C,Javaでちょっと工夫すれば差は無いはず。
scalaで実装

  // たらいまわし（普通）
  def tarai1(x:Int, y:Int, z:Int): Int = {
    if (x <= y) y
    else tarai1(tarai1(x - 1, y, z), tarai1(y - 1, z, x), tarai1(z - 1, x, y))
  }

  // たらいまわし（キャッシュ使用）
  var cache = Map.empty[Tuple3[Int, Int, Int], Int]
  def tarai2(x:Int, y:Int, z:Int): Int = {
    if (cache.contains((x,y,z)))
      cache((x,y,z))
    else {
      val result =
        if (x <= y) y
        else tarai2(tarai2(x - 1, y, z), tarai2(y - 1, z, x), tarai2(z - 1, x, y))
      cache((x,y,z)) = result
      result
    }
  }

tarai1は素直な実装。与えられた引数で再帰的に処理する。
tarai2は処理結果をキャッシュする。同じ引数で呼ばれた時に再帰的に処理するのは無駄なのでキャッシュされた値を返す。

引数に(20,10,5)を与えた時の処理時間、tarai1は26.8秒、tarai2は0.01秒。
無駄を省けば遅延評価無くてもいいね、という結果？

Scalaの遅延評価も使って比べてみたかったのだけれど、眠くなってきた（@酔っ払い）。
というかscalaの遅延評価は限定的なので無理かも。

調べているうちにStreamという無限リストを扱えるクラスを発見したのは収穫。コップ本には記述が無いなぁ。