メモ化

メモ化とは

メモ化 (Memoization) は、純粋関数 (同じ引数に対して常に同じ結果を返す関数) の計算結果をキャッシュし、同じ引数での再呼び出し時にキャッシュから結果を返す最適化手法である。Donald Michie が 1968 年に Nature 誌の論文「"Memo" Functions and Machine Learning」で命名した。

キャッシュとの違いは粒度だ。キャッシュは HTTP レスポンスやデータベースクエリ結果など外部リソースの保存を指すことが多いが、メモ化は関数レベルの最適化に特化している。

効果が劇的な例 - フィボナッチ数列

素朴な再帰でフィボナッチ数を求めると、同じ引数に対する計算が枝分かれの先で何度も重複する。メモ化はこの重複だけを取り除く。

// ❌ メモ化なし: fib(40) で 3 億回超の再帰呼び出しが走る
function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// ✅ メモ化あり: fib(40) が 79 回の呼び出しで終わる
const cache = new Map<number, number>();
function fibMemo(n: number): number {
  if (cache.has(n)) return cache.get(n)!;
  if (n <= 1) return n;
  const result = fibMemo(n - 1) + fibMemo(n - 2);
  cache.set(n, result);
  return result;
}

fib(40) の場合、メモ化なしでは 331,160,281 回 (約 3.3 億回) の関数呼び出しが発生する。メモ化ありでは 79 回の呼び出しで終わり、キャッシュに残るのは fib(2) から fib(40) までの 39 件だけだ。素朴な再帰の呼び出し回数は 2 × F(n+1) - 1 (F はフィボナッチ数) で、実際の増加率は黄金比 (約 1.618) の n 乗である。O(2^n) はその上界を示す表記で、メモ化するとこれが O(n) になる。

汎用メモ化関数

毎回同じ書き方を繰り返さずに済むよう、任意の純粋関数をメモ化する高階関数にしておくとよい。

function memoize<T extends (...args: any[]) => any>(fn: T): T {
  const cache = new Map<string, ReturnType<T>>();
  return ((...args: Parameters<T>) => {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key)!;
    const result = fn(...args);
    cache.set(key, result);
    return result;
  }) as T;
}

const expensiveCalc = memoize((x: number, y: number) => {
  // 重い計算...
  return x * y + Math.sqrt(x);
});

JSON.stringify でキーを生成しているため、プロパティの順序が違うオブジェクトは別のキーになる ({ a: 1, b: 2 } と { b: 2, a: 1 } は別扱い)。また Map はキーと結果を持ち続けるので、引数の種類が増え続ける関数では際限なくメモリを消費する。引数が単一のオブジェクトなら、キャッシュを WeakMap にする手がある。WeakMap はキーへの参照を保持しないため、そのオブジェクトが他から参照されなくなればキャッシュも一緒に回収される。ただしキーに使えるのはオブジェクトと登録済みでないシンボルだけで、数値や文字列を引数に取る関数には使えない。

React でのメモ化

React のレンダリング最適化はメモ化の応用だ。

useMemo - 計算結果のメモ化

const sortedItems = useMemo(
  () => [...items].sort((a, b) => a.price - b.price),  // コピーしてから並べ替える
  [items]  // items が変わらない限り再計算しない
);

Array.prototype.sort は配列をその場で並べ替えてコピーを作らない。items を直接並べ替えると、渡された props や state を書き換えてしまう。上のようにコピーを取るか、toSorted が使える環境ならそちらを使う。

useCallback - 関数のメモ化

const handleClick = useCallback(
  (id: string) => dispatch({ type: 'SELECT', id }),
  [dispatch]  // dispatch が変わらない限り同じ関数参照を返す
);

useCallback は子コンポーネントに渡すコールバックに使う。関数参照が変わらなければ、React.memo でラップした子コンポーネントの再レンダリングを防げる。

React.memo - コンポーネントのメモ化

const UserCard = React.memo(({ user }: { user: User }) => (
  <div>{user.name}</div>
));
// props が変わらない限り再レンダリングしない

React.memo の判定は浅い比較だ。React は新旧の props を、プロパティごとに参照が同一かどうかで比べる。そのため親のレンダリングごとに新しいオブジェクト・配列・関数を組み立てて渡していると、中身が同じでも毎回再レンダリングされる。渡す値を useMemo / useCallback で固定するか、比較関数を第 2 引数に渡して判定を明示する。

メモ化すべきケースとすべきでないケース

判断は「同じ引数でどれだけ呼ばれるか」と「1 回の計算がどれだけ重いか」の掛け算で決まる。

判断基準	メモ化すべき	メモ化すべきでない
計算コスト	高い (ソート、フィルタ、集計)	低い (単純な四則演算)
呼び出し頻度	同じ引数で頻繁に呼ばれる	毎回異なる引数
React	重いレンダリング、大きなリスト	軽量なコンポーネント

メモ化のオーバーヘッド

メモ化にはキャッシュの管理コスト (メモリ使用量、キーの生成・比較) がある。計算コストが低い関数をメモ化すると、キャッシュ管理のオーバーヘッドの方が大きくなり、逆にパフォーマンスが悪化する。

React の useMemo も同様で、依存配列の比較と値の保持がレンダリングごとに走る。軽い計算をメモ化すると、この固定のオーバーヘッドが再計算を省いた分を上回って遅くなる。「まず計測し、ボトルネックが確認できたらメモ化する」が正しいアプローチだ。

Lambda でのメモ化

Lambda のハンドラー外で初期化した変数は、同一実行環境内で再利用される。これを利用して、DynamoDB クライアントや設定値をメモ化できる。

ただし、Lambda の実行環境はいつ破棄されるか保証されない。キャッシュが消えても正しく動作する設計にする。

メモ化を扱う関連書籍も多い。