女性向けエンジニアスクール
3秒でわかる
一度計算した結果を引数とセットで記録し、同じ入力なら再利用する高速化の手法。処理そのものを変えずに、重複した呼び出しだけを丸ごと省けます。
もう少し詳しく
どういうものか
メモ化は、関数の計算結果を引数とセットで記録しておき、同じ引数で再び呼ばれたときは計算せずに記録から返す高速化の手法です。記録先は辞書やハッシュマップで、鍵が引数、値が結果になります。処理そのものは変えず、重複した呼び出しだけを消すため、正しさを保ったまま速度だけを上げられます。
なぜ必要か
再帰で書いた処理は、同じ引数を何度も計算していることがあります。フィボナッチ数を素直な再帰で書くと、40 番目を求める間に同じ値の計算が数億回走ります。メモ化を入れるとこの重複がすべて消え、呼び出し回数が引数の種類の数まで落ちます。動的計画法は、この考え方を表として持ち直したものです。
具体例
from functools import lru_cache
@lru_cache(maxsize=<a href="/glossary/none" class="text-primary font-medium underline underline-offset-2 hover:text-primary-dark">None</a>)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(100))
# 自前で書くとこうなる
cache = {}
def fib2(n):
if n in cache:
return cache[n]
v = n if n < 2 else fib2(n - 1) + fib2(n - 2)
cache[n] = v
return vJavaScript の React でも useMemo や useCallback が同じ発想で、依存配列が変わらない限り前回の値を返します。
つまずきやすいところ
外部の状態に依存する関数をメモ化すると壊れます。現在時刻を読む、データベースを見る、乱数を使う関数は、同じ引数でも結果が変わってよい関数なので、古い値を返し続けることになります。もうひとつは記録の際限ない増加で、引数の種類が多い関数を上限なしでメモ化するとメモリを食い尽くします。上限付きのキャッシュにして古いものから捨てる設計が要ります。リストや辞書は鍵にできないため、タプルへ変換する手間も忘れがちな点です。
似た用語との違い
| 手法 | 中身 |
|---|---|
| メモ化 | 呼ばれた引数と結果を記録し、再利用する |
| 動的計画法 | 小さい問題から表を埋めて答えを組み立てる |
| キャッシュ | 計算に限らず、取得結果全般を一時的に保存する |
メモ化は上から呼び出しながら記録するのに対し、動的計画法は下から順に表を埋めます。求める答えは同じで、埋める順番だけが違います。
覚え方
計算を速くするのではなく、同じ計算を二度しないだけ。速くなる理由は工夫ではなく省略にあります。
