Haskellでfibonacci数を早く！

Haskell

fibonacci数とは

F_0 = 0
F_1 = 1
F_n = F_{n-1} + F_{n-2}

素直にHaskellに実装する

fibonacci :: Int -> Integer
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = (fibonacci $ n-1) + (fibonacci $ n-2)

これはとてもスマートだがとても遅い。どのくらい遅いかというと、50とか指定した暁には現代の最高スペックCPUでも多分待ち切れないレベルで遅い。

その理由は、私みたいなド素人でもプロファイルを取れば分かる。（賢明な方であればプロファイル取らなくても分かるかもしれない）
このfibonacci関数は毎度律儀呼び出されており、メモ化（ある関数が同じ引数の呼び出しに対し、再計算を行わずに前回計算した値をそのまま返す処理）を行わない。

従ってこの原始的なfibonacci関数は
F_n + \sum_{i=1}^{n-1}i
回の関数呼び出しを行う。わーお、これは酷い。

ちょっと工夫してHaskellに実装する

これを早くする方法は色々あるが、とりあえずメモ化すればいい、ってのは誰でも思い付く。最初は手続き型っぽくHashTable使おうかと思ったが、遅延評価するHaskellはもっとシンプルに無限リスト使えばいい。

fibonacci :: [Integer]
fibonacci = map f [0..]
  where
    f :: Int -> Integer
    f 0 = 0
    f 1 = 1
    f n = (fibonacci !! (n-1)) + (fibonacci !! (n-2))

Haskellは必要になるまで値の評価を行わないので、無限リストが簡単に書ける。このように自分自身の前の値を参照すれば何度も呼び出す必要は無い。

実際速度を測ってみると10000とかでも数秒で値が帰ってくる。

もっと工夫して実装する

そもそも!!は割と遅い処理なので、これを無くしたいナーとか思うと、再帰を使ってこんな感じに書ける

fibonacci :: Int -> Integer
fibonacci num = f 0 1 num
  where
    f i _ 0 = i
    f i j n = f j (i+j) (n-1)

iはn-2、jはn-1の値である。こうすればデータを持つ必要もない。100000とかで数秒で帰ってくるのでとっても早い。