3 min read

Memoization

What is memoization?

Memoization 是一种优化技术,缓存一些消耗性能的函数执行后的结果,以便在下次使用相同的参数调用相同函数时立即返回结果

许多编程语言中都有实现。

Memoization 是使 递归 / 迭代函数 运行得更快的编程实践。

它在递归函数中特别有用,因为在递归时调用更可能使用相同的参数调用。以递归 factorial 函数为例:

function factorial(num) {
if (num === 1) {
return 1;
}
return num * factorial(num - 1);
}

如果我们调用 factorial(3) 的函数,会连续调用 factorial(3)、factorial(2)、factorial(1)

如果我们使这个函数有记忆性,再一次调用 factorial(3) 将直接返回已缓存的结果。

好处是,如果我们以此为基础,再次调用 factorial(4),整个递归过程会简化很多,因为之前factorial(3)已经缓存,所以不需要进一步递归,可以直接使用已缓存的结果,节省性能,加快执行速度。

一个常见的 Memoization 函数:

const memoize = (func) => {
const cache = {};
return (...args) => {
const key = JSON.stringify(...args);
if (cache[key]) return cache[key];
const val = func(...args);
cache[key] = val;
return val;
};
};

这个 Snippet 要点是:

  1. memoize func 的返回值是一个 function
  2. cache 可以缓存之前的值,因为返回的函数是一个闭包,会持久化访问变量。
  3. 整个 memoize 函数必须为一个纯函数

常见的 memoization 优化主要用于递归:

const memoFactorial = memoize((num) => {
console.log('working for factorial(' + num + ')');
if (num === 1) {
return 1;
}
return num * memoFactorial(num - 1);
});
console.log(memoFactorial(3));
console.log(memoFactorial(4));
console.log(memoFactorial(4));

要点:

  1. memoFactorial 函数以递归方式调用自身的 memoized 版本。
  2. memoized 函数缓存了之前阶乘的值,这显着提升了性能
    • 就像这样: factorial(6) = 6 * factorial(5)

最后

React 在 16.6 推出了新的 API: memo

借鉴了 Memoization 的思想。

简单地说 memo 是一个高阶函数,在纯函数组件中使用类似于之前 PureComponent 的行为,浅比较 props 的改变来决定是否 rerender

const ToTheMoonComponent = React.memo(function MyComponent(props) {
// only renders if props have changed
});

PureComponent works with classes. React.memo() works with functional components.

Reference

Memoization - Wikipedia