JS Funtions 中的记忆化（memoization）

记忆化（memoization）是一种提高计算机程序执行速度的优化技术，通过存储大量计算量函数的返回值，当这个结果再次使用时不需要重新计算，而是从缓存中直接取出。

JavaScript 的对象和数组要实现这种优化是非常方便的。

比如，斐波那契数列（Fibonacci，前面两项之和等于后一项的值），常见的写法如下：

const fibonacci = n => {
  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n-2);
};

for (let i = 0; i <= 10; i++) {
  console.log(i + ': ' + fibonacci(i));
};
1
2
3
4
5
6
7

这样实现的方法，做了很多重复性的工作，fibonacci 函数被调用了 453 次，其中 for 循环调用了 11 次，而它自己调用了 442 次。如果引入记忆功能，见可以显著地减少运算量。

Fibonacci 记忆化的实现

使用一个 memo 的数组储存计算结果：

const fibonacci = function () {
	let memo = [0, 1];
	const fib = n => {
		let result = memo[n];
		if (typeof result !== 'number') {
			result = fib(n-1) + fib(n-2);
			memo[n] = result;
		}
		return result;
	};
	return fib;
}();
1
2
3
4
5
6
7
8
9
10
11
12

fibonacci 函数被调用了 29 次，其中 for 循环调用了 11 次，自己调用了18 次去取的之前存储的结果。相比较传统的方法，极大地减少了运算量。

延伸：带记忆功能函数的构造器

我们可以把上面的这种技术推广一下，编写一个函数用于构造带记忆功能的函数。

const memoizer = (memo, formula) => {
  const recur = n => {
    let result = memo[n];
    if (typeof result !== 'number') {
      result = formula(recur, n);
      memo[n] = result;
    }
    return result;
  };
  return recur;
};
1
2
3
4
5
6
7
8
9
10
11

现在，可以使用 memoizer 函数来构造 fibonacci 函数，只需提供初始的 memo 数组和 formula 函数：

const fibonacci = memoizer([0, 1], function (recur, n) {
	return recur(n-1) + recur(n-2);
});
1
2
3

通过设计这种生产另一个函数的函数，可极大地减少我们的工作量。例，要产生一个可记忆的阶乘函数，只需要提供基本的阶乘公式即可：

const factorial = memoizer([1, 1], function (recur, n) {
  return n * recur(n-1);
});
1
2
3

---

参考自：《JavaScript语言精粹》