算法和流程控制

循环

for循环是常见的编程模式之一，也是提升性能必须要关注的要点之一。

js的循环有四种：

1. for循环
2. while循环
3. do--while循环
4. for--in循环

其中在浏览器中，while的循环会快于for循环，而for--in循环是最慢的，因为他会先从对象实例属性开始到从原型链继承而来的属性一一枚举。

如何提高循环的性能？

首先我们要知道，除了for--in，其他的循环性能都差不多，深究那种循环最快其实没有什么意义，循环的方式要看你环境的需求，那么抛开最快来讲，我们怎么才能提高循环的性能？

无非就两点：

1. 每次循环处理的事物
2. 循环的次数

通过减少两者中的一个，或者全部的时间开销，就可以提升整体的性能。

减少循环处理的事物

首先看下平时使用的循环：

var item = [1,2,3]
for(var i = 0;i<item.length;i++){
  get(item[i]);
}

var j = 0;
while(j<item.length){
  get(item[j++]);
}

var k = 0;
do {
  get(item[k++]);
}while(k<item.length)

function get(num){
  alert(num);
}

上面循环每次循环时都会产生一下操作：

1. 判断循环条件时先会查找一次item元素的length属性（item.length）
2. 然后进行一次数值比较（i<item.length）
3. 比较的计算结果然后转换为布尔值（i<item.length == true）
4. 一次自增操作（++）
5. 一次数组查找（item[i]）
6. 一次函数调用（get(item[i])）

这些循环虽然代码不多，但是每次循环都会产生以上的步骤，我们可以通过减少以上的步骤来达到效果

之前讲过一次，局部变量的访问时比访问全局的要快的，然后将需要重复访问的值保存为一个局部变量，就可以减少访问次数。

var item = [1,2,3]
for(var i = 0，len = item.length;i < len;i++){
  get(item[i]);
}

这样写就可以减少访问item元素的次数，其他循环也是一样的写，定义一个变量保存length值即可达到一样的效果。

我们还可以通过倒序的方式来提高循环性能。

var item = [1,2,3];
for(var i = item.length;i--;){
  get(item[i]);
}

在js中，倒序循环会略微提升性能，通过倒序循环，并把后执行体（i--）放在前测条件中，这样就将两次对比变为了一次，直接判断数字是否为0；任何非0值都会自动转化为true，而0则等于false，原来是先判断小于length吗？是否为true，现在就直接就是是否为true，每次循环处理的事件又减少了，提升了性能。

for(var i = item.length;i--;){
  get(item[i]);
}

var j = item.length;
while(j--){
  get(item[j]);
}

var k = item.length -1;
do {
  get(item[k]);
}while(k--)

相对于之前的循环，这里只产生四个步骤：

1. 一次前测条件判断（i== true）
2. 一次自减操作（i--）
3. 一次数组查找（item[i]）
4. 一次函数运行（ get(item[i])）

如何减少循环的次数？

最广为人知的一种方式是“达夫设备 deff’s device”；它可以在一次循环中运行多次循环操作，为此‘jeff Greenberg’也被认为是将 “deff’s device”从原始的c实现移植到js的第一人。

典型实现如下：

var iterations = Math.floor(item.length/8),
    startAt = item.length % 8,
    i = 0;

do {
  switch(startAt) {
     case 0 : get(item[i++]);
     case 7 : get(item[i++]);
     case 6 : get(item[i++]);
     case 5 : get(item[i++]);
     case 4 : get(item[i++]);
     case 3 : get(item[i++]);
     case 2 : get(item[i++]);
     case 1 : get(item[i++]);
  };
  startAt = 0;
}while(--iterations)

iterations 判断当前元素能执行几个8次，使用Math.floor()去除小数点后的数。

startAt 通过求余判断余几次。

do -- while运行，先循环，switch判断余数，因为没有使用break跳出循环，所以，当case 0 判断为true的时候，它以及他后面的执行体都会运行，也就是说后面的get(item[i++])都会运行一遍，达到运行8次的效果。

