0%

JavaScript之函数记忆

函数记忆??我的理解就是记忆化搜索、以空间换时间,我用C++其实写的挺多的。

以经典的fibonaci为例:

1
2
3
4
5
6
7
8
9
var count = 0
var f = function(n){
count++
return n < 2 ? n : f(n - 1) + f(n - 2);
}
for(var i = 0; i <= 10; i++){
console.log(i,f(i))
}
console.log('执行次数', count)

执行结果:

1
2
3
4
5
6
7
8
9
10
11
12
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
'执行次数', 453

接下来,我们定义一个memo的数组来保存我们得储存结果,并把它隐藏在闭包中,让该函数能一直访问到这个数组,不被垃圾回收机制回收

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var count = 0
var f = function(){
var memo = [0,1];
var fib = function(n){
count++
var result = memo[n];
if(typeof result !== 'number'){
result = fib(n - 1) + fib(n - 2)
memo[n] = result
}
return result
}
return fib
}()
for(var i = 0; i <= 10; i++){
console.log(i,f(i))
}
console.log('执行次数', count)

执行结果:

1
2
3
4
5
6
7
8
9
10
11
12
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
执行次数 29

可见调用次数远远减少,分析一下,应该是从 $2^n \rightarrow n^2$.

我没用闭包写了一下,结果一样,不知道有什么区别:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var count = 0
var memo = [0,1];

var f = function(n){
count++;
var ret = memo[n];
if (typeof ret === 'number')
return ret;

return memo[n] = f(n-1) + f(n-2);
}

for(var i = 0; i <= 10; i++){
console.log(i,f(i))
}
console.log('执行次数', count)

参考链接:wclimb-JavaScript之函数记忆