今天在做一個(gè)樹(shù)形結(jié)構(gòu)計(jì)算時(shí)使用了遞歸废菱，使用js計(jì)算抖誉，樹(shù)一旦比較大了衰倦，頁(yè)面經(jīng)程宦卡頓樊零，后來(lái)調(diào)試發(fā)現(xiàn)問(wèn)題出在遞歸函數(shù)上，后來(lái)給每個(gè)葉節(jié)點(diǎn)加了計(jì)算緩存才算解決了問(wèn)題驻襟。
為了弄明白究竟慢在哪里，自己做了個(gè)實(shí)驗(yàn)塑悼，以簡(jiǎn)單的斐波那契數(shù)列為例,先定義一個(gè)簡(jiǎn)單函數(shù)
f=function(n){
return n<2?n:f(n-1)+f(n-2);
}
再定義一個(gè)時(shí)間計(jì)算函數(shù)
time=function(func){
function dofunc(n){
var t1=new Date();
var r=func(n);
var t2=new Date();
console.log((t2-t1)+'ms');
return r;
}
return dofunc
}
好了現(xiàn)在看看運(yùn)行時(shí)間
| 命令 ftime=time(f) | 結(jié)果 | 時(shí)間 |
|---|---|---|
| ftime(30) | 832040 | 1369ms |
| ftime(31) | 1346269 | 2199ms |
| ftime(32) | 2178309 | 3533ms |
| ftime(33) | 3524578 | 5884ms |
再往上去厢蒜，我這電腦已經(jīng)扛不住了，居然只能算到30左右斑鸦。。巷屿。
如果加個(gè)緩存試試呢
重新定義一個(gè)帶緩存的ff函數(shù)
ff=function(){
mem=[0,1];
function f(n){
var r=mem[n];
if(typeof(r)!='undefined'){
return r;
}else{
mem[n]=f(n-2)+f(n-1)
return mem[n];
}
}
return f
}()
再來(lái)看看運(yùn)行時(shí)間
| 命令 ftime=time(ff) | 結(jié)果 | 時(shí)間 |
|---|---|---|
| fftime(30) | 832040 | 0ms |
| fftime(300) | 2.2223224462942035e+62 | 1ms |
| fftime(1000) | 4.346655768693743e+208 | 1ms |
| fftime(3000) | Infinity | 2ms |
太出乎我的意料了墩虹，也難怪那些大公司都對(duì)算法是有要求的...
PS：后來(lái)想用快一點(diǎn)的語(yǔ)言會(huì)不會(huì)好些嘱巾，于是用python測(cè)試了一下性能诫钓，發(fā)現(xiàn)也就是比js快個(gè)3、4倍的樣子菌湃，不過(guò)遇到這樣指數(shù)級(jí)的問(wèn)題，光靠語(yǔ)言間的快慢是無(wú)法解決的惧所，C/C++大拿不要嘲笑，我確實(shí)不會(huì)下愈。。势似。
