- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
同じ答えを繰り返し作り直している計算を、1回だけ作って取っておく形に変えます。
まず結論
同じ部分問題を何度も解き直しているなら、答えを覚えておけば済みます。払うのは、覚えておく場所です。
この交換の極端さは、秒数より呼び出し回数がはっきり示します。フィボナッチの素朴な再帰は n=35 で 29,860,703 回呼ばれますが、異なる部分問題は 36 個しかありません。
fib(n) = fib(n-1) + fib(n-2) をそのまま再帰で書いて n=35 を計算します。関数は何回呼ばれるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
重なる部分問題と、覚えておくという選択
fib(n) は fib(n-1) と fib(n-2) の和である。この定義をそのまま再帰で書くと、落とし穴があります。fib(35) を求めるには fib(34) と fib(33) が要り、fib(34) を求めるにもまた fib(33) が要ります。同じ fib(33) が2つの別の枝から要求され、素朴に書くとその2回はそれぞれ一から計算されます。
枝分かれは段ごとに起きるので、重複は下へ行くほど倍々に広がります。一方で引数に現れる値は n=35 なら 0〜35 の 36 通りしかありません。答えが 36 種類しかないのにそれを何百万回も作り直している——これが「同じ計算を2回している」状態です。
対処は単純で、一度出した答えを引数ごとに取っておき、次に同じ引数が来たら取り出すだけです。Python 公式は functools.cache をこう説明しています。
Simple lightweight unbounded function cache. Sometimes called "memoize".
Returns the same as lru_cache(maxsize=None), creating a thin wrapper around a dictionary lookup for the function arguments.
辞書引きの薄いラッパー、というのが正体です。引数を鍵にした辞書がひとつ増えるだけ。そして辞書が増えるということは、場所を払うということです。
- ・重複は段が深くなるほど倍々に広がる
- ・一方で引数の種類は 0〜35 の 36 通りしかない
2,986万回と36個
実際に測りました。環境は Docker の python:3.13-slim(Python 3.13.15)、ネットワーク無し、同じスクリプトを2回実行して再現性を確認しました。
--- call counts (naive), n vs number of function calls ---n= 10 naive calls= 177 memo distinct subproblems=11n= 20 naive calls= 21,891 memo distinct subproblems=21n= 30 naive calls= 2,692,537 memo distinct subproblems=31n= 35 naive calls= 29,860,703 memo distinct subproblems=36
n が 10 から 35 へ 25 増えただけで、呼び出し回数は 177 回から 29,860,703 回になっています。右の列はほぼ動きません。n=35 での比は約 83万倍です。
メモ化側が何をしたかは公式のAPIが報告します。lru_cache を付けた関数は cache_info() を持ち、キャッシュを空にして fib(35) を1回呼んだ直後の値がこれです。
CacheInfo(hits=33, misses=36, maxsize=None, currsize=36)
misses=36 が実際に計算した回数、hits=33 が保存済みの答えを使い回した回数、currsize=36 が保存エントリ数です。本当に行われた計算は 36 回で、残りは辞書引きで済みました。
ここで大事なのは、この数字が測定値ではない点です。秒数は機械の速さや負荷で変わりますが、29,860,703 と 36 はアルゴリズムの形だけで決まるので、どの機械で走らせても同じ値になります。覚えるなら秒数ではなくこちらです。
n=35 の素朴な再帰で 29,860,703 回の呼び出しが起きるのに、異なる部分問題が 36 個しかないのはなぜですか。
時間が減り、場所が増える
2つの出力を並べると、交換の両側が数字で見えます。時間側は 29,860,703 回の呼び出しが実計算 36 回 + 辞書引き 33 回になり、空間側は保存エントリが 0 個から 36 個になりました。素朴な再帰は場所を一切使わない代わりに答えを捨てては作り直し、メモ化は捨てるのをやめる代わりに置き場所を持ちます。減った時間の対価として場所を払っているわけです。
だから 「メモ化すれば速くなる」は条件付きです。部分問題が重ならないなら、hits が立たないまま保存場所と辞書操作の費用だけが残ります。「遅いからメモ化する」ではなく、同じ引数の呼び出しが繰り返されているかを先に確かめる順序になります。
もうひとつの条件が、答えが後から変わらないことです。公式はこう書いています。
Accordingly, it doesn't make sense to cache functions with side-effects, functions that need to create distinct mutable objects on each call (such as generators and async functions), or impure functions such as time() or random().
time() をキャッシュすれば、以後ずっと同じ時刻が返ります。使い回してよいかは、速さではなく関数の性質で決まります。
場所の払い方は二択ではない
同じ fib(35) を、保存場所の使い方だけ変えて3通り書けます。3つ目は再帰も辞書も使わず、直前の2つの値を変数に持って下から順に足していく形です。
方法 保存する場所 呼び出し/反復素朴な再帰 なし 29,860,703 回の呼び出しメモ化 36 エントリ 実計算 36 回 + 使い回し 33 回下から積み上げ 変数2つ n 回の反復
下から積み上げる方法は、n がいくら大きくても持つ値は2つのままです。払い方は二択ではなく段階があります。
ただしこれを一般則にしてはいけません。フィボナッチでは次の値が直前の2つだけで決まるので古い値を捨てられますが、依存の形が複雑な問題では後からどれが要るか分からず、保存を減らせません。差は問題の依存構造から来ています。
Python 公式は lru_cache について「time() や random() のような impure な関数をキャッシュしても意味がない」と述べています。ここから読み取れる、メモ化が成立する条件は何ですか。
純関数のメモ化(本レッスン)
fib(33) の答えは、いつ引いても同じです。保存した瞬間から永遠に正しいので、古くなったかを確かめる仕組みが要りません。使い回してよいかは、関数が純粋かどうかだけで決まります。
HTTP のキャッシュ(第35週)
保存した応答の元になった資源は、サーバ側で後から変わりえます。だから保存してあるだけでは足りず、まだ使ってよいかを判断する仕組みが必要になります。第35週『キャッシュはどこに効くのか — 鍵と鮮度』で扱った通りです。
どちらも「答えを保存して引き直す」仕組みです。では、メモ化に無くて HTTP キャッシュにあるものは何でしょうか。
保存した答えが、保存した後に間違いになることがあるかどうかで考えてみてください。
この章のまとめ
- 同じ部分問題が重なって現れるなら、答えを保存して引き直せば再計算は消える。Python 公式は
functools.cacheを辞書引きの薄いラッパーと説明している。 - n=35 で素朴な再帰は 29,860,703 回呼ばれるが、異なる部分問題は 36 個。
cache_info()はhits=33, misses=36, currsize=36を報告する。 - この呼び出し回数はアルゴリズムの性質なので、どの機械でも同じ。秒数は環境で変わる。
- 減った時間の対価は保存場所。部分問題が重ならないなら、払うだけで得るものが無い。
- 使い回してよいかは速さではなく関数の性質で決まる。純関数なら鮮度の判断がそもそも不要。ここが第35週の HTTP キャッシュとの分かれ目。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
n=35 のフィボナッチで、素朴な再帰の呼び出し回数 29,860,703 と cache_info() の currsize=36 を並べると何が言えますか。
用語集(3語)
- メモ化
- 一度計算した答えを引数と対応づけて保存し、同じ引数で呼ばれたら再計算せずに返す手法。Python 公式は functools.cache を Sometimes called "memoize". と説明している。
- 純関数
- 同じ引数なら常に同じ答えを返し、外部に影響を残さない関数。メモ化が成立する条件。time() や random() はこれに当たらない。
- cache_info()
- lru_cache が付いた関数のメソッド。hits(使い回した回数)・misses(計算した回数)・currsize(保存中の件数)を返す。