« Project Euler : Problem 46 ~ Goldbach予想 | トップページ | Project Euler : Problem 47 »

2010年8月30日 (月)

Haskell の fibonacci が遅い理由が分かった

 Haskell の勉強のためにちょくちょく覗かせてもらっているブログに『Haskellの神話』という記事が載っていました。
 詳しいことは元のブログを読んでもらうとして、簡単に説明すると

  • Haskell で有名な "fibs = 0 : 1 : zipWith (+) fibs (tail fibs) " という実装は、実はかなり遅い。
  • その原因は Haskell の特徴である「遅延評価」のせいである。
  • (+) を「正格評価」してくれる "zipWith'" を "seq" を使って自前で定義すると "fibs" はとても速くなる
ということらしいです。
 『Haskellの神話』のコードを基に次のようなコードを書いてみました。
-- test1 fib n = fibs !! n fibs = 1 : 1 : zipWith (+) fibs (tail fibs) main = print $ fib 100000
-- test2 zipWith' f (a:as) (b:bs) = x `seq` x : zipWith' f as bs where x = f a b zipWith' _ _ _ = [] fib n = fibs !! n fibs = 1 : 1 : zipWith' (+) fibs (tail fibs) main = print $ fib 100000
 実際に試してみると、
$ time ./test1 42026927029951543863190051012939151 ..(以下略) real 0m3.122s user 0m2.332s sys 0m0.016s
$ time ./test2 42026927029951543863190051012939151 ..(以下略) real 0m0.858s user 0m0.232s sys 0m0.004s
といった具合で、あまりの差に愕然……。

 自分の場合、「Fibonacci 数列」を

fibonacci :: Integral a => [a] fibonacci = fibs 1 1 where fibs a b = a : fibs b (a + b)
というふうに定義していたのですが、これだと「test1」とほぼ同じでした。
 そこで私も "seq" を使って自前の「Fibonacci 数列」をちょいと改造してみました。
fibonacci :: Integral a => [a] fibonacci = fibs 1 1 where fibs a b = seq a $ a : fibs b (a + b)
 これはほぼ「test2」と同じ性能のようです。

 Haskell は「遅延評価」のおかげで簡単に「無限リスト」を操作する手段を手に入れたけど、そのせいで計算が遅くなることがあるということなんですね。
 "seq" を使った「正格化」での速度改善とかはどこでも使える分けではなさそうだし、素人の私には使いどころが分からない……。
 Haskell の奥はとんでもなく深そうですね。(だいたい、まだ「モナド」がよく分かっていないし……)

« Project Euler : Problem 46 ~ Goldbach予想 | トップページ | Project Euler : Problem 47 »

Haskell」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/49293419

この記事へのトラックバック一覧です: Haskell の fibonacci が遅い理由が分かった:

« Project Euler : Problem 46 ~ Goldbach予想 | トップページ | Project Euler : Problem 47 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