🦊

Memoizationとは？

2024/12/11に公開

JavaScript

Memoizationとは？

Memoization（メモ化）とは、関数の結果を**キャッシュ（保存）**しておき、同じ入力値で関数が呼び出されたときに保存された値を再利用する最適化手法です。これにより、不要な繰り返し計算を避け、パフォーマンスを大幅に向上させることができます。

簡単に言えば、**「同じ質問を何度もせず、一度計算した答えを覚えておこう」**という概念です。

なぜ必要なのでしょうか？

次のような状況でMemoizationが役立ちます

複雑な計算: 繰り返し呼び出され、計算コストが高い関数。

function memoize(fn) {
  const cache = {};
  return function (...args) {
    const key = JSON.stringify(args);
    if (cache[key]) {
      console.log(`キャッシュから取得: ${key}`);
      return cache[key];
    }
    const result = fn(...args);
    cache[key] = result;
    console.log(`新しく計算: ${key}`);
    return result;
  };
}

// 複雑な計算関数（例: 2乗計算）
const expensiveCalculation = (num) => {
  console.log(`複雑な計算実行中: ${num}`);
  return num * num;
};

// メモ化適用
const memoizedExpensiveCalculation = memoize(expensiveCalculation);

// 呼び出し例
console.log(memoizedExpensiveCalculation(5)); // 新しく計算: 25
console.log(memoizedExpensiveCalculation(5)); // キャッシュから取得: 25
console.log(memoizedExpensiveCalculation(10)); // 新しく計算: 100

データリクエスト: 同じデータを要求する際にAPI呼び出しを減らし、キャッシュされたデータを再利用する。

function memoizeApi(fn) {
  const cache = {};
  return async function (...args) {
    const key = JSON.stringify(args);
    if (cache[key]) {
      console.log(`キャッシュから取得: ${key}`);
      return cache[key];
    }
    const result = await fn(...args);
    cache[key] = result;
    console.log(`新しくリクエスト: ${key}`);
    return result;
  };
}

// 仮想のAPI呼び出し関数
async function fetchData(id) {
  console.log(`API 요청: ID ${id}`);
  // 実際のAPI呼び出しの代わりにPromiseで結果を返す
  return new Promise((resolve) => setTimeout(() => resolve({ id, data: `データ ${id}` }), 1000));
}

// メモ化適用
const memoizedFetchData = memoizeApi(fetchData);

// 呼び出し例
(async () => {
  console.log(await memoizedFetchData(1)); // 新しくリクエスト: { id: 1, data: "データ 1" }
  console.log(await memoizedFetchData(1)); // キャッシュから取得: { id: 1, data: "データ 1" }
  console.log(await memoizedFetchData(2)); // 新しくリクエスト: { id: 2, data: "データ 2" }
})();

再帰呼び出しの最適化: フィボナッチ数列、ツリー探索など再帰的に動作するアルゴリズム。

function memoizedFibonacci(n, cache = {}) {
　if (n <= 1) return n; // 基本値を返す
  if (cache[n]) {
    console.log(`キャッシュから取得: F(${n}) = ${cache[n]}`);
    return cache[n];
  }
  console.log(`新しく計算: F(${n})`);
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache);
  return cache[n];
}

// 呼び出し例
console.log(memoizedFibonacci(10)); // 計算過程と共に結果を返す
console.log(memoizedFibonacci(10)); // キャッシュから直接結果を返す

フィボナッチ数列

// フィボナッチ数列 (メモ化なし)
function fibonacci(n: number): number {
  if (n <= 1) return n; // 基本ケースの処理
  return fibonacci(n - 1) + fibonacci(n - 2); // 再帰的に計算
}

// メモ化を使用したフィボナッチ数列
function memoizedFibonacci(n: number, cache: Record<number, number> = {}): number {
  if (n <= 1) return n; // 基本ケースの処理
  if (cache[n]) return cache[n]; // キャッシュを確認
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache); // 結果をキャッシュに保存
  return cache[n]; // 結果を返す
}

// 実行時間を測定する関数
function measureTime(label: string, fn: () => void) {
  console.time(label); // 実行時間の計測を開始
  fn(); // 測定対象の関数を実行
  console.timeEnd(label); // 実行時間の計測を終了
}

// 実行
console.log('メモ化なしのフィボナッチ計算:');
measureTime('Without Memoization', () => {
  console.log(fibonacci(40)); // 計算結果を出力
});

console.log('メモ化を使用したフィボナッチ計算:');
measureTime('With Memoization', () => {
  console.log(memoizedFibonacci(40)); // 計算結果を出力
});

Memoizationの仕組み

Memoizationを簡単に実装するには、以下の3つのステップで構成されます

入力値の保存: 関数が呼び出された際に、入力値をキー（key）として保存します。
結果値の保存: 入力値に対する計算結果を値（value）として保存します。
キャッシュの確認: 同じ入力値が再度渡された場合、計算を行わず、保存された結果を返します。

コード例で学ぶ

javascript

function memoize(fn) {
  const cache = new Map(); // 結果を保存するキャッシュ

  return function (...args) {
    const key = JSON.stringify(args); // 入力値をキャッシュキーに変換
    if (cache.has(key)) {
      console.log(`キャッシュから取得: ${key}`);
      return cache.get(key);
    }
    const result = fn(...args); // 新しい結果を計算
    cache.set(key, result); // キャッシュに結果を保存
    console.log(`新しく計算: ${key}`);
    return result;
  };
}

// 加算関数
const add = (a, b) => a + b;

// メモ化適用
const memoizedAdd = memoize(add);

// 呼び出し例
console.log(memoizedAdd(1, 2)); // 新しく計算: 3
console.log(memoizedAdd(1, 2)); // キャッシュから取得: 3
console.log(memoizedAdd(2, 3)); // 新しく計算: 5

TypeScript

function memoize<T extends (...args: any[]) => any>(fn: T): T {
  const cache = new Map<string, ReturnType<T>>(); // 結果を保存するキャッシュ

  return function (...args: Parameters<T>): ReturnType<T> {
    const key = JSON.stringify(args); // 入力値をキャッシュキーに変換
    if (cache.has(key)) {
      console.log(`キャッシュから取得: ${key}`);
      return cache.get(key)!; // キャッシュされた値を返す
    }
    const result = fn(...args); // 新しい結果を計算
    cache.set(key, result); // キャッシュに結果を保存
    console.log(`新しく計算: ${key}`);
    return result;
  } as T;
}

// 加算関数
const add = (a: number, b: number): number => a + b;

// メモ化適用
const memoizedAdd = memoize(add);

// 呼び出し例
console.log(memoizedAdd(1, 2)); // 新しく計算: 3
console.log(memoizedAdd(1, 2)); // キャッシュから取得: 3
console.log(memoizedAdd(2, 3)); // 新しく計算: 5

結論

メモ化関数は、TypeScriptで作成することで型の安全性を確保し、より信頼性の高いコードを記述することができます。特に、繰り返しの計算やAPI呼び出し、再帰アルゴリズムなど、パフォーマンス最適化が必要な状況で効果的に活用できます。TypeScriptの強力な型システムを利用することで、複雑なプロジェクトにおいても安全かつ効率的なコードを作成することが可能になります。

Memoizationとは？

なぜ必要なのでしょうか？

フィボナッチ数列

Memoizationの仕組み

コード例で学ぶ

javascript

TypeScript

結論

Discussion