【翻译】如何利用记忆化技术缓存JS函数结果并加速你的代码

How to use Memoize to cache JavaScript function results and speed up your code

函数是编程的组成部分，使我们的代码具有模块化和复用性。

用函数将我们的程序分割成块是很常见的，我们利用函数来执行一些有用的操作。

有时，多次调用一个函数会变的代价很高（比如计算一个数的阶乘）。缓存技术可以让我们优化这些程序，并且让他们执行的更快。

比如，我们有一个返回一个数阶乘的函数：

1
2
3
4
function factorial(n) {
    // Calculations: n * (n-1) * (n-2) * ... (2) * (1)
    return factorial;
}

如果我们要算factorial(50)，计算机将执行这个函数 50 次，然后返回最终结果。

当factorial(50)计算完成后，我们再来算一下factorial(51)，可能你已经发现了，前 50 次的我们已经算过，可以不用重复计算，就像这样：

1
factorial(51) = factorial(50) * 51;

但是我们的原函数不会这么想，他会在每次调用时都会从头开始执行计算：

1
factorial(51) = 51 * 50 * 49 * ... * 2 * 1

如果有一种方式，来让我们的factorial函数记住他以前计算过的结果，并且用他来加速代码的执行，是不是很有用呢？

记忆化出现了，记忆化是一种让程序记住（缓存）他以前计算过的结果的方式，这里是他的定义：

在计算机科学中，记忆化（英语：memoization 而非 memorization）是一种提高程序运行速度的优化技术。通过储存大计算量函数的返回值，当这个结果再次被需要时将其从缓存提取，而不用再次计算来节省计算时间。

记忆化简单来说就是记忆，或者存储在内存里。一个记忆化程序通常更快，因为如果随后函数调用之前的一个值，我们将从缓存中获取结果，而不是执行该函数。

这里是一个记忆化函数的例子（如果你想测试一下的话，请前往CodePen)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// a simple function to add something
const add = (n) => n + 10;
add(9);
// a simple memoized function to add something
const memoizedAdd = () => {
    let cache = {};
    return (n) => {
        if (n in cache) {
            console.log("Fetching from cache");
            return cache[n];
        } else {
            console.log("Calculating result");
            let result = n + 10;
            cache[n] = result;
            return result;
        }
    };
};
// returned function from memoizedAdd
const newAdd = memoizedAdd();
console.log(newAdd(9)); // calculated
console.log(newAdd(9)); // cached

记忆化摘要

下面是上述代码的摘要：

  • memoizedAdd返回了一个稍后调用的函数，这在 JS 里这是可能的，因为在 JS 中，函数是一类对象，可以将它们用作高顺位函数（也有译高阶函数，higher order functions）并返回另一个函数。
  • cache可以记录他的值，因为返回的函数存在于闭包（closures）之中
  • 记忆化函数应该是纯净（pure）的。一个纯净的函数对特定的输入，无论经过多少次调用，都将返回相同的输出，这让cache可以如我们的预期记录数据。

写下你自己的记忆化函数

前面的代码运行的不错，但是如何把我们自己的函数变成一个记忆化函数呢？
如何写下你自己的记忆化函数（CodePen）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// a simple pure function to get a value adding 10
const add = (n) => n + 10;
console.log("Simple call", add(3));
// a simple memoize function that takes in a function
// and returns a memoized function
const memoize = (fn) => {
    let cache = {};
    return (...args) => {
        let n = args[0]; // just taking one argument here
        if (n in cache) {
            console.log("Fetching from cache");
            return cache[n];
        } else {
            console.log("Calculating result");
            let result = fn(n);
            cache[n] = result;
            return result;
        }
    };
};
// creating a memoized function for the 'add' pure function
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3)); // calculated
console.log(memoizedAdd(3)); // cached
console.log(memoizedAdd(4)); // calculated
console.log(memoizedAdd(4)); // cached

这个简单的memoize函数将简单函数（simple functions）包装成一个记忆的等价物。这个函数在简单函数上运行良好，而且可以轻松调整，以适应任何数量的参数。另外一个方式是使用一些 de-facto 库，比如：

记忆递归函数

如果你尝试向memoize函数，或者向来自 Lodash 的_.memoize函数传递一个递归函数，结果并不会如你所料，因为其后续调用的递归函数最终将调用自身而不是记忆函数，从而不使用缓存。

所以只需确保你的递归函数也能调用记忆函数，做如下调整：CodePen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// same memoize function from before
const memoize = (fn) => {
    let cache = {};
    return (...args) => {
        let n = args[0];
        if (n in cache) {
            console.log("Fetching from cache", n);
            return cache[n];
        } else {
            console.log("Calculating result", n);
            let result = fn(n);
            cache[n] = result;
            return result;
        }
    };
};
const factorial = memoize((x) => {
    if (x === 0) {
        return 1;
    } else {
        return x * factorial(x - 1);
    }
});
console.log(factorial(5)); // calculated
console.log(factorial(6)); // calculated for 6 and cached for 5

代码中的一些需要注意的点：

  • factorial函数递归调用它自己的记忆化版本。
  • 记忆化函数获取了之前的 factorial 值，显著提高了被重用时的计算速度factorial(6) = 6 * factorial(5)

记忆化和缓存相同吗？

在某些程度上是的，记忆化实际上是一种缓存的特殊类型。缓存可以总体上指任何一种面向未来的存储技术（比如 HTTP 缓存（HTTP Caching）），而记忆化特指缓存函数返回值的技术。

什么时候记忆你的函数？

尽管看起来记忆化技术能被运用于所有函数，但是他也有一些使用的局限性：

  • 记忆化函数应该是纯净的，这样他才可以每次对相同的输入返回相同的结果。
  • 记忆是空间和速度之间的权衡，因此对于具有有限的输入范围的功能而言是重要的，以便可以更频繁地使用缓存的值
  • 看起来你应该记忆（译者注：原文如此，这里应该说缓存）你的 API 调用，但是并没有必要，因为浏览器自动帮我们做了，如 HTTP 缓存（HTTP Caching）。
  • 在我看来，高计算量程序是记忆化技术的最优应用之处，它可以帮助提高程序性能（阶乘和斐波那契不是真正好的现实例子）
  • 如果在使用 React/Redux，可以看一看reselect，它是一个记忆选择器，用来确保你的计算计算进发生在状态树的相关部分发生变化时。

扩展阅读

我希望本文对你有用，你现在一定更好的理解了 Javascript 中的记忆化技术。

原文载于 Medium 平台，原文地址[https://medium.freecodecamp.org/understanding-memoize-in-javascript-51d07d19430e]，作者[Divyanshu Maithani](https://medium.freecodecamp.org/@divyanshu013)，翻译 Mingfei Ding，转载请注明原文作者及翻译，如果版权问题请联系dmf@squirrel.tech