IT 技書の森

メモ化

関数の計算結果をキャッシュし、同じ引数での再計算を避ける最適化手法

パフォーマンス最適化

メモ化とは

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

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

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

// ❌ メモ化なし: O(2^n) - fib(40) で約 1.2 秒
function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// ✅ メモ化あり: O(n) - fib(40) で 0.01ms 未満
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) の場合、メモ化なしでは約 3.3 億回の関数呼び出しが発生する。メモ化ありでは 40 回で済む。計算量が 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 でキーを生成しているため、引数がオブジェクトの場合はプロパティの順序に注意が必要だ。WeakMap を使えばオブジェクト引数のメモリリークを防げる。

React でのメモ化

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

useMemo - 計算結果のメモ化

const sortedItems = useMemo(
  () => items.sort((a, b) => a.price - b.price),
  [items]  // items が変わらない限り再計算しない
);

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 (user) が変わらない限り再レンダリングしない

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

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

メモ化のオーバーヘッド

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

React の useMemo も同様だ。依存配列の比較コストが再計算コストを上回る場合、useMemo は逆効果になる。「まず計測し、ボトルネックが確認できたらメモ化する」が正しいアプローチだ。

Lambda でのメモ化

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

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

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

関連用語