前言

代碼的組織結(jié)構(gòu)和解決具體問題的思路是影響代碼性能的主要因素洛心。程序運行速度與代碼量的多少沒有必然關(guān)系儿奶。
這里討論的技術(shù)并不限于JavaScript宝与，同樣適用于其他編程語言喜滨。

循環(huán)

在大多與編程語言中捉捅，代碼的執(zhí)行時間大部分消耗在循環(huán)中，是提升性能必須關(guān)注的要點之一虽风。在JavaScript中锯梁，死循環(huán)或長時間運行的循環(huán)還會嚴重影響用戶體驗，所以必須充分重視循環(huán)的實現(xiàn)焰情。

循環(huán)的類型

在ECMA-262中定義了四種循環(huán)類型

1、for循環(huán)

for循環(huán)是最常見的循環(huán)類型剥懒。它由四部分組成：初始化内舟、前測條件、后執(zhí)行體初橘、循環(huán)體验游。如下示例：

for(var i = 0; i < 10; i++){
    doSomething();
}
// i=0,是初始化
// i<10,是前測條件
// i++是后執(zhí)行體
// {}內(nèi)是循環(huán)體

for循環(huán)的執(zhí)行順序如下：

1. 初始化
2. 前測條件判斷，true繼續(xù)執(zhí)行保檐，false結(jié)束
3. 循環(huán)體執(zhí)行
4. 后執(zhí)行體執(zhí)行耕蝉，返回2。

從for的執(zhí)行順序我們可以看出夜只，i的值在循環(huán)結(jié)束時是10.

注意：由于JavaScript中沒有塊級作用域垒在，所以var i實際可能是函數(shù)級/全局變量。所以lint檢查時扔亥，同一個函數(shù)里的兩個及以上的for循環(huán)场躯，同時定義var i時，會報'i' used outside of binding context. (block-scoped-var)錯誤旅挤。

2踢关、while循環(huán)

while循環(huán)是最簡單的循環(huán)，由前測條件和循環(huán)體組成粘茄。如下示例

var i = 0;
while（i < 10） {
    doSomething();
    i++;
}

這里i=0可以理解為初始化签舞，因為i未聲明秕脓，前測條件為false。

3儒搭、do-while循環(huán)

由循環(huán)體和后測條件組成吠架。如下示例

var i = 0;
do {
    doSomething();
} while（i++ < 10） 

在do-while循環(huán)中，至少會執(zhí)行一次循環(huán)體师妙，與其他三種有明顯的區(qū)別诵肛。

4、for-in循環(huán)

for-in循環(huán)是比較特殊的循環(huán)類型默穴。它可以遍歷一個對象的屬性/方法名怔檩。如下示例：

for(var prop in object){
    doSomething();
}

循環(huán)體每次運行時，prop會被賦值為object的一個屬性/方法名（字符串）蓄诽，直到遍歷完所有屬性/方法才結(jié)束薛训。fori-in循環(huán)遍歷的屬性/方法包括對象實例屬性/方法和原型鏈中繼承的屬性/方法。
注意：如果數(shù)組有追加屬性/方法仑氛，那么遍歷數(shù)組時就會出錯乙埃。所以編程規(guī)范中強調(diào)數(shù)組遍歷不要使用for-in

var array = [1,2,3]
for(var prop in array) {
    console.log(prop)
}
// 打印結(jié)果 1 2 3
Array.prototype.isNumber = function(){
    return true;
}
for(var prop in array) {
    console.log(prop)
}
// 打印結(jié)果 1 2 3 isNumber
var object ={
    a:1,
    b:2,
    f1:function(){}
}
for(var prop in object) {
    console.log(prop)
}
// 打印結(jié)果 a b f1

循環(huán)性能

因為for-in循環(huán)每次迭代操作都要搜索實例或原型的屬性/方法，所以其性能明顯低于其他三種循環(huán)锯岖。其他三種循環(huán)類型則沒有明顯的性能差異介袜。所以除非必要，否則避免使用for-in循環(huán)出吹。
影響循環(huán)的性能主要是如下兩個因素：

1. 每次迭代處理的事務(wù)
2. 迭代的次數(shù)

減少這兩者中一個或者全部的時間開銷遇伞，就能提升整體性能。下面分別就這兩個因素進行說明捶牢。

減少迭代工作量

如果每次循環(huán)迭代要執(zhí)行很多操作鸠珠，花很長時間，那么整個循環(huán)必然需要更多時間才能完成秋麸。
典型的循環(huán)示例如下：

for(var i=0; i < items.length; i++){
    process(items[i])
}

在上面的循環(huán)中渐排，每次迭代執(zhí)行時會產(chǎn)生如下操作：

1. 在控制條件中查找一次屬性（items.length）
2. 在控制條件中查找一次比較（i < items.length）
3. 一次比較操作，查看控制條件是否為true（i < items.length == true）
4. 一次自增操作（i++）
5. 一次數(shù)組查找（items[i]）
6. 一次函數(shù)調(diào)用 (process(items[i]))

