JavaScript性能优化（四）

本文是阅读《高性能JavaScript》一书后，从 算法与流程控制 模块对JavaScript性能优化做了部分总结，记录一下。可能总结的不好，不是很完整，也希望各位大佬能多给出一些建议。万分感谢！

---

循环

循环类型

• 普通 for 循环

  在for循环中初始化的var语句会创建一个函数级的变量，而不是循环级。由于JavaScript只有函数级作用域，因此在for循环中使用var定义一个新变量相当于在循环体外定义一个新变量

• while 循环，while 循环是最简单的前测循环

• do-while 循环，是 JavaScript 中唯一一种后测循环

• for-in 循环：可以枚举任何对象的属性名

  • for-in 循环是四种循环中最慢的，另外三种循环性能相仿
  • 不要用 for-in 来遍历数组成员
  • 尽量避免使用 for-in 循环，除非你明确需要一个属性数量未知的对象

循环性能

当循环复杂度为 O(n) 时，减少每次迭代的工作量是最有效的方法。当复杂度大于 O(n)，建议着重减少迭代次数

• 减少迭代的工作量

  1. 减少对象成员及数组项的查找次数

     // 原始版本
     for (var i = 0; i < items.length; i ++) {
         process(items[i]);
     }
     
     // 最小化属性查找（优化版本）
     for (var i = 0, len = items.length; i < len; i ++) {
         process(items[i]);
     }
     
     // 优化后的版本大概能节省25%的运行时间（IE中甚至可以节省50%）
     // 另外三种循环也是一样的优化方式

  2. 使用倒序循环来提高循环性能

     // 数组项的顺序与索要执行的染污无关时，可以按照下面方式改写。可以略微提升性能
     for (var i = items.length; i --; ) {
         process(items[i]);
     }

• 减少迭代次数

  1. 达夫设备（Duff’s Device）

     是否应该使用“达夫设备”，无论是原始版本还是优化版本，很大程度上取决于迭代次数。若循环次数小于1000，性能提升微不足道。如果迭代次数超过1000，那么“达夫设备”的执行效率明显提升。

     • 初始版本

       // credit: Jeff Greenberg
       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);

     • 优化版本

       此算法将余数处理和主循环分开。尽管这种方式使用两次循环代替之前的一次循环，但它移除了循环体中的 switch 语句，速度比原始循环更快

     // credit: Jeff Greenberg
     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--]]);
     }

  2. 其他方案

基于函数的迭代

尽管基于函数的迭代提供了一个更为便利的迭代方法，但它仍然 比基于循环的迭代要慢一些

• Ecma-262 标准第四版一如了一个新的原生数组方法：forEach()：items.forEach(function(value, index, array) {})

• YUI 3 的each()：Y.Array.each(items, function(value, index, array) {})

• Jquery 的 each()：jQuery.each(items, function(index, value) {})

• Dojo 的 forEach()：dojo.each(items, function(value, index, array) {})

• ProtoType 的 each()：items.each(function(value, index) {})

• MooTools 的 each()：$each(items, function(value, index) {})

---

条件语句

if-else 对比 switch

大多数的语言对 switch 语句的实现都采用了 branch table（分支表）索引来进行优化。
另外，在 JavaScript 中，switch 语句比较值时使用权等操作符，不会发生类型转换的消耗。

• 大多数情况下，switch 比 if-else 运行得要快

• 循环条件较少时，if-else 更易读，条件数量较多时，switch 更易读

• if-else 适用于判断两个离散值或者几个不同的值域。当判断多与两个离散值时，switch 语句是更佳选择

优化 if-else

优化 if-else 的目标是：最小化到达正确分之前所需判断的条件数量

• 最简单的优化方法是确保可能出现的条件放在首位

• 把 if-else 组织成一系列嵌套的 if-else 语句

  // 实例代码：
  
  // 普通版本
  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;
  }
  
  // 优化版本
  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 {
              return result9;
          }
      }
  }

  重写后的 if-else 语句每次到达正确分支最多经过4次条件判断。它使用二分法把值域分成一系列的区间，然后逐步缩小范围。耗时仅是普通版本的一半。
  这个方法非常适用于有多个值域需要测试的时候（如果是离散值，那么switch语句通常更为合适）。

查找表

有些时候优化条件语句的最佳方案是避免使用 if-else 和 switch。当有大量离散值需要测试时，if-else 和 switch 比使用查找表慢很多。JavaScript 中可以使用数组和普通对象来构建查找表。通过查找表访问数据比用 if-else 或 switch 快很多，特别是在条件语句数量很大的时候。

使用查找表相对于 if-else 和 switch，不仅速度更快，而且有时代码的可读性更好，特别是当需要测试的离散值数量非常大的时候。

// 普通switch
switch (value) {
    case 0: 
        return result0;
    case 1: 
        return result1;
    case 2: 
        return result2;
    case 3: 
        return result3;
    case 4: 
        return result4;
    case 5: 
        return result5;
    case 6: 
        return result6;
    case 7: 
        return result7;
    case 8: 
        return result8;
    case 9: 
        return result9;
    default:
        return result10;
}

// 使用查找表技术优化
// 将返回值集合存入数组
var results = [result0, result1, result2, result3, result4, result5, result6, result7, result8, result9, result10];

// 返回当前结果值
return results[value];

---

调用栈限制

JavaScript 引擎支持的递归数量与 JavaScript 调用栈大小直接相关。只有 IE 例外，它的调用栈与系统空闲内存有关，而其他浏览器都有固定数量的调用栈限制。

使用了太多递归，甚至超过最大调用栈容量时，浏览器会报告一下错误信息：

• Internet Explorer: “Stack overflow at line x”

• Firefox: “Too much recursion”

• Safari: “Maximum call stack exceeded”

