函数记忆是指将上一次的计算结果存储起来，当下一次调用的时候，如果还是相同的参数的话，就直接返回存储的结果。

例子

// 来自《javascript 权威指南》
function (a, b) {
    return a + b;
}
const memoize = memoize(add);
memoize(1, 2); // 3
memoize(1, 2); // 3 （上一次的结果，而非重新计算）

原理

实现一个这样的函数很简单，原理上只要把参数和对应的结果数据存到一个对象上，调用时，判断参数对应的数据是否存在，存在的话就直接返回。

第一版

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

测试一下

const add = function (a, b, c) {
    return a + b + c;
};
const memoizedAdd = memoize(add);
console.time("use memoize");
for (let i = 0; i < 100000; i++) {
    memoizedAdd(1, 2, 3);
}
console.timeEnd("use memoize");
console.time("not use memoize");
for (let i = 0; i < 100000; i++) {
    add(1, 2, 3);
}
console.timeEnd("not use memoize");

在 Node 中测试，使用 memoize 大约消耗 60 ms，如果不使用函数记忆，大约耗时 1.5 ms。

可以看出函数记忆也不是万能的，在这个简单的场景，其实并不适合函数记忆。

函数记忆只是一种编程技巧，本质上是牺牲算法的空间的复杂度以换取更优的时间复杂度。

第二版

在第一版中使用了 join 方法，很容易想到参数是对象时，就会自动调用 toString 方法转换成 [Object object] ，再拼接字符串作为 key 值。

例子

const propValue = function (obj) {
    return obj.value;
};
const memoizedAdd = memoize(propValue);
console.log(memoizedAdd({value: 1})); // 1
console.log(memoizedAdd({value: 2})); // 1

为了解决这个问题重新写一版。

// 来自 underscore
const memoize = function (func, hasher) {
    const memoize = function (key) {
        const cache = memoize.cache;
        const address = "" + (hasher ? hasher.apply(this, arguments) : key);
        if (!cache[address]) {
            cache[address] = func.apply(this, arguments);
        }
        return cache[address];
    };
    memoize.cache = {};
    return memoize;
};

可以看出 underscore 使用函数的第一个参数作为 key，这样肯定是有问题的。

例子

const add = function (a, b, c) {
    return a + b + c;
};
const memoizedAdd = memoize(add);
memoizedAdd(1, 2, 3); // 6
memoizedAdd(1, 2, 4); // 6

如果需要支持多参数，需要传入 hasher 函数。自定义存储 key 值，考虑使用 JSON.stringify。

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, 4)); // 7

使用 JSON.stringify，如果参数是对象的话也开以得到解决，因为存储的是对象序列化后的字符串。

场景

以斐波那契数列为例

let count = 0;
const fibonacci = function (n) {
    count++;
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
for (let i = 0; i <= 10; i++) {
    fibonacci(i);
}
console.log(count); // 453

最后的 count 为 453，说明了 fibonacci 函数调用了 453 次，循环也就 11 次而已，为啥会调用这么多次了？

具体分析

当执行 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(3) 本身这一次，共 3 + 5 + 1 = 9 次。

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

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

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

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

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

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

执行次数：1 + 1 + 3 + 5 + 9 + 15 + 25 + 41 + 109 + 177 = 453 次

函数记忆

let count = 0;
let fibonacci = function (n) {
    count++;
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
fibonacci = memoize(fibonacci);
for (let i = 0; i <= 10; i++) {
    fibonacci(i);
}
console.log(count); // 12

结果为 12 次，那为什么是 12 次了？明明循环也就 11 次。

其实很简单当执行 fibonnacci(2) 时，相当于 fibonacci(1) + fibonacci(0)，因为 fibonacci(0) 的值为 0， !cache[address] 的结果为 true，所以又会执行一次 fibonacci 函数。多出的那一次就在这里。

最后

函数记忆适用于需要大量重复计算或者大量计算又依赖之前的结果的场景。当遇到类似的场景就应该想到函数记忆。

参考：

[1] JavaScript专题之函数记忆