如此簡單的循環(huán)中灸蟆，即使代碼不多驯耻，也要進行許多操作。下面我們看看炒考，如何減少迭代執(zhí)行時的操作吓歇。

減少對象成員及數(shù)組項的查找次數(shù)

例如之前提到過的局部變量替換成員函數(shù)或者屬性。這樣修改后每次控制條件中直接跟局部變量len比較票腰，而不用去讀取items.length屬性城看。

for(var i=0， len = items.length; i < len; i++){
    process(items[i])
}

倒序循環(huán)

通過點到數(shù)組的順序杏慰，減少控制條件中的查找屬性和比較操作测柠。

for(var i = items.length; i--;){
    process(items[i])
}

當(dāng)然如果實際需求對順序有要求炼鞠，就不能用此方法了。

利用數(shù)組取值結(jié)果進行條件判斷

JS在賦值時會自動返回結(jié)果轰胁，利用這個返回結(jié)果進行條件判斷谒主，從而使得條件判斷和數(shù)組取值合二為一，達到減少操作的目的赃阀。

for(var i=0, item; item = items[i]; i++){
    process(item)
}

提示：當(dāng)循環(huán)復(fù)雜度為O(n)時霎肯，減少每次迭代的工作量最有效，當(dāng)復(fù)雜度大于O(n)時榛斯，建議減少迭代次數(shù)观游。

減少迭代次數(shù)

減少迭代次數(shù)的典型方法“達夫設(shè)備（Duff's Device）”。是一種循環(huán)體展開技術(shù)驮俗，是在一次迭代中實際執(zhí)行了多次迭代的操作懂缕。示例如下（原書上的例子是錯誤的）：

var i = items.length % 8;
while(i){
    process(items[--i])
}
i = items.length
var j = Math.floor(items.length / 8)
while(j--){
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
    process(items[--i])
}

基于函數(shù)的迭代

數(shù)組forEach方法，遍歷數(shù)組的所有成員王凑，并在每個成員上執(zhí)行一次函數(shù)搪柑。示例如下：

items.forEach(function (value, index , array) {
    process(value)
})

三個參數(shù)分別是：當(dāng)前數(shù)組項的值，索引和數(shù)組本身索烹。
各大瀏覽器都原生支持該方法工碾，同時各種JS類庫也都由類似的實現(xiàn)。但由于要調(diào)用外部方法百姓，帶來了額外的開銷倚喂，所以性能比之前介紹的集中循環(huán)實現(xiàn)慢很多。

條件語句

if-else對比switch

由于各瀏覽器針對if-else和switch進行了不同程度的優(yōu)化瓣戚，很難簡單說那種方式更好，只有在判斷條件數(shù)量很大時焦读，switch的性能優(yōu)勢才明顯子库。更多的時候是從易讀性方面考慮。一般來說判斷條件較少時使用if-else更易讀矗晃，當(dāng)條件較多時switch更易讀仑嗅。

優(yōu)化if-else

同樣是使用if-else，實際也存在很大的性能差距张症。這是因為到達正確分支時仓技，所需要執(zhí)行的判斷條件數(shù)量不同造成的。主要的的優(yōu)化方法有如下幾種：

1. 最可能出現(xiàn)的條件放首位俗他。

if (value < 5) {
    //dosomthing
} else if (value >5 && value < 10) {
    //dosomthing
} else {
    //dosomthing
}

如果value大部分情況下小于5脖捻，此時只需要執(zhí)行一次條件判斷。如果value大部分大于10兆衅，那么需要執(zhí)行兩次條件判斷地沮，造成性能下降嗜浮。

2. 把if-else組織成一系列嵌套的if-else，減少每個分支達到的判斷次數(shù)摩疑。

if (value == 0) {
    return result0
} else if (value == 1) {
    return result1
}  else if (value == 2) {
    return result2
}  else if (value == 3) {
    return result3
}  else if (value == 4) {
    return result4
}  else if (value == 5) {
    return result5
} else {
    return result
}

上述條件語句最多要判斷6次危融，如果value是均勻分布的，那么必然會增加平均執(zhí)行時間雷袋。采用類似二分法的方式吉殃，進行嵌套，就可以有效減少判斷次數(shù)楷怒。改進后代碼如下：

if (value < 3) {
    if (value == 0) {
        return result0
    } else if (value == 1) {
        return result1
    } else {
        return result2
    }
} else {
    if (value == 3) {
        return result4
    } else if (value == 4) {
        return result4
    } else if (value == 5) {
        return result5
    }  else {
        return result
    }
}

此時最多判斷次數(shù)變?yōu)?次蛋勺，減少了平均執(zhí)行時間。

查找表

