讀古今文學網 > 編寫高質量代碼:改善JavaScript程序的188個建議 > 建議32:使用製表 >

建議32:使用製表

代碼所做的事情越少,它的運行速度就越快,因此,避免重複工作很有意義。多次執行相同的任務也在浪費時間。製表法通過緩存先前計算結果為後續計算所使用,避免了重複工作,這使得製表成為遞歸算法中最有用的技術。

當遞歸函數被多次調用時,重複工作很多。以下factorial函數是一個遞歸函數重複多次的典型例子。


var fact6=factorial(6);

var fact5=factorial(5);

var fact4=factorial(4);


此代碼生成3個階乘結果,factorial函數總共被調用了18次。此代碼中最糟糕的部分是,所有必要的計算已經在第一行代碼中執行過了。因為6的階乘等於6乘以5的階乘,所以5的階乘被計算了兩次。更糟糕的是,4的階乘被計算了3次。更為明智的方法是保存並重利用它們的計算結果,而不是每次都重新計算整個函數。使用製表法重寫factorial函數:


function memfactorial(n){

if(!memfactorial.cache){

memfactorial.cache={

"0":1,

"1":1

};

}

if(!memfactorial.cache.hasOwnProperty(n)){

memfactorial.cache[n]=n*memfactorial(n-1);

}

return memfactorial.cache[n];

}


使用製表法設計階乘函數的關鍵是建立一個緩存對象,此對像位於函數內部,其中預置了兩個最簡單的階乘:0和1。在計算階乘之前,先檢查緩存中是否已經存在相應的計算結果。沒有對應的緩衝值說明這是第一次計算此數值的階乘,計算完成之後結果被存入緩存之中,以備今後使用。


var fact6=memfactorial(6);

var fact5=memfactorial(5);

var fact4=memfactorial(4);


上面代碼返回3個不同的階乘值,總共只調用memfactorial函數8次。既然所有必要的計算都在第一行代碼中完成了,那麼後兩行代碼不會產生遞歸運算,因為直接返回了緩存中的數值。製表過程會因遞歸函數的種類不同而略有不同,但總體上具有相同的模式。