首页 » 编写高质量代码:改善JavaScript程序的188个建议 » 编写高质量代码:改善JavaScript程序的188个建议全文在线阅读

《编写高质量代码:改善JavaScript程序的188个建议》建议66:使用函数实现历史记录

关灯直达底部

函数可以利用对象去记住先前操作的结果,从而能避免无谓的运算,这种优化称为记忆。JavaScript的对象和数组要实现这种优化是非常方便的。

例如,使用递归函数计算fibonacci数列。一个fibonacci数字是之前两个fibonacci数字之和。最前面的两个数字是0和1。


var fibonacci=function(n){

return n<2?n:fibonacci(n-1)+fibonacci(n-2);

};

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

document.writeln('<br>'+i+':'+fibonacci(i));

}


返回下列值:


0:0

1:1

2:1

3:2

4:3

5:5

6:8

7:13

8:21

9:34

10:55


在上面代码中,fibonacci函数被调用了453次,其中循环调用了11次,它自身调用了442次,去计算可能已刚计算过的值。如果使该函数具备记忆功能,就可以显著减少它的运算次数。

先使用一个临时数组保存存储结果,存储结果可以隐藏在闭包中。当函数被调用时,先看是否已经知道存储结果,如果已经知道,就立即返回这个存储结果。


var fibonacci=(function{

var memo=[0,1];

var fib=function(n){

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+=1){

document.writeln('<br>'+i+':'+fibonacci(i));

}


这个函数返回同样的结果,但它只被调用了29次,其中循环调用了11次,它自身调用了18次,去取得之前存储的结果。当然,可以把这种函数形式抽象化,以构造带记忆功能的函数。memoizer函数将取得一个初始的memo数组和fundamental函数。memoizer函数返回一个管理memo存储和在需要时调用fundamental函数的shell函数。memoizer函数传递这个shell函数和该函数的参数给fundamental函数。


var memoizer=function(memo,formula){

var recur=function(n){

var result=memo[n];

if(typeof result!=='number'){

result=formula(recur,n);

memo[n]=result;

}

return result;

};

return recur;

};


现在,就可以使用memoizer来定义fundamental函数,提供初始的memo数组和fundamental函数。


var fibonacci=memoizer([0,1],function(recur,n){

return recur(n-1)+recur(n-2);

});


通过设计能产生其他函数的函数,可以极大地减少一些不必要的工作。例如,要产生一个可记忆的阶乘函数,只需提供基本的阶乘公式即可。


var factorial=memoizer([1,1],function(recur,n){

return n*recur(n-1);

});