• Opera: “Abort（control stack overflow）”

• Chrome 是唯一不显示调用栈溢出错误的浏览器

尽管在 JavaScript 中捕获这些错误是有可能的，但并不推荐这样做。那些有潜在问题的调用栈溢出问题的脚本不应该发布上线

---

递归

使用递归可以把复杂的算法变简单。比如阶乘函数：

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

递归的潜在问题是终止条件不明确或缺少终止条件会导致函数长时间运行，并使得用户界面处于假死状态

当遇到调用栈大小限制时，第一步应该先检查代码中的递归实例。为此，有两种递归模式值得注意：

• 直接递归模式（即函数调用自身）

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

• 隐伏模式（两个或多个函数互相调用）

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

大多数调用栈错误都这两种模式有关。组常见的导致栈溢出的原因是不正确的终止条件，因此定位模式错误的第一步是验证终止条件。如果终止条件没有问题，那么可能是算法中包含了太多层递归，为了能在浏览器中安全的工作，建议改用 迭代、Memoization，或者结合两者使用。

---

迭代

任何递归能实现的算法同样可以用迭代来实现。迭代算法通常包含以下几个不同的循环，分别对应计算过程的不同方面，这也会引入它们自身的性能问题。然而，使用优化后的循环替代长时间运行的递归函数可以提升性能，因为 运行一个循环比反复调用一个函数的开销要少很多

例如合并排序算法：

• 使用递归

  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() 函数会导致很频繁的自调用。一个长度为 n 的数组最终会调用 mergeSort() 2*n - 1 次，这意味着一个长度超过 1500 的数组会在 Firefox 上发生栈溢出错误。

• 使用迭代优化

  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 work = [];
      for (var i = 0, len = items.length; i < len; i ++) {
          work.push([items[i]]);
      }
      work.push([]);
  
      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] = []; // 如果数组长度为奇数
      }
  
      return work[0];
  }

  这个版本没有使用递归，尽管迭代版本的合并排序算法比递归实现得要慢一些，但它不会像递归版本那样受调用栈限制的影响。把递归算法改用迭代实现是避免栈溢出错误的方法之一。

---

Memoization

减少工作量就是最好的性能优化技术。代码要处理的事越少，它的运行速度就越快。沿着这个思路，避免重复工作也是有意义的。多次执行相同的任务纯粹是浪费时间。Memoization 正是一种避免重复工作方法，它缓存前一个计算结果供后续计算使用，避免了重复工作。这使得它成为递归算法中有用的技术。

• 普通的阶乘函数

  function factorial(n) {
      if(n == 0) {
          return 1;
      } else {
          return n * factorial(n - 1);
      }
  }
  var fact6 = factorial(6);
  var fact5 = factorial(5);
  var fact4 = factorial(4);

  这段代码有3次阶乘计算，导致 factorial() 函数一共被调用了 18 次。改代码中最糟糕的部分是，所有必要的计算在第一行代码里已经处理掉了。

• 使用 Memoization 技术进行重写（保存并重用计算结果，而不是每次都重新计算整个函数）

  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];
  }
  
  var fact6 = memfactorial(6);
  var fact5 = memfactorial(5);
  var fact4 = memfactorial(4);

  该代码返回了3个不同的阶乘值，但只调用了 memfactorial() 函数 8 次。因为所有必要的计算都在第一行完成并缓存了，所以接下来的梁行代码不会发生地柜运算，而是直接返回缓存中的值了。

• 更简单的版本

  /**
   * 基础功能的 memoize 函数
   *    @param {*} fundamental 需要增加缓存功能的函数
   *    @param {*} cache 可选的缓存对象
   */
  function memoize(fundamental, cache) {
      cache = cache || {};
  
      var shell = function(arg) {
          if (!cache.hasOwnProperty(arg)) {
              cache[arg] = fundamental(arg);
          }
          return cache[arg];
      };
  
      return shell;
  }
  
  function factorial(n) {
      if(n == 0) {
          return 1;
      } else {
          return n * factorial(n - 1);
      }
  }
  
  var memfactorial = memoize(factorial, {"0": 1, "1": 1});
  var fact6 = memfactorial(6);
  var fact5 = memfactorial(5);
  var fact4 = memfactorial(4);

  这种通用的 Memoization 与手工更新给定函数的算法先比优化效果要差一些，因为 memoize() 函数会缓存特定参数的函数调用结果。当代码以相同的参数多次调用外壳函数时才能节省时间。因此，当 Memoization 函数存在显著性能问题时，最好有针对性的手工实现它，而不是直接用通用 Memoization 方案。

---

小结

• for、while、和 do-while 循环性能特性相当，并没有一种循环类型明显快于或慢于其他类型

• 避免使用 for-in 循环，除非你需要遍历一个属性数量未知的对象

• 改善循环性能的最佳方式是减少每次迭代的运算量和减少循环迭代次数

• 通常来说，switch 总是比 if-else 快，但并不总是最佳解决方案

• 在判断条件较多时，使用查找表比 if-else 和 switch 更快

• 浏览器的调用栈大小限制了递归算法在 JavaScript 中的应用；栈溢出错误会导致其他代码中断执行

• 如果你遇到栈溢出错误，可将方法改为迭代算法，或使用 Memoization 来避免重复计算

运行的代码数量越大，使用这些策略所带来的性能提升也就越明显。

JavaScript 和其他编程语言一样，代码的写法和算法会影响运行时间。与其他语言不同的是，JavaScript 可用资源有限（由于JavaScript是解释型语言，与编译性语言不同的是，它无需编译，而是将代码以字符串的形式交给 JavaScript 引擎来执行。因此，代码性能在一定程度上取决于客户端浏览器的JavaScript引擎），因此优化技术更为重要。