25日前公開・24日前更新・6 min read

フィボナッチ+メモ化再帰を体験する

AtCoder競技プログラミング初心者Rust

はじめに

メモ化再帰を用いてフィボナッチ数列の計算が速くなることを体験します.
使用言語は Rust ですが, 基礎的な文法しか使用しません. 関数の再帰呼び出しと配列を使用するくらいです.

フィボナッチ数列とは

知ってるよ, って方は飛ばしてください.

次の式で表される数列のこと.

F_i = F_{i - 1} + F_{i - 2} \,\, (n \ge 2) , \, F_0 = 0 , \, F_1 = 1

$F_0$ を定義しない場合もありますが, 今回はプログラムで扱うので便宜上 $0$ から開始するものとする.

$F_0$ から $F_7$ は次の通り:

i : 0, 1, 2, 3, 4, 5, 6, 7
F : 0, 1, 1, 2, 3, 5, 8, 13

愚直に実装する

fib の定義

フィボナッチ数列の第 $n$ 項を計算する関数 fib(n) を定義します.

fib の実行

以下のコードブロックで実行してみる.

愚直に実装したときの問題

普通に結果も出て一件落着とはなりません. 実は, この実装では無駄な計算をたくさんしています.

fib(5)を例に計算を追跡します.

fib(5) = fib(4) + fib(3) ... (1)
         = fib(3) + fib(2) + fib(3) ... (2)
         = fib(2) + fib(1) + fib(2) + fib(3) ... (3)
         = fib(1) + fib(0) + fib(1) + fib(2) + fib(3) ... (4)
         = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(3) ... (5)
         = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(2) + fib(1) ... (6)
         = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) ... (7)
         = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5

計算を見てわかるように, fib(0), fib(1) になるまでひたすら展開しています.

例えば (2) の時点で fib(3) + fib(2) + fib(3) = fib(3) * 2 + fib(2) 的なことができれば, (5) から (7) における 2回目の fib(3) を展開する必要がなくなります.

無駄な計算をコードで確認

fib(n)が呼ばれた回数をv[n]に記録する配列vを用意し, fib(5)の場合で確認する.

fib(0) was called 3 times.

fib(1) was called 5 times.

fib(2) was called 3 times.

fib(3) was called 2 times.

fib(4) was called 1 times.

fib(5) was called 1 times.

()

計算量

すごく雑に見積もります.

愚直な実装では, fib(n) = fib(n - 1) + fib(n - 2) という風に, 各 $n$ の計算が2つに分裂します. そして $n$ は $n = 0, 1$ になるまで $1$ ずつ減少していくので, 倍, 倍, 倍, ..., を $n$ 回, 即ち $O(n) = 2^n$ です.

あれ?

ここで一度, 自分の手や頭でfib(5)を計算してみる. 恐らくこんな感じで計算する.

fib(0) = 0, fib(1) = 1
fib(2) = fib(1) + fib(0) = 1 + 0 = 1
fib(3) = fib(2) + fib(1) = 1 + 1 = 2
fib(4) = fib(3) + fib(2) = 2 + 1 = 3
fib(5) = fib(4) + fib(3) = 3 + 2 = 5

あれ? 僕賢い? でも明らかに $n$ の線形時間( $O(n) = n$ )で解けてるからコンピュータより賢い?

自惚れるんじゃあない. 何が違うんだろうかと考える.

再帰定義では, $n = 0, 1$ の時に初めてfib(n) = 0, 1という数値に落ち着く. 逆に言えば, $n \ge 2$ の間はひたすら展開する.
手計算では, すでに計算した値を用いているため, わざわざ $n = 0, 1$ まで展開する必要がない.

というわけで, メモ化です. 実装しましょう.

メモを用いた実装

色々な実装方法がありますが, ここではメモを引数として与えてやります.

また, メモの初期化方法も様々です. ここでは, メモされていないことを None として扱うため, Noneで初期化します.

未メモ状態の表し方として,

-1 (フィボナッチ数列の定義から, 負の値をとることがない)
bool型配列を別に用意

などの方法もあります.

実行

以下で実行してみる.

fib(0) = 0

fib(1) = 1

fib(2) = 1

fib(3) = 2

fib(4) = 3

fib(5) = 5

fib(6) = 8

fib(7) = 13

()

呼び出し回数を確認

愚直に計算した場合と同様に, 呼び出し回数(メモを用いず実際にfib(n)を計算した回数)を調べます.

fib(0) was called 0 times.

fib(1) was called 0 times.

fib(2) was called 1 times.

fib(3) was called 1 times.

fib(4) was called 1 times.

fib(5) was called 1 times.

()

結果の比較

それぞれの呼び出し回数を比べる(表を使ってみた).

fib(n)	0	1	2	3	4	5
愚直	3	5	3	2	1	1
メモ	0	0	1	1	1	1

メモ化した場合は $O(n) = n$ なので当然と言えば当然. 表にするまでもない.

$n = 5$ の時点でこの差なので, $n$ をより大きい値にすると差がもっと大きくなることが容易に想像がつく. Magicode のコードブロック上で $n$ を大きくすることは負担になる可能性があるので, 控えましょう(どのくらいまでやってくれるのかは気になるが).

まとめ

簡単に実装できて, かなりのコストを削減できる.
ブラウザやメモリの話でもキャッシュ(メモ)という言葉はよく聞く. つまり, 知っていると色々応用できるかも.
いつぞやの AtCoder でとりあえずメモしたら通った問題もある. 解法としては載っていなかったが.
あわよくば Rust おもろそうとか思ってくれたりして(誰目線)(match 位しか Rust っぽさ出さなかったけど).