JavaScript学习笔记之函数记忆
本文讲解函数记忆与菲波那切数列的实现，分享给大家，具体如下
定义
函数记忆是指将上次的计算结果缓存起来，当下次调用时，如果遇到相同的参数，就直接返回缓存中的数据。
举个例子：
functionadd(a,b){
returna+b;
}
//假设memorize可以实现函数记忆
varmemoizedAdd=memorize(add);
memoizedAdd(1,2)//3
memoizedAdd(1,2)//相同的参数，第二次调用时，从缓存中取出数据，而非重新计算一次
原理
实现这样一个memorize函数很简单，原理上只用把参数和对应的结果数据存到一个对象中，调用时，判断参数对应的数据是否存在，存在就返回对应的结果数据。
第一版
我们来写一版：
//第一版(来自《JavaScript权威指南》)
functionmemoize(f){
varcache={};
returnfunction(){
varkey=arguments.length+Array.prototype.join.call(arguments,",");
if(keyincache){
returncache[key]
}
elsereturncache[key]=f.apply(this,arguments)
}
}
我们来测试一下：
varadd=function(a,b,c){
returna+b+c
}
varmemoizedAdd=memorize(add)
console.time('usememorize')
for(vari=0;i<100000;i++){
memoizedAdd(1,2,3)
}
console.timeEnd('usememorize')
console.time('notusememorize')
for(vari=0;i<100000;i++){
add(1,2,3)
}
console.timeEnd('notusememorize')
在Chrome中，使用memorize大约耗时60ms，如果我们不使用函数记忆，大约耗时1.3ms左右。
注意
什么，我们使用了看似高大上的函数记忆，结果却更加耗时，这个例子近乎有60倍呢！
所以，函数记忆也并不是万能的，你看这个简单的场景，其实并不适合用函数记忆。
需要注意的是，函数记忆只是一种编程技巧，本质上是牺牲算法的空间复杂度以换取更优的时间复杂度，在客户端JavaScript中代码的执行时间复杂度往往成为瓶颈，因此在大多数场景下，这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。
第二版
因为第一版使用了join方法，我们很容易想到当参数是对象的时候，就会自动调用toString方法转换成[Objectobject]，再拼接字符串作为key值。我们写个demo验证一下这个问题：
varpropValue=function(obj){
returnobj.value
}
varmemoizedAdd=memorize(propValue)
console.log(memoizedAdd({value:1}))//1
console.log(memoizedAdd({value:2}))//1
两者都返回了1，显然是有问题的，所以我们看看underscore的memoize函数是如何实现的：
//第二版(来自underscore的实现)
varmemorize=function(func,hasher){
varmemoize=function(key){
varcache=memoize.cache;
varaddress=''+(hasher?hasher.apply(this,arguments):key);
if(!cache[address]){
cache[address]=func.apply(this,arguments);
}
returncache[address];
};
memoize.cache={};
returnmemoize;
};
从这个实现可以看出，underscore默认使用function的第一个参数作为key，所以如果直接使用
varadd=function(a,b,c){
returna+b+c
}
varmemoizedAdd=memorize(add)
memoizedAdd(1,2,3)//6
memoizedAdd(1,2,4)//6
肯定是有问题的，如果要支持多参数，我们就需要传入hasher函数，自定义存储的key值。所以我们考虑使用JSON.stringify：
varmemoizedAdd=memorize(add,function(){
varargs=Array.prototype.slice.call(arguments)
returnJSON.stringify(args)
})
console.log(memoizedAdd(1,2,3))//6
console.log(memoizedAdd(1,2,4))//7
如果使用JSON.stringify，参数是对象的问题也可以得到解决，因为存储的是对象序列化后的字符串。
适用场景
我们以斐波那契数列为例：
varcount=0;
varfibonacci=function(n){
count++;
returnn<2?n:fibonacci(n-1)+fibonacci(n-2);
};
for(vari=0;i<=10;i++){
fibonacci(i)
}
console.log(count)//453
我们会发现最后的count数为453，也就是说fibonacci函数被调用了453次！也许你会想，我只是循环到了10，为什么就被调用了这么多次，所以我们来具体分析下：
当执行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次！
如果我们使用函数记忆呢？
varcount=0;
varfibonacci=function(n){
count++;
returnn<2?n:fibonacci(n-1)+fibonacci(n-2);
};
fibonacci=memorize(fibonacci)
for(vari=0;i<=10;i++){
fibonacci(i)
}
console.log(count)//12
我们会发现最后的总次数为12次，因为使用了函数记忆，调用次数从453次降低为了12次!
兴奋的同时不要忘记思考：为什么会是12次呢？
从0到10的结果各储存一遍，应该是11次呐？咦，那多出来的一次是从哪里来的？
所以我们还需要认真看下我们的写法，在我们的写法中，其实我们用生成的fibonacci函数覆盖了原本了fibonacci函数，当我们执行fibonacci(0)时，执行一次函数，cache为{0:0}，但是当我们执行fibonacci(2)的时候，执行fibonacci(1)+fibonacci(0)，因为fibonacci(0)的值为0，!cache[address]的结果为true，又会执行一次fibonacci函数。原来，多出来的那一次是在这里！
多说一句
也许你会觉得在日常开发中又用不到fibonacci，这个例子感觉实用价值不高呐，其实，这个例子是用来表明一种使用的场景，也就是如果需要大量重复的计算，或者大量计算又依赖于之前的结果，便可以考虑使用函数记忆。而这种场景，当你遇到的时候，你就会知道的。