Skip to main content

Memorized Function

· 5 min read
Arthur

记忆化​

记忆化 Memorization（简写 memo），是一种提高程序执行速度的优化技术，简单来说就是把需要重复计算的结果缓存在内存中，下次要用时直接取出来就行，不用再计算一次，属于典型的空间换时间的优化方案，通常会用在有大计算量或者递归、循环应用等一些场景。

举例来说，对于阶乘，通常会使用递归来实现：

function factorial(n) {
  return n === 1 ? 1 : n * factorial(n - 1);
}

现在，5 的阶乘就可以这样调用：

factorial(5) = 5! = 5 * 4 * 3 * 2 * 1 = 120;

如果我们还想计算 6 的阶乘呢，factorial(6) = 6 * factorial(5)，此时又会计算一次 5 的阶乘，这显然是多余的一次计算量。

缓存​

全局缓存​

要解决这个问题，最简单的方式就是在外层定义一个缓存：

const cache = [1, 1];
function factorial(n) {
  if (!cache[n]) cache[n] = n * factorial(n - 1);
  return cache[n];
}

加入缓存后性能得到了大幅提升：

console.time();
for (let i = 1; i < 1000; i++) {
  factorial(i);
}
console.timeEnd();
// 普通阶乘：10.355ms
// 加入缓存：0.231ms

记忆化函数​

但此时的cache缓存变量一来是定义在全局对象上的，二来是为阶乘这个函数量身定制的，并不能用在其他地方。此时就需要利用闭包（Closure）来创建一个可访问局部变量的函数：

function memo() {
  const cache = [1, 1];

  function factorial(n) {
    if (!cache[n]) cache[n] = n * factorial(n - 1);
    return cache[n];
  }
  return factorial;
}

const factorial = memo();
console.log(factorial(5));

这里定义了一个高阶函数（HOC），在里面定义了闭包factorial，这样就能访问memo函数的局部缓存变量cache。lodash 中也提供了memoize方法，源码如下：

function memoize(func, resolver) {
  if (
    typeof func !== "function" ||
    (resolver != null && typeof resolver !== "function")
  ) {
    throw new TypeError("Expected a function");
  }
  const memoized = function (...args) {
    const key = resolver ? resolver.apply(this, args) : args[0];
    const cache = memoized.cache;

    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = func.apply(this, args);
    memoized.cache = cache.set(key, result) || cache;
    return result;
  };
  memoized.cache = new (memoize.Cache || Map)();
  return memoized;
}

memoize.Cache = Map;

export default memoize;

原理基本类似，lodash 同样创建了一个内部函数memoized，不同的是它把局部缓存数据cache放到了这个memoized函数上面，这样做的好处就是外界可以直接访问并修改缓存。借鉴该方式，简单改造我们的阶乘函数：

function memo() {
  function factorial(n) {
    const cache = factorial.cache;
    if (!cache[n]) cache[n] = n * factorial(n - 1);
    return cache[n];
  }
  factorial.cache = [1, 1];
  return factorial;
}

const fact = memo();
// 这样就可以在外部直接访问或修改缓存
console.log(fact(5), fact.cache);

不要滥用​

记忆化是使用空间换取时间，并且数据会存储在内存中，因此不能滥用以免导致内存消耗过大，需要在内存占用与执行速度间做个平衡，通常可用于频繁调用的大计算量场景。如果大家使用 Redux 的话，可能会碰到 reselect，它就是通过创建一个记忆化的选择器来优化性能。

课后题：https://github.com/lydiahallie/javascript-questions#78-what-is-the-output

引用​