再帰処理の定番の一つがフィボナッチ数の算出だ。以前、別件で触れたように*1、ロジックの特性上、無数の重複処理が生じる。これらの重複を効率的に処理するための典型的な手立てとして、次の手法が挙げられる。
| メモ化 | 計算済みの結果をキャッシュする |
| 末尾再帰 | インタプリタ、コンパイラによる最適化 |
前者は汎用的に機能する一方、キャッシュを併用するため、メモリ効率が悪い。後者はロジックの書き方だけでなく、インタプリタ、コンパイラに依存するため、汎用的に機能しない。しかし、より高速なパフォーマンスを期待できる。
どのプログラム言語でも定番の話題なのだが、特にF#においては、フィボナッチ数の処理自体をメモ化することについて言及している投稿が見当たらなかった。フィボナッチ数の算出に限らず、関数そのものを汎用的にメモ化する手段について言及した投稿ばかりなのだ。
この投稿では、指定した順位のフィボナッチ数を求める処理を題材に、通常の再帰、メモ化再帰、末尾再帰についてまとめた。
普通の再帰
n番目のフィボナッチ数を求めるには、n-1番目、n-2番目のフィボナッチ数を合算する。そのロジックは、次のように表現できる。
let rec fib n = match n with | 0 | 1 -> n | n -> fib (n-1) + fib (n-2)
10番目の数を求めようと思えば、8、9番目の数を求め、さらにそれぞれ6、7番目、7、8番目と、処理の重複が積み重なっていく。表現は単純だが、無用な重複処理を多分に孕んでいる。
少なくとも、一度求めた順位のフィボナッチ数については、その結果を再利用したい。そこでメモ化再帰を考える。
メモ化再帰
キャッシュとして、n番目をキーとして、対応するフィボナッチ数を格納するデータを用意する。ここではDictionary*2を用いる。
まず要求された順位を確認し、計算済みであれば該当するDictionaryの値を返す。それ以外の場合、フィボナッチ数を計算することにすれば、そのロジックは次のようになる。
let fib_memo n = let memo = new Dictionary<_,_>() let rec fib n = let isExist, value = memo.TryGetValue n if isExist then //printf "!" value else match n with | 0 | 1 -> n | n -> let value = fib (n-1) + fib (n-2) memo.Add(n, value) value fib n
print文のコメントを解除すると、実際にキャッシュ（メモ）が機能していることが確認できる。
 |
test.fsx#load "fibonacci.fsx" open fibonacci for i in 0 .. 10 do fib_memo i |> printfn "%A " printfn "" |
末尾再帰
再帰処理において、その処理の最後で再帰呼出しすることを末尾呼び出しと呼ぶ。そのようにして終了しているコードは末尾再帰の状態にあり、コンパイラやインタープリタによって処理が最適化される。
例えば、メモ化再帰で紹介した関数は、フィボナッチ数を求める関数fibを内包しており、関数末尾でfibを再帰呼出ししている。つまり、この関数はメモ化だけでなく、末尾再帰にも対応している。
Microsoft公式サイトでは、フィボナッチ数を求める末尾再帰処理として、次のコードを紹介している。メモ化再帰の関数同様、関数内部に再帰する関数loopを内包しており、関数末尾でloopを呼び出している。
[<TailCall>] let fib_tail_recursion n = let rec loop acc1 acc2 n = match n with | 0 -> acc1 | 1 -> acc2 | _ -> loop acc2 (acc1 + acc2) (n - 1) loop 0 1 n
パフォーマンス比較
以上の関数3つのパフォーマンスを比較してみる。40番目までのフィボナッチ数を列挙させ、その処理時間を比較する。
通常の再帰処理では2秒足らずを要するところ、メモ化再帰、末尾再帰では1秒もかからない。通常の再帰処理に比べて圧倒的に高速なのが分かる。興味深いのは、メモ化処理の有無によるパフォーマンス上の差異だ。
メモ化再帰も末尾再帰であることから、単純にロジックの違いがパフォーマンス差に影響していると考えられる。さらに、ループ回数を増やしていくほど、このパフォーマンス差が拡大していく。今回の場合は、メモ化しない方が高速なのが分かる。
コード
