什么是memoization,你如何实现它?

Question

Accepted Answer

**Memoization** 将函数的结果缓存,并以其参数作为键,因此使用相同输入的重复调用会立即返回缓存结果,而不是重新计算。它用**内存换取速度**,仅适用于**纯**函数(相同输入→相同输出,无副作用)。

## 一个通用的 memoize 包装器

```js
function memoize(fn) {
  const cache = new Map();
  return (...args) => {
    const key = JSON.stringify(args); // build a cache key from the arguments
    if (cache.has(key)) {
      return cache.get(key);          // cache hit — skip the work
    }
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

const slowSquare = n => { /* expensive */ return n * n; };
const fastSquare = memoize(slowSquare);
fastSquare(4); // computes → 16
fastSquare(4); // cached → 16 instantly
```

## 经典应用:递归斐波那契

```js
const fib = memoize(n => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
// turns exponential O(2^n) into roughly O(n) by caching subproblems
```

## 权衡与注意事项

- **缓存键策略**:`JSON.stringify` 对函数失效,对象的键顺序很重要。对于对象参数,`WeakMap`(以引用作为键)可以避免内存泄漏。
- **无界增长**:缓存永不缩小——对于长时间运行的进程,使用 **LRU** 缓存。
- 仅在重新计算成本高且输入重复时才进行 memoization。

## 为什么这很重要

Memoization 随处可见:React 的 `useMemo`/`React.memo`、Reselect 选择器、动态规划。

其核心概念(按输入缓存纯结果)是一致的;技巧在于选择键并限制缓存大小。