《高性能 JavaScript》第 4 章算法和流程控制

布满荆棘的人生 2022-09-03 07:26 137阅读 0赞

# 第 4 章 算法和流程控制 #

> 《高性能 JavaScript》—— Nicholas C. Zakas

代码的整体结构是影响运行速度的重要因素之一。

## 1. 循环 ##

在大多数编程语言中，代码执行时间大部分消耗在循环中。

### 1.1. 循环类型 ###

四种循环语法

*  `for`
 *  `while`
 *  `do while`
 *  `for in`

示例：

for (var i=0; i < 10; i++){
        
      // loop body
    }
    
    
    var i = 0;
    while(i < 10) {
        
     // loop body
     i++;
    }
    
    
    var i = 0;
    do {
        
      // loop body // 后测循环，至少执行一次
    } while (i++ < 10);
    
    
    for (var prop in object){
        
      // loop body
    }

### 1.2. 循环性能 ###

`for` 、`while`、`do while` 速度差不多，  
由于 `for in` 每次循环都要搜索对象（或原型链），所以非常慢，是其他循环类型的 1/7。

循环的性能与以下两个因素有关：

*  每次迭代的工作量
 *  迭代的次数

#### 1.2.1. 减少每次迭代的工作量 ####

将 `length` 存到局部变量中，大约可以节省 25% 的运行时间。

// original loops
    for (var i=0; i < items.length; i++){
        
      process(items[i]);
    }
    
    // minimizing property lookups
    for (var i = 0, len = items.length; i < len; i++) {
        
      process(items[i]);
    }

以及优化每次迭代的具体代码。

#### 1.2.2. 减少迭代次数 ####

除了迭代里的代码，每次迭代本身也会消耗性能，上千次的迭代会带来明显的性能开销。

减少迭代次数能明显提升性能。

最出名的减少迭代次数的模式是 达夫设备（Duff’s Device），如下：

// 除以 8 后的余数
    var i = items.length % 8;
    
    while(i) {
        
      process(items[i--]);
    }
    
    // 8 的倍数
    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--]);

“Duff’s Device” 是一种循环体展开技术，每次迭代执行之前 8 次迭代的操作，  
循环次数超过 1000 才会有明显的性能提升，如 50 万次迭代，运行时间比常规循环少 70%。

### 1.3. 基于函数的迭代 ###

ES4 引入 `Array.prototype.forEach` 函数，如下：

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

尽管 `forEach` 是一个很便利的迭代方式，  
但循环（`for`、`while` 等）仍旧比 `forEach` 快 8 倍。

## 2. 条件语句 ##

`if-else` 和 `switch` 都是（流程控制中的）选择类型的语句

### 2.1. `if-else` vs `switch` ###

`if-else` 适用于判断两个离散值或几个不同的值域

`switch` 适用于判断两个以上的离散值

代码如下：

if (found){
        
     //do something
    } else {
        
     //do something else
    }
    
    
    switch (color){
        
      case "red":
        //do something
        break;
    
      case "blue":
        //do something
        break;
    
      case "brown":
        //do something
        break;
    
      case "black":
        //do something
        break;
    
      default:
        //do something
    }

`switch` 比 `if-else` 要快，当条件数量很大时才会很明显。

### 2.2. 优化 `if-else` ###

到达正确分支的路径越小越好：

1.  概率最高的条件排第一
2.  嵌套

// value < 5 的概率最高时，代码最优
    if (value < 5) {
        
      //do something
    } else if (value > 5 && value < 10) {
        
      //do something
    } else {
        
      //do something
    }

// value 是 0 ~ 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;
    }
    
    // 可以改为嵌套，类似于 二分查找
    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;
        }
      }
    }

### 2.3. 在表（哈希表或数组）查找 ###

当有大量离散值时，最好使用（哈希）表或数组，  
比 `if-else` 、 `switch` 更快且更可读。

