Memoization

[nanyang24]

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;
    }
}

这段 code 的要点是：

1. memoize 函数的 返回值是一个 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