メモ化とは、答えを覚えておくこと
メモ化とは、一度求めた答えを覚えておき、同じ計算を二度しないようにする工夫です。遅い再帰を、ほとんど一瞬で終わる手順に変えられます。
フィボナッチ数の30番目は、そのままだと約270万回も関数を呼びます。メモ化すると、59回で済みます。
このレッスンのゴール
メモ
遅い再帰に辞書のメモを足して、呼び出しの回数を減らせる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| 重複する計算 | 同じ引数で、何度も行われる同じ計算 | |
| メモ化 | 求めた答えを覚えて、再利用すること | |
| メモ | 答えを覚える辞書。引数が鍵、答えが値 | memo[n] |
| 辞書 | 鍵から値を引く Python のデータ | |
| 最少枚数 | 金額を作る硬貨の枚数で、一番少ないもの |
学生が入力するセルは、このプレビューでは空白です。
同じ計算が何度も行われる
fib(5) を求めるとき、fib(3) は2回、fib(2) は3回も計算されます。引数が同じなら、答えは毎回同じです。
n が大きくなると、この無駄は急に膨らみます。fib(30) の呼び出しは、2692537 回です。
メモなしの呼び出し回数
# メモなしのフィボナッチ。同じ計算を何度もやり直します。
calls = [0]
def fib(n):
calls[0] = calls[0] + 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(25), "呼ばれた回数:", calls[0])
# 25 を 20 に変えて、回数を見ましょう。
メモ化は辞書に答えを入れる
メモ化は3つの手順です。まず、辞書に答えがあれば、それを返します。なければ計算します。最後に、答えを辞書に入れます。
こうすると、各 n の計算は1回だけです。fib(30) の呼び出しは、2n-1 で59回になります。
メモ化した呼び出し回数
# メモ（辞書）つきのフィボナッチ。一度求めた答えは、辞書から取り出します。
calls = [0]
memo = {}
def fib(n):
calls[0] = calls[0] + 1
if n in memo:
return memo[n]
if n < 2:
result = n
else:
result = fib(n - 1) + fib(n - 2)
memo[n] = result
return result
print(fib(30), "呼ばれた回数:", calls[0])
# 30 を 40 に変えても、回数は 79 回です。
メモの有無で変わる呼び出し回数
| n | メモなし | メモあり |
|---|---|---|
| 10 | 177 | 19 |
| 20 | 21891 | 39 |
| 30 | 2692537 | 59 |
学生が入力するセルは、このプレビューでは空白です。
硬貨の最少枚数にも使える
金額を作る硬貨の最少枚数を考えます。答えは、どの硬貨を最後に1枚使うかを全部試して、一番少ないものです。
(金額 - 硬貨) の最少枚数を、もう一度求めることになります。同じ金額を何度も求めるので、メモ化が効きます。次の表は、1円、5円、12円という仮の硬貨の答えです。
1、5、12 の硬貨で金額を作る
| 金額 | 最少枚数 | 内訳 |
|---|---|---|
| 5 | 1 | 5 |
| 10 | 2 | 5 と 5 |
| 12 | 1 | 12 |
| 13 | 2 | 12 と 1 |
| 15 | 3 | 5 と 5 と 5 |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
大きい硬貨から使えば、いつも枚数が最少だと思いがちです。15円を作るとき、12円を使うと 12 と 1 と 1 と 1 の4枚です。5円を3枚の方が少なくなります。全部の硬貨を試して、一番少ないものを選びます。
ラボの端末で表を作る
表を下から作る方法もあります。最初の2つを決め、足し算を繰り返して、小さい方から順に埋めます。
次の Run は、フィボナッチ数を表に入れて出します。同じ値を、2回計算しません。2つ目は、40番目を求めます。
最初の11個を表に入れる
python3 -c "t = [0, 1]; [t.append(t[-1] + t[-2]) for _ in range(9)]; print(t)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
40番目を求める
python3 -c "t = [0, 1]; [t.append(t[-1] + t[-2]) for _ in range(39)]; print(t[-1])"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦: 作り方の数
課題が通ったら、金額を作る組み合わせが何通りあるかを数えましょう。順番は区別しません。
最少枚数の問題と、メモの鍵がどう違うか考えます。金額と、使う硬貨の数の2つが要ることに気づけるでしょうか。