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

nishio hirokazu @nishio

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

nishio hirokazu @nishio

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

K. Sakaguchi @pi8027

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

nishio hirokazu @nishio

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

K. Sakaguchi @pi8027

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

K. Sakaguchi @pi8027

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

nishio hirokazu @nishio

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

nishio hirokazu @nishio

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

K. Sakaguchi @pi8027

@nishio Control.Arrow

nishio hirokazu @nishio

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

K. Sakaguchi @pi8027

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

nishio hirokazu @nishio

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

K. Sakaguchi @pi8027

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

K. Sakaguchi @pi8027

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

K. Sakaguchi @pi8027

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

nishio hirokazu @nishio

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

K. Sakaguchi @pi8027

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

Jun Mukai @jmuk

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

nishio hirokazu @nishio

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

nishio hirokazu @nishio

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

K. Sakaguchi @pi8027

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

K. Sakaguchi @pi8027

http://www.haskell.org/haskellwiki/The_Fibonacci_sequence ほー

Jun Mukai @jmuk

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

herumi @herumi

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

kinaba @kinaba

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