可以将数组的索引或对象的键值作为条件判断的依据，如：

switch(value){
        
      case 0:
        return result0;
    
      case 1:
        return result1;
    
      case 2:
        return result2;
    
      default:
        return defaultResult;
    }
    
    // 优化：使用数组
    var results = [result0, result1, result2];
    return results[value];
    
    // 优化：使用对象（字典、哈希表）
    var results = {
        
      '0': result0,
      '1': result1,
      '2': result2,
    };
    return results[value];

## 3. 递归 ##

// n 的阶乘
    function factorial(n){
        
      if (n == 0){
        
        return 1;
      } else {
        
        return n * factorial(n-1);
      }
    }

递归可以把复杂的算法变得简单，  
但终止条件未处理好会导致长时间运行JS，进而冻结页面，  
而且浏览器会限制递归调用栈的大小。

### 3.1. 调用栈限制 ###

JS 引擎支持的递归数量与 JS 调用栈大小有关。

超过调用栈大小，会报错，可以使用 `try catch` 捕获：

try {
        
      recurse();
    } catch (ex){
        
      console.log("Too much recursion!", ex);
    }

存在调用栈溢出的代码不应该发布上线。

### 3.2. 递归的两种方式 ###

递归通常有两种方式：

1.  自己调自己
2.  两个函数相互调用

自己调自己：

function recurse(){
        
     recurse();
    }
    
    recurse();

两个函数相互调用：

function first(){
        
      second();
    }
    
    function second(){
        
      first();
    }
    
    first();

当出现调用栈溢出时，通常是以上两种递归中的一种造成的。

建议改用 迭代或 memoization（to be remembered）

### 3.3. 迭代 ###

任何递归能实现的算法，用迭代也可以实现。  
运行一个循环比反复调用一个函数的开销要小得多。

例如合并排序算法，递归实现：

当数组有 n 项时，`mergeSort` 会调用 2\*n-1 次，  
这意味着 n 为 1500 时，在 Firefox 上会导致栈溢出。

使用迭代的方式实现：

//uses the same mergeSort() function from previous example
    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];
    }

尽管迭代版本比递归版本慢一点，但可以避免调用栈溢出的错误。

### 3.4. memoization ###

> memoization 来源于拉丁语 memorandum (“to be remembered”)，不要与 memorization 混淆了。  
> memoization 是一种优化技术，主要用于通过存储昂贵的函数调用的结果来加速计算机程序，并在再次发生相同的输入时返回缓存的结果。

缓存计算结果，即将入参作为 key 缓存到字典中，比如计算阶乘：

执行计算之前，先检测缓存中是否有相同入参的计算结果，有则使用，无则进行计算并缓存。

可以封装一个通用的 memoize() 函数：

// 封装原始函数，返回一个新函数（外壳）
    function memoize(fundamental, cache){
        
      cache = cache || {
        };
    
      // 外壳
      var shell = function(arg) {
        
        if (!cache.hasOwnProperty(arg)){
        
          cache[arg] = fundamental(arg);
        }
    
        return cache[arg];
      };
    
      return shell;
    }
    
    // memoize the factorial function
    var memfactorial = memoize(factorial, {
         "0": 1, "1": 1 });
    
    // call the new function
    var fact6 = memfactorial(6);
    var fact5 = memfactorial(5);
    var fact4 = memfactorial(4);

## 4. 总结 ##

JS 因为资源有限，优化技术显得尤为重要：

*  `for` `while` `do while` 性能差不多，根据使用习惯进行选择
 *  避免 `for in`
 *  优化循环的方式：减少每次迭代的工作量、减少循环次数
 *  `switch` 比 `if else` 要快
 *  离散值条件较多时，使用数组或字典更快
 *  调用栈大小限制了递归的使用，栈溢出会导致代码中断
 *  可以使用 迭代或 memoization 来避免栈溢出错误

当执行代码越多，以上策略带来的性能优化越明显。