2010年6月22日

Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」はとても遅い件

まとめました。
1
nishio hirokazu @nishio

WikipediaのHaskellの項目、fib = 1:1:zipWith (+) fib (tail fib)が線形時間で動くって書いてあるけど、これ正しくないよね?

2010-06-22 14:00:54
nishio hirokazu @nishio

Haskellの「fib=1:1:zipWith(+) fib (tail fib)」は2.6乗のオーダーで時間がかかり、N = 100000ではPythonより遅い http://d.hatena.ne.jp/nishiohirokazu/20100622/1277208908

2010-06-22 21:21:36
坂口和彦 @pi8027

@nishio 型が [Integer] になっていませんか? [Int] なら速いかもしれない。(分からないけど)

2010-06-22 21:33:56
nishio hirokazu @nishio

@pi8027 Intだとすぐに溢れるだろJK

2010-06-22 21:36:22
坂口和彦 @pi8027

ああでも Int の範囲に納まらないのかな

2010-06-22 21:36:30
坂口和彦 @pi8027

@nishio なんで遅くなるか良く分かっていないんですが、fib = map fst $ iterate (snd &&& uncurry (+)) (1,1) だとどうですか

2010-06-22 21:38:13
nishio hirokazu @nishio

@pi8027 えー。それが仮に速くても僕の記事になんの影響もない気がするんだが(笑)

2010-06-22 21:40:13
nishio hirokazu @nishio

@pi8029 おっと、&&&がない!何をインポートすればいい?

2010-06-22 21:41:36
nishio hirokazu @nishio

@pi8027 いまコンパイルしているけど、僕の予想では同程度かさらに遅くなるんじゃないかな

2010-06-22 21:41:12
坂口和彦 @pi8027

@nishio でも下に出ているような冗長はコードはいらなくなるわけですよね。

2010-06-22 21:41:17
nishio hirokazu @nishio

@pi8027 冗長なコードと同程度に早ければね。僕の予想は1:1:zipWithと同等かさらに遅いってもので、それは正しかった。10万で1.9sec, 20万で19.1sec。激しく悪化している(笑)

2010-06-22 21:47:34
坂口和彦 @pi8027

@nishio えー。でもやっぱりあの冗長なコードは許せないので、もうちょっと色々試してみます...。

2010-06-22 21:54:40
坂口和彦 @pi8027

GHC に手を入れて速度問題を解決できるのが一番いいんだけどなぁ。

2010-06-22 21:54:53
坂口和彦 @pi8027

型の上ではリストのように見えるけど、普通にループ回してくれればいいだけなので、GHCさんには頑張ってほしい。

2010-06-22 21:55:50
nishio hirokazu @nishio

@pi8027 ちなみに僕の想像が正しければ遅くなる理由(余計な0.6乗)はサンクの増殖が原因で、高速なバージョンが速いのは単に末尾再帰であることだけじゃなくてfib' 5 1 1を簡約したときにfib' 4 1 (1 + 1)になるだけでサンクが増えないからだ

2010-06-22 22:09:19
坂口和彦 @pi8027

@nishio じゃあ、Int -> (a -> a) -> a -> a みたいな型を持つ"関数をN回適用した結果を返す関数"があればいいんですよね。

2010-06-22 22:17:56
Jun Mukai @jmuk

@nishio 手元に今Haskellの実行環境がないので自信があまりないですが、下のものは+を正格評価しないとスタックが溢れたりしないでしょうか。上も遅延評価が影響したりしてないですかね。

2010-06-22 22:11:39
nishio hirokazu @nishio

@jmuk 上のが遅い理由は遅延評価だと思います。下のはfib 4 1 (1 + 1)のパターンマッチで1 + 1の評価が強制されるのでseqとかしないでも大丈夫です。

2010-06-22 22:18:14
nishio hirokazu @nishio

@pi8027 「関数をN回適用する」ってサンクが作られたらダメな気がする

2010-06-22 22:20:24
坂口和彦 @pi8027

@nishio それは処理系次第ですよ。iter (n+1) f a が iter n f (f a) になればいい。

2010-06-22 22:22:48
Jun Mukai @jmuk

@nishio ようやく実行環境を整えました。上は遅延評価ですね。下も-O3でないと評価が遅延されて遅いかと。zipWith'みたいな関数を定義すれば普通に速いかと。

2010-06-23 00:49:27
herumi @herumi

zipWith'は既に試してましたが,zipWithより2倍ぐらい遅くなったので「遅延だから」というのは違うと思います. zipWith' f (x:xs) (y:ys) = ((f $! x) $! .. http://togetter.com/li/31078

2010-06-23 10:01:10
kinaba @kinaba

Integer加算の分を考えると話が複雑になるので、とりあえず0,0から始めてみる http://codepad.org/FgRsOFi7 と、at0 と at1 が同じくらい(当たり前)で、at2 が圧倒的に速い。速いのは当然なんだけどオーダが違うように見えるのは、えーと…

2010-06-23 12:43:54
残りを読む(4)

コメント

herumi @herumi 2010年6月23日
zipWith'は既に試してましたが,zipWithより2倍ぐらい遅くなったので「遅延だから」というのは違うと思います. zipWith' f (x:xs) (y:ys) = ((f $! x) $! y):zipWith' f xs ys であってますかね.
0
kinaba @kinaba 2010年6月23日
+の引数の計算ではなく、+の計算自体を正格評価しないと変わらないので、遅延をやめるならば zipWith' f (x:xs) (y:ys) = ((:) $! (f x y)) (zipWith' f xs ys) ではないでしょうか @herumi
0