Memorized Function

CodecWang

发布于 2022-06-29 11:22:20

4910

发布于 2022-06-29 11:22:20

文章被收录于专栏：CodecWang

Author: CodecWang
Date: 2022/06/04

记忆化

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

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

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

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

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

如果我们还想计算 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];
}Copy to clipboardErrorCopied

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

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

记忆化函数

但此时的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));Copy to clipboardErrorCopied

这里定义了一个高阶函数（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;Copy to clipboardErrorCopied

原理基本类似，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);Copy to clipboardErrorCopied