第二次do--while循环的时候--操作，如果只循环一次的话，iterations 为0，转化为false，但是也有个问题，如果不能完整的循环一次，iterations 为0的时候，再--操作，就等于-1，这样就会死循环下去，我个人时这样避免的：

var iterations = Math.floor(item.length/8) == 0 ？1 ：Math.floor(item.length/8),
    startAt = item.length % 8,
    i = 0;

do {
  switch(startAt) {
     case 0 : get(item[i++]);
     case 7 : get(item[i++]);
     case 6 : get(item[i++]);
     case 5 : get(item[i++]);
     case 4 : get(item[i++]);
     case 3 : get(item[i++]);
     case 2 : get(item[i++]);
     case 1 : get(item[i++]);
  };
  startAt = 0;
}while(--iterations)

通过一个三元运算判断，如果等于0就返回1，这样下一次--操作就不会是负数了。

实际上还有一种稍快的版本，他取消了do--while，并将余数处理和主循环分开了。

var i = item.length % 8;

while(i) {
  get(item[i--])
}

i = Math.floor(item.length / 8);

while(i) {
  get(item[i--]);
  get(item[i--]);
  get(item[i--]);
  get(item[i--]);
  get(item[i--]);
  get(item[i--]);
  get(item[i--]);
  get(item[i--]);
}

但是这样写是有问题的，不对，意思是明白的，所以我自己修正了一下，写成这样

var startAt = item.length % 8,
    iterations = Math.floor(item.length / 8),
    i = 0;

while(startAt) {
  get(item[i++]);
  startAt--;
}

while(iterations) {
  get(item[i++]);
  get(item[i++]);
  get(item[i++]);
  get(item[i++]);
  get(item[i++]);
  get(item[i++]);
  get(item[i++]);
  get(item[i++]);
  iterations--；
}

实际上这两种还是要看你循环的次数的，如果循环的次数过少，实际上没什么提示，但如果你循环1000次以上，提升就很明显了。

基于函数的迭代

ECMA-262 标准第四版引入了一个新的原生数组方法：forEach()。此方法会遍历一个数组的所有成员，并在每个成员上执行一个函数。要运行的函数作为参数传给forEach()，并在调用时接收三个参数，分别时：当前循环到的数组项的值、索引值、数组本身。

除了当前循环到的数组项的值时必须的，其他两个都是自选项，可写可不写，看需要。

例子：

item.forEach(function(value,index,array){
  get(value);
});

这个方法ie9及以上和其他浏览器都支持，这个方法相对使用普通的循环，减少了代码量，但是相对来说，调用外部方法怎么也会比普通循环慢一些，如果你的项目对速度有很大的要求，那么使用这个并不是一个很好的选择。（比普通循环慢8倍）

条件语句

条件判断也是编写代码不可少的一部分，条件表达式决定了js代码的运行流向，但由于不同的浏览器针对流程控制都有进行不同的优化，因此使用if-else还是switch方法，没有绝对的定论。

但是如何使用if-else还是switch，最简单的方法就是通过判断条件的数量来判断，判断的条件越多，使用switch就更方便易读，主要还是看使用的环境和条件。

比如：

if(found) {

}else {

}

switch(found) {
  case  true : 
        //代码处理
        break;
  case false :
        //代码处理
        break;
  default : 
        //其他处理
}

上面简单的判断，if会比switch方便易读，但如果我们增加判断的条件，就相反了

if(color == 'red') {
   //代码处理
}else if(color == 'blue') {
   //代码处理
}else if(color == 'brown') {
   //代码处理
}else if(color == 'black') {
   //代码处理
}else {
   //代码处理
}

switch(found) {
  case  'red': 
        //代码处理
        break;
  case 'blue':
        //代码处理
        break;
  case 'brown':
        //代码处理
        break;
  case 'black':
        //代码处理
        break;    
  default : 
        //其他处理
}

