数値キー圧縮による O(1) メモイゼーション実装
与えられた関数 fn に対し、同じ引数の組み合わせに対して再度呼び出さないメモイズ版を返します。引数の順序は意味を持ち、(a, b) と (b, a) は異なるキーとして扱います。
| 関数 | 引数 | 制約 |
|---|---|---|
sum |
a, b (2つ) | 0 ≤ a, b ≤ 105 |
fib |
n (1つ) | 1 ≤ n ≤ 10 |
factorial |
n (1つ) | 1 ≤ n ≤ 10 |
Input: fnName = "sum", actions = ["call","call","getCallCount","call","getCallCount"]
values = [[2,2],[2,2],[],[1,2],[]]
Output: [4,4,1,3,2]
Explanation:
memoizedSum(2, 2); // returns 4, sum() が呼ばれる（初回）
memoizedSum(2, 2); // returns 4, sum() は呼ばれない（キャッシュヒット）
getCallCount(); // returns 1
memoizedSum(1, 2); // returns 3, sum() が呼ばれる（新しい引数）
getCallCount(); // returns 2Map<number, number> で O(1) キャッシュ
type Fn = (...params: number[]) => number;
function memoize(fn: Fn): Fn {
// キャッシュ: 数値キー → 計算結果
const cache = new Map();
// 外部から観測される実際の関数呼び出し回数
let callCount = 0;
const memoized: Fn = function (...args: number[]): number {
// キー圧縮:
// 引数1つ → n そのもの (fib, factorial)
// 引数2つ → a * 100001 + b (sum)
// 100001 = 10^5 + 1 で、a と b の組み合わせが一意に対応
const key = args.length === 1 ? args[0] : args[0] * 100001 + args[1];
// キャッシュヒット: fn を呼び出さず結果を返す
if (cache.has(key)) {
return cache.get(key)!;
}
// キャッシュミス: fn を実行し結果を保存
callCount += 1;
const result = fn(...args);
cache.set(key, result);
return result;
};
// LeetCode の判定ハーネス側から呼ばれる拡張プロパティ
// Fn 型には収まらないため any キャスト（コア logic には影響なし）
(memoized as any).getCallCount = (): number => callCount;
return memoized;
}
フローの説明：
1. 引数受信: 関数が引数を受け取る
2. 数値キーを計算: 引数の個数に応じてキーを生成（1つなら n、2つなら a × 100001 + b）
3. キャッシュヒット判定: Map にキーが存在するか確認
4. キャッシュヒット: 既存の結果を返す（fn を呼び出さない）
5. キャッシュミス: callCount を増加し、fn を実行して結果をキャッシュに保存
6. 結果を返す: 計算またはキャッシュから取得した結果を返す
| 操作 | 時間計算量 | 空間計算量 | 備考 |
|---|---|---|---|
| キー計算 | O(1) |
O(1) |
乗算・加算のみ |
| Map ルックアップ | O(1) 平均 |
— | ハッシュテーブル |
| キャッシュ保持 | — | O(m) |
m = ユニーク引数組み合わせ数 |
| 呼び出し全体 | O(1) amortized |
O(m) |
fn の実行コストは含まない |
| 指標 | 改善前（文字列キー） | 現行（数値キー） |
|---|---|---|
| キー型 | string |
number |
| キー生成コスト | O(k) — join で新規文字列生成 | O(1) — 乗算・加算のみ |
| メモリ効率 | 文字列キー + 数値値 | 数値キー + 数値値（最小） |
| Map 型 | Map<string, number> |
Map<number, number> |
なぜ 100001 か？ b の最大値が 105 なので、異なる a で生成されるキー範囲が重ならないためには乗数が 105 + 1 = 100001 以上である必要があります。
衝突不可能性の証明: 異なる引数ペア (a₁, b₁) ≠ (a₂, b₂) が同じキーを生成しないことを示します。