有時候使用查找表的方式比if-else和switch更優(yōu)率寡，特別是大量離散數(shù)值的情況迫卢。JS中可以很方便的使用數(shù)組和對象來構(gòu)建查找表。使用查找表不僅能提高性能還能答復(fù)降低圈復(fù)雜度和提高可讀性冶共，而且非常方便擴展乾蛤。
例如上面的示例改為查找表：

var results = [result0,result1,result2,result3,result4,result5,result]
return result[value]

這里示例是數(shù)值，調(diào)用函數(shù)也同樣適用捅僵，例如

var fn = {
    1: function(){/* */},
    2: function(){/* */},
    3: function(){/* */}
}
fn[value]()

遞歸

遞歸可以把復(fù)雜的算法變得簡單家卖。很多傳統(tǒng)算法就是用遞歸實現(xiàn)的，例如階乘函數(shù)：

function factorial (n) {
    if (n == 0) {
        return 1
    } else {
        return n * factorial(n -1)
    }
}

但是遞歸函數(shù)存在著終止條件不明確或缺少終止條件庙楚，導(dǎo)致函數(shù)長時間運行上荡，使得用戶界面處于假死狀態(tài)。而且遞歸還可能遇到瀏覽器的“調(diào)用棧大小限制（Call stack size limites）”馒闷。所以需要慎用酪捡。

調(diào)用棧限制

JS引擎支持的遞歸數(shù)量與JS調(diào)用棧大小直接相關(guān)。只有IE的調(diào)用棧與系統(tǒng)空閑內(nèi)存有關(guān)纳账，其他瀏覽器都是固定數(shù)量的調(diào)用棧限制逛薇。需要注意的是各瀏覽器和版本調(diào)用棧數(shù)量大小差別很大。
當(dāng)使用太多的遞歸（或者死循環(huán)）疏虫，甚至超過最大調(diào)用棧限制時永罚，就會出現(xiàn)調(diào)用棧異常。各瀏覽器報錯信息如下：

IE: Stack overflow at line x
Firefox: Too much recursion
Safari: Maximum call stack size exceeded
Opera: Abort (control stack overflow)
Chrome: 不顯示調(diào)用棧溢出錯誤

同時各瀏覽器對該錯誤的處理方式也是不同的卧秘，請直接看書中描述呢袱，這里不再贅述。

遞歸模式

遞歸有兩種模式：

1. 函數(shù)調(diào)用自身翅敌，如之前說的階乘羞福。
2. 隱伏模式，即循環(huán)調(diào)用蚯涮。A調(diào)用B坯临，B又調(diào)用A焊唬，形成了無限循環(huán)，很難定位看靠。
   由于遞歸的這些隱藏危害赶促，建議使用迭代、Memoization替代挟炬。

迭代

任何遞歸實現(xiàn)的算法鸥滨，同樣可以使用迭代來實現(xiàn)。迭代算法通常包含幾個不同的循環(huán)谤祖，分別對應(yīng)計算過程的不同方面婿滓，這也會引入他們自身的性能問題。然而粥喜，使用優(yōu)化后的循環(huán)替代長時間運行的遞歸函數(shù)可以提升性能凸主。
以合并排序算法為例

function merge(left, right) {
  var result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left).concat(right);
}
function mergeSort(items) {
  if (items.length == 1) {
    return items;
  }
  var middle = Math.floor(items.length / 2),
    left = items.slice(0, middle),
    right = items.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

此算法中mergeSort存在頻繁的遞歸調(diào)用，當(dāng)數(shù)組長度為n時额湘，最終會調(diào)用2*n-1次卿吐，很容易造成棧溢出錯誤。
使用迭代改進此算法锋华。mergeSort代碼如下：

function mergeSort(items) {
  if (items.length == 1) {
    return items;
  }
  var work = [];
  for (var i = 0, len = items.length; i < len; i++) {
    work.push([items[i]]);
  }
  work.push([]); //in case of odd number of items
  for (var lim = len; lim > 1; lim = (lim + 1) / 2) {
    for (var j = 0, k = 0; k < lim; j++ , k += 2) {
      work[j] = merge(work[k], work[k + 1]);
    }
    work[j] = []; //in case of odd number of items
  }
  return work[0];
}

Memoization

就是緩存前一次的計算結(jié)果避免重復(fù)計算嗡官。繼續(xù)以階乘為例，如下三個階乘毯焕，共需要執(zhí)行factorial函數(shù)18次衍腥。其實計算6的階乘的時候，已經(jīng)計算過5和4的階乘纳猫。特別是4的階乘被計算了3次婆咸。

var fact6 = factorial(6);
var fact5 = factorial(5);
var fact4 = factorial(4);

我們利用Memoization技術(shù)重寫factorial函數(shù)，代碼如下：

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];
}

這是再執(zhí)行6,5,4的階乘芜辕，實際只有6的階乘進行了遞歸計算尚骄，共執(zhí)行factorial函數(shù)8次。5和4的階乘直接中緩存里取出結(jié)果物遇。