《高性能JavaScript》第四章 算法和流程控制
4.1 循環(huán)
4.1.1 循環(huán)的類型
主要有四種循環(huán)類型：for韩脏、while阅仔、do-while和for-in羞迷。
// 1、for循環(huán)：初始化、前測條件昼接、后執(zhí)行體和循環(huán)體組成泪喊。
for (var i=0; i < 10; i++){
// 循環(huán)體
}
// 2纬纪、while循環(huán)：前測條件和循環(huán)體組成摘仅。
var i = 0;
while(i < 10){
// 循環(huán)體
i++;
}
// 3、do-while循環(huán)：循環(huán)體和后測條件組成须床。
var i = 0;
do {
// 循環(huán)體
} while (i++ < 10);
// 4族阅、for-in循環(huán)：可以枚舉任何對象的屬性名沐寺。
for (var prop in object){
// 循環(huán)體
}
注意：
for循環(huán)初始化的var語句會創(chuàng)建一個函數(shù)級別的變量，而不是循環(huán)級禾酱。由于JavaScript只有函數(shù)級作用域，因此for循環(huán)中定義一個新變量相當(dāng)于在循環(huán)體外定義一個新變量腰懂。
4.1.2 循環(huán)性能
循環(huán)的性能提升主要由這幾個方面入手：
- 循環(huán)的類型：除了
for-in循環(huán)比其他三種循環(huán)明顯要慢外跋选，其他幾種性能都差不多。所以除非明確需要迭代一個屬性數(shù)量未知的對象哗蜈，否則避免使用for-in循環(huán)； - 減少迭代的工作量：將需要多次查找的屬性存入局部變量中重復(fù)使用，并使用倒序循環(huán)目溉；
// 原始版本
for (var i=0; i < items.length; i++){
process(items[i]);
}
var j=0;
while (j < items.length){
process(items[j++]]);
}
var k=0;
do {
process(items[k++]);
} while (k < items.length);
// 最小化屬性查找：在大多數(shù)瀏覽器中能節(jié)省25%運行時間
for (var i=0, len=items.length; i < len; i++){
process(items[i]);
}
var j=0,
count = items.length;
while (j < count){
process(items[j++]]);
}
var k=0,
num = items.length;
do {
process(items[k++]);
} while (k < num);
//最小化屬性查找并反轉(zhuǎn)：比原始版本快50%~60%
for (var i=items.length; i--; ){
process(items[i]);
}
var j = items.length;
while (j--){
process(items[j]]);
}
var k = items.length-1;
do {
process(items[k]);
} while (k--);
- 減少迭代次數(shù)：使用“達夫設(shè)備（Duff’s Device）”模式限制迭代次數(shù)绣檬。Duff’s Device背后的基本理念：每次循環(huán)最多可調(diào)用8次
process()，循環(huán)迭代的次數(shù)為總數(shù)除以8段直。
// 原始版Duff’s Device
var iterations = Math.floor(items.length / 8),
startAt = items.length % 8,
i = 0;
do {
switch(startAt){
case 0: process(items[i++]);
case 7: process(items[i++]);
case 6: process(items[i++]);
case 5: process(items[i++]);
case 4: process(items[i++]);
case 3: process(items[i++]);
case 2: process(items[i++]);
case 1: process(items[i++]);
}
startAt = 0;
} while (--iterations);
// 升級版Duff’s Device：盡管這種方式用兩次循環(huán)代替之前一次循環(huán)俏站，但移除了循環(huán)體中的switch語句，速度比原始更快痊土。
var i = items.length % 8;
while(i){
process(items[i--]);
}
i = Math.floor(items.length / 8);
while(i){
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
}
性能優(yōu)化：迭代次數(shù)
<1000肄扎，和常規(guī)循環(huán)結(jié)構(gòu)比性能提升微不足道；迭代次數(shù)>1000赁酝，Duff’s Device模式性能會有明顯提升犯祠。在5000次迭代中，性能比常規(guī)提升70%酌呆。
4.1.3 基于函數(shù)的迭代
ECMA-262標準第四版介紹了本地數(shù)組對象的一個新方法forEach()衡载。此方法遍歷一個數(shù)組的所有成員，并在每個成員上執(zhí)行一個函數(shù)隙袁。在每個元素上執(zhí)行的函數(shù)作為 forEach()的參數(shù)傳進去痰娱，并在調(diào)用時接收三個參數(shù)，它們是：數(shù)組項的值菩收，數(shù)組項的索引梨睁，和數(shù)組自身。
items.forEach(function(value, index, array){
process(value);
});
性能優(yōu)化：在所有情況下娜饵，基于循環(huán)的迭代比基于函數(shù)的迭代快
8倍坡贺。因此在運行速度嚴格要求時，基于函數(shù)的迭代不是合適的選擇箱舞。
4.2 條件語句
4.2.1 if-else對比switch
多數(shù)情況下拴念，switch比if-else運行的要快，但只有條件數(shù)量很大時才快的比較明顯褐缠。這兩句的主要性能區(qū)別是：當(dāng)條件增加時政鼠，if-else性能負擔(dān)增加的程度比switch要多。
性能優(yōu)化：
if-else適用于判斷兩個離散值或幾個不同的值域队魏；當(dāng)判斷多個離散值時公般，switch語句是更佳選擇。
4.2.2 優(yōu)化if-else
優(yōu)化目標：最小化到達正確分支前所需判斷的條件數(shù)量胡桨。
優(yōu)化原則：
- 將最可能出現(xiàn)的條件放在首位官帘，最小概率出現(xiàn)的的條件放在末尾；
- 使用
if-else嵌套：嵌套過程中使用二分法把值域分成一系列區(qū)間昧谊，逐步縮小范圍刽虹。從而減少條件判斷次數(shù)。
- 反例
// 最多要判斷10次
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 if (value == 6){
return result6;
} else if (value == 7){
return result7;
} else if (value == 8){
return result8;
} else if (value == 9){
return result9;
} else {
return result10;
}
- 正例
// 最多判斷4次
if (value < 6){
if (value < 3){
if (value == 0){
return result0;
} else if (value == 1){
return result1;
} else {
return result2;
}
} else {
if (value == 3){
return result3;
} else if (value == 4){
return result4;
} else {
return result5;
}
}
} else {
if (value < 8){
if (value == 6){
return result6;
} else {
return result7;
}
} else {
if (value == 8){
return result8;
} else if (value == 9){
return result9;
} else {
return result10;
}
}
}
4.2.3 查找表
- 描述
JavaScript中可以使用數(shù)組和普通對象來構(gòu)建查找表呢诬，特別是在條件語句數(shù)量很大的時候涌哲，性能比條件語句快很多胖缤。 - 原因
當(dāng)你使用查找表時，必須完全拋棄條件語句阀圾。這個過程變成數(shù)組項查詢或者對象成員查詢哪廓。主要優(yōu)點：不用書寫任何條件語句，即便候選值數(shù)量增加時初烘，也幾乎不會產(chǎn)生額外的開銷涡真。 - 反例
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 if (value == 6){
return result6;
} else if (value == 7){
return result7;
} else if (value == 8){
return result8;
} else if (value == 9){
return result9;
} else {
return result10;
}
- 正例
// 將返回值存入數(shù)組
var results = [result0, result1, result2, result3, result4, result5, result6, result7, result8, result9, result10]
// 利用數(shù)組返回當(dāng)前結(jié)果
return results[value];
4.3 遞歸
4.3.1 調(diào)用棧限制
JavaScript引擎支持的遞歸數(shù)量與JavaScript調(diào)用棧大小直接相關(guān)。如果超出了瀏覽器的調(diào)用棧限制肾筐，就會拋出調(diào)用棧溢出的異常哆料。
4.3.2 遞歸模式
遞歸一般有兩種模式：直接遞歸模式和隱伏模式。第二種模式在出現(xiàn)問題時吗铐，很難定位东亦。
// 1、直接調(diào)用模式
function recurse(){
recurse();
}
recurse();
// 2抓歼、隱伏模式
function first(){
second();
}
function second(){
first();
}
first();
4.3.3 迭代
- 描述
任何遞歸能實現(xiàn)的算法讥此，迭代也能實現(xiàn)拢锹。 - 原因
使用優(yōu)化后的循環(huán)替代長時間運行的遞歸函數(shù)可以提升性能谣妻，因為運行一個循環(huán)比反復(fù)調(diào)用一個函數(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));
}
- 正例
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);
}
// 使用迭代后比遞歸要慢一些卒稳，但不會受到調(diào)用棧限制蹋半。是避免棧溢出錯誤的方法之一。
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([]); // 如果數(shù)組長度為奇數(shù)
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] = []; // 如果數(shù)組長度為奇數(shù)
}
return work[0];
}
4.3.4 Memoization
Memoization是一種避免重復(fù)工作的方法充坑，它緩存前一個計算結(jié)果后供后續(xù)計算使用减江。
以階乘函數(shù)為例：
function factorial(n){
if (n == 0){
return 1;
} else {
return n * factorial(n-1);
}
}
// 使用過程中factorial()函數(shù)被調(diào)用了18次，而所有必要的計算在第一行代碼里已經(jīng)處理掉了捻爷。
var fact6 = factorial(6);
var fact5 = factorial(5);
var fact4 = factorial(4);
使用Memoization后辈灼，將第一次計算的結(jié)果緩存起來，后期再調(diào)用的時候也榄，直接從緩存中讀取結(jié)果巡莹。
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];
}
歡迎大佬糾錯指導(dǎo)，歡迎同行交流學(xué)習(xí)甜紫。
GitHub：https://github.com/Code4GL
簡書：http://www.reibang.com/u/7f5541a6b6d2
知乎：https://www.zhihu.com/people/code4gl/activities
公眾號：code_everything
QQ：771841496
郵箱：guanli1991@163.com
掃碼關(guān)注公眾號code_everything
