メモ化フィボナッチ

フィボナッチ数は fib(k) = fib(k-1) + fib(k-2) で決まります。この式をそのまま再帰にすると、数行で書けるのに、n を 40 にした途端に返ってこなくなります。式は正しいのに遅い。その理由を数えるところから始めます。

fib(5) を出すのに、fib(2) を 3 回計算している

fib(5) は fib(4) と fib(3) を呼び、fib(4) はまた fib(3) と fib(2) を呼びます。

fib 3 が 2 回、fib 2 が 3 回出てきます。しかも 2 回目の fib 3 は、1 回目とまったく同じ計算を最初からやり直しています。呼び出しの総回数を数えると、次のように伸びます。

n が 10 増えるごとに、およそ 123 倍です。答えは n + 1 種類しかないのに 3 億回計算しているのだから、無駄なのは計算の中身ではなく、同じ問いを何度も出していることのほうです。

2 回目からは、書き留めた答えを読む

対策は 1 つだけです。出した答えをその場で書き留めておき、次に同じ問いが来たら計算せずに読み出します。例として、組み合わせの数で試します。comb(n, k) は comb(n-1, k-1) + comb(n-1, k) で決まり、これも素朴に書くと同じ重複が起きます。

def comb(n, k, memo=None):
    if memo is None:
        memo = {}
    if k == 0 or k == n:
        return 1
    if (n, k) in memo:
        return memo[(n, k)]
    memo[(n, k)] = comb(n - 1, k - 1, memo) + comb(n - 1, k, memo)
    return memo[(n, k)]

memo=None は引数を省略したときに None を使う指定です。comb(4, 2) なら関数の中で新しい辞書を作り、再帰では comb(3, 1, memo) のように同じ辞書を渡します。初期値を memo={} にすると呼び出し間で辞書を共有してしまうため、None から作ります。

(n, k) は二つの値をまとめたタプルです。例えば memo = {}、memo[(4, 2)] = 6 と書くと、memo[(4, 2)] で 6 を取り出せます。整数の組を一つの辞書キーにできるので、二つの引数が両方同じ問いを区別できます。演習のキーは整数一つです。

書き留める場所を用意し、答える前に覗き、返す前に書き込む。この 3 つだけです。同じ (n, k) は一度しか計算されなくなるので、計算回数は答えの種類の数までしか増えません。

こうして途中の答えを覚えておく手を メモ化、fib(k) = fib(k-1) + fib(k-2) のように自分自身で自分を表す式を 漸化式、小さいほうから順に埋めていくやり方を ボトムアップ と呼び、これらを使う設計法をまとめて 動的計画法 と言います。

書き留めた紙を、次の人に渡してしまう

memo = {}          # 関数の外に置くと呼び出しをまたいで残る

def f(k):
    ...

書き留める場所を関数の外に作ると、前の呼び出しの結果が次の呼び出しにも残ります。同じ計算をする関数なら得に見えますが、途中で条件が変わる問題では前の答えが混ざり、原因の分かりにくい間違いになります。書き留める場所は、外から呼ばれる関数の中で作るのが安全です。

やってみよう

ひな形の TODO を完成させてください。基底ケース・記憶の確認・再帰結果の保存を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

本文の comb は二つの小さい問題を組み合わせ、その答えを辞書に覚えます。演習でも辞書は引数で明示して渡します。辞書の生成と最初の呼び出しは用意しました。小さい入力での停止、記録の確認、再帰結果を保存して返す処理を自分で書きます。

1. 基底ケース・記憶の確認・再帰結果の保存を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える