Skip to main content

JavaScript 函数记忆

一、什么是函数记忆​

函数记忆指将函数上次的调用结果缓存起来，下次调用时如果遇到相同的参数，就直接返回缓存的结果。

举个例子：

function add(a, b) {
  return a + b;
}

const memoizedAdd = memoize(add);

memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数再次调用时，直接从缓存中取出数据

二、函数记忆的实现​

函数记忆只是一种编程技巧，本质上是牺牲算法的空间复杂度换取更优的时间复杂度，适用于大量重复求值的场景。

1、JavaScript 权威指南的实现​

function add(a, b, c) {
  return a + b + c;
}

/**
 * 函数记忆
 * @param fn 原函数
 * @example memoize(function)
 * @example 用于需要大量重复求值的场景，例如递归求解斐波那契数
 */
const memoize = (fn) => {
  const cache = {};
  return function () {
    const key = arguments.length + Array.prototype.join.call(arguments, ",");
    if (key in cache) {
      return cache[key]
    } else {
      return cache[key] = fn.apply(this, arguments)
    }
  }
}

const memoizedAdd = memoize(add)

console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 5)) // 8
console.log(memoizedAdd(1, 2, 3)) // 相同的参数再次调用时，直接从缓存中取出数据

这种方式使用了 join 方法，当参数是对象时会自动调用 toString 方法转成 [Object object]，再拼接字符串作为 key 值，因此这种方式不适用于参数为对象的场景，underscore 的实现可以满足这种情况 ▼

2、underscore 的实现​

function add(a, b, c) {
  return a + b + c;
}

/**
 * 函数记忆
 * @param fn 原函数
 * @param hasher 计算 key 值的函数，如果未传则直接使用 key
 * @example memoize(function, hashFunction)
 * @example 用于需要大量重复求值的场景，例如递归求解斐波那契数
 */
const memoize = (fn, hasher) => {
  const memoize = function (key) {
    // 储存变量
    const cache = memoize.cache;

    // 求 key
    // 如果传入了 hasher，则用 hasher 函数来计算 key
    // 否则用 参数 key（即 memoize 方法传入的第一个参数）当 key
    const address = '' + (hasher ? hasher.apply(this, arguments) : key);

    // 如果这个 key 还没被 hash 过（还没求过值），则多一步缓存操作
    if (!cache[address]) {
      cache[address] = fn.apply(this, arguments);
    }

    // 返回缓存的值
    return cache[address];
  };

  // cache 对象被当做 key-value 键值对，缓存中间运算结果
  memoize.cache = {};

  // 返回一个函数（经典闭包）
  return memoize;
};

const memoizedAdd = memoize(add, function () {
  const args = Array.prototype.slice.call(arguments)
  return JSON.stringify(args)
})

console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 5)) // 8
console.log(memoizedAdd(1, 2, 3)) // 相同的参数再次调用时，直接从缓存中取出数据

这种方式使用时传入 hasher 函数来自定义存储的 key 值，可以使用 JSON.stringify 解决第一种方式不支持对象的问题。

三、函数记忆的应用​

以斐波那契数列为例：

let count = 0;
function fibonacci(n) {
  count++;  // 记录 fibonacci 函数的执行次数
  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

for (var i = 0; i <= 10; i++) {
  fibonacci(i)
}
console.log(count) // 453

最后的 count 数为 453，也就是说 fibonacci 函数被调用了 453 次，分析如下：

当执行 fib(0) 时，调用 1 次

当执行 fib(1) 时，调用 1 次

当执行 fib(2) 时，相当于 fib(1) + fib(0) 加上 fib(2) 本身这一次，共 1 + 1 + 1 = 3 次

当执行 fib(3) 时，相当于 fib(2) + fib(1) 加上 fib(3) 本身这一次，共 3 + 1 + 1 = 5 次

当执行 fib(4) 时，相当于 fib(3) + fib(2) 加上 fib(4) 本身这一次，共 5 + 3 + 1 = 9 次

当执行 fib(5) 时，相当于 fib(4) + fib(3) 加上 fib(5) 本身这一次，共 9 + 5 + 1 = 15 次

当执行 fib(6) 时，相当于 fib(5) + fib(4) 加上 fib(6) 本身这一次，共 15 + 9 + 1 = 25 次

当执行 fib(7) 时，相当于 fib(6) + fib(5) 加上 fib(7) 本身这一次，共 25 + 15 + 1 = 41 次

当执行 fib(8) 时，相当于 fib(7) + fib(6) 加上 fib(8) 本身这一次，共 41 + 25 + 1 = 67 次

当执行 fib(9) 时，相当于 fib(8) + fib(7) 加上 fib(9) 本身这一次，共 67 + 41 + 1 = 109 次

当执行 fib(10) 时，相当于 fib(9) + fib(8) 加上 fib(10) 本身这一次，共 109 + 67 + 1 = 177 次

所以执行的总次数为：177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 次

使用记忆函数如下：

let count = 0;
function fibonacci(n) {
  count++;
  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

const memoize = (fn) => {
  const cache = {};
  return function () {
    const key = arguments.length + Array.prototype.join.call(arguments, ",");
    if (key in cache) {
      return cache[key]
    } else {
      return cache[key] = fn.apply(this, arguments)
    }
  }
}
fibonacci = memoize(fibonacci)

for (let i = 0; i <= 10; i++) {
  fibonacci(i)
}
console.log(count) // 11

可以看到，使用函数记忆后，执行的次数大幅度减少了。