Skip to content

在JavaScript中如何使用记忆化?

什么是记忆化?

记忆化是一种常用的技术,可以显著加快代码的运行速度。它依赖于一个缓存来存储先前完成的工作单元的结果。缓存的目的是避免重复执行相同的工作,从而加快后续调用耗时函数的速度。

使用记忆化的条件

根据其定义,我们可以很容易地推断出一些条件,帮助我们发现适合记忆化的好候选函数:

  • 执行缓慢、代价高或耗时较长的函数调用可以从记忆化中受益
  • 记忆化加速后续调用,因此最好在预期在相同情况下多次调用相同函数时使用
  • 结果存储在内存中,因此当在非常不同的情况下多次调用相同函数时,应避免使用记忆化

记忆化一个函数

在JavaScript中,编写自己的记忆化函数非常简单。对于这个实现,我们将使用一个Map来存储结果。Map对象保存键值对并记住键的原始插入顺序。这使得它非常适合记忆化,因为我们可以使用函数的参数作为键,使用结果作为值。

const memoize = fn => {
  const cache = new Map();
  const cached = function (val) {
    return cache.has(val)
      ? cache.get(val)
      : cache.set(val, fn.call(this, val)) && cache.get(val);
  };
  cached.cache = cache;
  return cached;
};

// 这个函数执行缓慢,将受益于记忆化
const anagrams = str => {
  if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str];
  return str
    .split('')
    .reduce(
      (acc, letter, i) =>
        acc.concat(
          anagrams(str.slice(0, i) + str.slice(i + 1)).map(val => letter + val)
        ),
      []
    );
};

```js
const anagramsCached = memoize(anagrams);

anagramsCached('javascript');
// 花费很长时间
anagramsCached('javascript');
// 由于已经缓存,返回几乎立即完成

使用代理对象进行记忆化

虽然前面的例子是实现记忆化的一种好方法,但是JavaScript的代理对象提供了一种有趣的替代方案,通过使用handler.apply()陷阱。

使用陷阱,我们可以拦截函数调用并检查结果是否已经缓存。如果已经缓存,我们返回缓存的结果。如果没有缓存,我们调用原始函数并在返回之前缓存结果

const memoize = fn => new Proxy(fn, {
  cache: new Map(),
  apply (target, thisArg, argsList) {
    let cacheKey = argsList.toString();
    if(!this.cache.has(cacheKey))
      this.cache.set(cacheKey, target.apply(thisArg, argsList));
    return this.cache.get(cacheKey);
  }
});

const fibonacci = n => (n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2));
const memoizedFibonacci = memoize(fibonacci);

for (let i = 0; i < 100; i ++)
  fibonacci(30);                      // ~5000ms
for (let i = 0; i < 100; i ++)
  memoizedFibonacci(30);              // ~50ms