事实证明，大多数情况下，使用switch会比if要快，但是前提是当前的条件数量很大才能体现，这两个语句主要的性能区别是：当条件增加时，if--else的性能负担增加程度会比switch要多。 因此，我们自然倾向于条件少时使用if，条件多时使用switch。

优化if--else

最简单的方法就是将容易出现的情况写在最上面：比如5以下的数字容易出现

if(value < 5) {
   
}else if(value > 5) {
   
}else {

}

但是当条件过多时，这样写还不够，我们可以通过嵌套的方式来优化

if(value == 0) {
  return 0;
}else if(value == 1) {
  return 1;
}else if(value == 2) {
  return 2;
}
......
//这样不断重复的判断

优化：

if(value < 6) {
  if(value < 3) {
      if(value == 0) {
          return 0;
      }else if(value == 1) {
          return 1;
      }else {
           return 2;
      }
  }else {
      if(value == 3) {
        return 3;
      }else if(value == 4) {
        return 4;
      }else {
        return 5;
      }
  }
}else {
  if(varlue < 8) {
    if(value == 6) {
      return 6;
    }else (value == 7) {
      return 7
    }
  }else {
    if(value == 8) {
      return 8;
    }else if(vlaue == 9) {
      return 9;
    }else {
      return 10;
    }
  }

}

通过判断范围然后嵌套再判断范围可以减少if判断的次数，比一个一个的判断要好的多。这个方法适用于有多个值域需要测试的时候，如果是不确定的随机数字，那么使用switch会更好。

查找表

有些时候优化条件语句的最佳方案就是避免使用if-else和switch。当有大量离散值的时候，使用查找表会比判断语句快的多。

简单点来说就是将需要返回的值全部保存在一个对象中，可以是数组，也可以是键值对的形式，然后通过调用对应的下标或者键名来获取到结果，这样完全抛弃判断语句，整个过程变成对象值查询的过程，减少了不必要的开销。

var arr ['1s','2s','3s'];

return arr[x];

递归

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

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

递归函数的潜在问题是终止条件不明确或者缺少终止条件会导致函数的长时间运行，并使得用户界面假死，而且递归函数还可能遇到浏览器调用栈的大小限制。

当你使用了太多的递归，甚至超过浏览器的栈的最大容量时，浏览器就会报告错误信息，并终止代码运行。

IE : “Stack overflow at line x”

Firefox: “Too much recursion”

safari : “Maximum call stack size exceeded”

opera : “Abort(control stack overflow)”

chrome是唯一个不显示调用栈溢出错误信息的浏览器。

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

一种是上面的factorial()，即函数调用自身

function recures() {
  recures()
}
 recures()

在发生错误时，我们可以很快的定位到，但另一种模式就不好定位了：

function one() {
  two()
}

function two() {
  one()
}

one()

两个函数相互调用，形成一个无限循环，这种模式很难在代码库中定位到。

大多数的栈调用错误都与这两种模式有关，最常见导致溢出的原因就是不正确的终止条件，因此定位错误的原因首先就要验证终止的条件，如果终止条件没有问题，那么就可能是算法中包含了太多的递归，为此可以采用其他的方式，建议使用迭代。

迭代

function factorial(n) {
  var arr = n ;
  while(--n > 0) {
    arr = arr * n
  }
  return arr
}


factorial(6)

通过循环的方式代替递归，也就是迭代，迭代本身的意思就是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

名字高大上，其实就是循环嘛！

迭代其实常用于合并排序，由于比较难理解，我从网上找到一张非常明了的图，这个展示一下：

也就是分而治之，代码如下：

function mergn(left,right) {
    var result = [];
    if(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 mergSort(item){
    if(item.length == 1) {
        return item;
    }
    
    var middle = Math.floor(item.length / 2),
        left = item.slice(0,middle),
        right = item.slice(middle);
    
    return mergn(left,right);
    
}

当然迭代也是有优化的，针对上面这个也有对应的方式，但是我目前理解不来，后续再写吧！