JS程式設計建議——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次。既然所有必要的計算都在第一行代碼中完成了，那麼後兩行代碼不會産生遞歸運算，因為直接傳回了緩存中的數值。制表過程會因遞歸函數的種類不同而略有不同，但總體上具有相同的模式。