『ふつうのHaskellプログラミング』に載ってた「たらい回し関数1」を、当時リリースされたばかりの Java 8 を使った遅延評価版で書いてみたことがあるが、ムダな計算がなくなってだいたい千分の一くらい時間で計算が終わるようになった。
今回は、これを Cats のEvalを用いて書いてみる。Scala は2.12.8、Cats は1.6.0を使った。
- ソース: eval.sc (gist)
ふつうのたらい回し関数
ふつうに Scala でtaraiを書くと以下のようになる。
def tarai(x: Int, y: Int, z: Int): Int =
if (x <= y) y else tarai(tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y))
このマシン(4G の MBA) の IntelliJ Scala Worksheetから、(20, 10, 5)を与えて実行すると 6〜7秒かかる。
def measure(f: => Int): (Int, Long) = {
val start = System.currentTimeMillis()
val result = f
val millis = System.currentTimeMillis() - start
(result, millis)
}
measure(tarai(20, 10, 5))
//res0: (Int, Long) = (20,6076)
次に Evalを用いて、この遅延評価版を書いてみる。
Eval 版
Eval はトランポリンを使ったスタックセーフなデータ型で、val キーワード相当の now、lazy val 相当の later、def 相当の always といった 3つの評価戦略がある。以下、これを踏まえてそれぞれみてみる。
自然な Eval
何通りか書き方があるがここでは以下のように書いてみた。
def taraiE(x: Eval[Int], y: Eval[Int], z: Eval[Int]): Eval[Int] =
(x, y).mapN(_ <= _) ifM (y, taraiE(taraiE(x.map(_ - 1), y, z),
taraiE(y.map(_ - 1), z, x),
taraiE(z.map(_ - 1), x, y)))
xとyのペアを apply 構文のmapNで大小比較してから、flatMap 構文のifMで条件分岐させた。デクリメントするところはmapを使用しているが、mapの実装ではEval.FlatMapとNowを組み合わせたようなインスタンスが生成されている。
以下のようにすると、実行のたびにかなりバラつくが 2〜8ミリ秒で計算が終わる。
val me = measure { taraiE(Now(20), Now(20), Now(5)).value }
//me: (Int, Long) = (20,2)
ここではEvalの派生クラスNowで渡しているが、Later、Alwaysでも結果はあまり変わらない。
以下のように、mapをつかわず型をNow、Later、Alwaysに固定したtaraiを書くこともできる。
Now 固定
Nowは、eager 評価かつメモ化される。純正な Scala の構文でいえばvalキーワードがついた変数と似た挙動になる。
def taraiN(x: Now[Int], y: Now[Int], z: Now[Int]): Now[Int] = Now {
if (x.value <= y.value) y.value
else taraiN(taraiN(Now(x.value - 1), y, z),
taraiN(Now(y.value - 1), z, x),
taraiN(Now(z.value - 1), x, y)).value
}
val mn = measure { taraiN(Now(20), Now(10), Now(5)).value }
//mn: (Int, Long) = (20,37578)
即時評価なためオリジナルのtaraiと同様無駄な計算も評価されてしまうため遅い。むしろオリジナルと比べて6倍ほども時間がかかっている。
Later 固定
Laterもメモ化されるが、lazy に評価される。Scalaの構文だとlazy valな変数に対応する2。
def taraiL(x: Later[Int], y: Later[Int], z: Later[Int]): Later[Int] = Later {
if (x.value <= y.value) y.value
else taraiL(taraiL(Later(x.value - 1), y, z),
taraiL(Later(y.value - 1), z, x),
taraiL(Later(z.value - 1), x, y)).value
}
val ml = measure { taraiL(Later(20), Later(10), Later(5)).value }
//ml: (Int, Long) = (20,11)
遅延評価＋メモ化で速い。
Always 固定
Alwaysも lazy な評価だが、これはメモ化されない。def、()=>Int、Function0と似た挙動になる。
def taraiA(x: Always[Int], y: Always[Int], z: Always[Int]): Always[Int] = Always {
if (x.value <= y.value) y.value
else taraiA(taraiA(Always(x.value - 1), y, z),
taraiA(Always(y.value - 1), z, x),
taraiA(Always(z.value - 1), x, y)).value
}
val ma = measure { taraiA(Always(20), Always(10), Always(5)).value }
//ma: (Int, Long) = (20,8)
これも遅延評価されていて必要な値のみが計算されるので速い。メモ化はされないがこの例ではあまり影響がない。
名前渡し版
実はEvalを使わなくても「名前渡し」で同様に書ける。
def taraiZ(x: => Int, y: => Int, z: => Int): Int =
if (x <= y) y else taraiZ(taraiZ(x - 1, y, z),
taraiZ(y - 1, z, x),
taraiZ(z - 1, x, y))
val mz = measure(taraiZ(20, 10, 5))
//mz: (Int, Long) = (20,9)
これも速い。メモ化しない遅延評価だからAlwaysに近い。
まとめ
| タイプ | 遅延 | メモ | 時間 | 備考 |
|---|---|---|---|---|
| オリジナル | × | × | 6〜7sec | - |
| 自然な Eval | - | - | 2〜8ms | Eval.FlatMap |
| Now | × | ○ | 30〜40sec | val 相当 |
| Later | ○ | ○ | 5〜20ms |
lazy val 相当 |
| Always | ○ | × | 5〜20ms |
def、()=>Int 相当 |
| 名前渡し | ○ | × | 5〜20ms | - |
※ 「時間」は何度か実行してからの目分量。