javaScript之函数记忆

发表于 更新于 阅读次数：

函数记忆

定义

函数记忆是指将上次的计算结果缓存起来，当下次调用时，如果遇到相同的参数，就直接返回缓存中的数据 。
举个例子

1
2
3
4
5
6
7
8
9
function add(a, b) {
    return a + b;
}

// 假设 memorize 可以实现函数记忆
    var memoizedAdd = memoize(add);

    memoizedAdd(1, 2); //3
    memoizedAdd(1, 2) // 相同的参数，第二次调用的时候，从缓存中取出数值，而非重新计算一次

原理

实现这样一个 memoize 函数很简单，原理上制用把参数和对应的结果数据存到一个对象中，使用时，判断参数对应的数据是否存在，存在就返回对应的结果数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
    var cache = {};
    return function(){
        // 形式  "1fn..."
        var key = arguments.length + Array.prototype.join.call(arguments, ",");
        if(key in cache) {
            return cache[key]
        }
        else {
            return cache[key] = f.apply(this, arguments)
        }
    }
}

这里来测试一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var add = function(a, b, c) {
    return a + b + c;
}
var memoizedAdd = memoize(add)

console.time(`use memoize`)
for(var i = 0; i < 100000; i ++){
    memoizedAdd(1, 2, 3);
}
console.timeEnd('use memoize')

console.time('not use memoize')
for(var i = 0; i < 100000; i++) {
    add(1, 2, 3)
}
console.timeEnd('not use memoize')

// use memoize: 56.51806640625ms
// not use memoize: 1.68310546875ms

在Chrome中，使用memoize大约耗时60ms，如果没有使用memoize函数记忆，大约耗时1.3ms左右。

注意

怎么我们使用了函数记忆，结果却更加耗时？ 所以，记忆函数不是万能的，你看这个简单的场景，其实并不适合用函数记忆。

需要注意的是，函数记忆只是一种编程技巧，本质上是牺牲算法的空间复杂度以换取更优的时间复杂度，在客户端JavaScript中代码的执行时间复杂度往往成为瓶颈，因此在大多数场景下，这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。

第二版

因为第一版使用了join方法，我们很容易想到当参数是对象的时候，就会自动调用toString方法转换成[object Object]， 在拼接字符串作为key值。下面是个demo来验证一下这个问题：

1
2
3
4
5
6
7
var propValue = function(obj) {
    return obj.value
}
var memoizedAdd = memoize(propValue)

console.log(memoizedAdd({value: "a"})) // a
console.log(memoizedAdd({value: 1})) // a

两者都返回了 a, 这显然是有问题的，所以我们来看看 underscore 的 memoize函数如何实现的：

1
2
3
4
5
6
7
8
9
10
11
12
13
var memoize = function(func, hasher) {
    memoize.cache = {};
    var memoize = function(key){
        var cache = memoize.cache;
        var address = "" + (hasher ? hasher.apply(this, arguments) : key);
        if(!cache[address]){
            cache[address] = func.apply(this, arguments);

        }
        return cache[address];
    }
    return memoize;
}

从这个实现可以看出，underscore默认使用function的第一个参数作为key，所以如果直接使用是有问题的

1
2
3
4
5
6
7
8
var add = function(a, b, c) {
    return a + b + c;
}

var memoizedAdd = memoize(add);

memoizedAdd(1, 2, 3); // 6
memoizedAdd(1, 2, 4);// 6

因为第一参数相同，所以memoize会把这两使用当成同一个，第二次直接返回了缓存的值。
所以，如果要支持多参数，我们就要传入hasher函数，自定义存储的key值，可以考虑使用JSON.stringify:

1
2
3
4
5
6
7
8
9
10
var hasher = function() {
    var args = Array.prototype.slice.call(arguments);
    return JSON.stringify(args);
}
var memoizedAdd = memoize(Add, hasher);

console.log(memoizedAdd(1, 2, 3));
// address => "[1,2,3]"
console.log(memoizedAdd(1, 2, 4));
// address => "[1,2,4]"

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

使用场景

我们以斐波那契额数列为例：

1
2
3
4
5
6
7
8
9
10
11
var count = 0;
var fibonacci = function(n) {
    count++;
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

for(var i = 0; i <= 10; i++) {
    fibonacci(i);
}

console.log(count); // 453

我们会发现最后count数为453，也就是说fibonacci函数被调用了453次，我们只是循环了10次为什么会调用这么多次呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
当执行 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(4) 本身这一次，共 5 + 3 + 1 = 9 次

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

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

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

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

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

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

所以总会执行： 177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 次！

如果使用记忆函数呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
var count = 0;
var fibonacci = function(n) {
    count++;
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

fibonacci = memoize(fibonacci)

for (var i = 0; i <= 10; i++) {
    fibonacci(i)
}

console.log(count) // 11

我们会发现最后的总次数为11次，因为使用了函数记忆，调用次数从453降到11次！

温馨提示

也许在日常开发中用不到fibonaci，这个例子感觉使用价值不高，其实，这个例子是用来表明一种使用场景，也就是如果需要大量重复的计算，或者大量计算又依赖于之前的结果，便可以考虑使用函数记忆。

使用场景

最大公约数(GCD)

1
2
3
4
5
6
function gcd(a, b) {
    var temp;
    if(a < b) tempb=b, b=a, a=temp;
    while(b != 0) temp=b, b=a%b, a=temp;
    return a;
}

阶层(factorial)

1
2
3
function factorial(n) {
    return (n <= 1) ? 1 : n * factorial(n-1);
}

可能都是些偏向数学的解决。但是扩展了思路，在遇到动态规划的问题时，更难想到优化点，比如很典型的上楼梯一次可以一步或者两部，问上10级有多少种走法，其实就有那么一些fibonacci的味道在里面。