フィボナッチ関数の計算について記事を見掛けた。
計算速度が大幅に違う理由を遅延評価と誤解しているようだけれど、そうではない。
まず最初の定義について見てみよう。
fibonacci :: Integer -> Integer fibonacci n | n == 1 = 1 | n == 2 = 1 | otherwise = fibonacci (n-2) + fibonacci (n-1)
この定義だと計算は非常に遅い。 どうして遅くなるのかを考えるにはコールツリーを書いてみるとわかりやすい。
この関数を1回呼ぶと2つに枝分れしていくので、関数呼出しの回数は指数関数のオーダーになる。 ここでは関数呼出しの回数がそのまま計算量であると考えてよいだろう。 そして同じ引数での呼出しが何度もあることがわかる。
そして速度を改善したもうひとつの定義を見てみよう。
fibonacci :: Integer -> Integer fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)
これは前者と違って同じ計算をしないようになっている。
配列として定義されているのでちょっとわかりにくいが、このコンセプトをそのまま再帰関数に変形するとこうなる。
fibonacci :: Integer -> Integer fibonacci n = s n 0 1 where s i a b | i <= 0 = a | otherwise = s (i - 1) b (a + b)
これのコールツリーは枝分れが無い。
計算は線形時間で完了することになる。 関数型言語で計算量のオーダーを見積もるにはコールツリーを考えると良いかもしれない。
Document ID: 8ac61e4e0f3bc8eaf27d2bd5d9a5d8a7
