循环优化与链表是否一个闭环

 

经典的判断链表是否有环：

方法一：有个经典的算法就是解决这个问题的,好象是叫快慢法.他的原理是,如果A,B两人从同一地点出发,B的速度大于A,那么如果存在一个环的话,B和A肯定是能再见面的.

C/C++ code?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

ool IsLoop( link* head) {    link* s = head; //移动缓慢的指针    link* f = head; //移动快速的指针           do    {       if( s == NULL ) return (false );       s = s->next; //一次向前移动一个              if( f== NULL ) return (false );       f = f->next;             if( f== NULL ) return (false );       f = f->next; //一次向前移动2个    }while( f!= s);      return (f!=NULL); }   方法二：按照顺序读取链表，然后没读取一个就记录下当前位置和当前位置指向的下一个位置，然后判断当前位置的下一个位置是否前面已读取过。当然，要自己写一个辅助结果去记录。

优化下面这段代码，并说明原因
 for(int i =0; i < 1000; i++)
    for (int j=0; j < 100; j++)
       for (int k = 0; k < 10; k++)
           fun(i, j, k);

for (int k = 0; k < 10; k++){

    for (int j=0; j < 100; j++){

        for(int i =0; i < 1000; i++){

           fun(i, j, k);

        }

   }

}

虽然循环次数相同，但是层与层之间的切换次数减少，节省了栈的切换频率，可以提升效率。

 

 这个问题的主要原因是CPU内部的指令执行机制。现在，基本上CPU内部都有分支指令预测，就是当执行（现在大多将这一阶段提前到预取指令时执行）到转移指令时，都会直接从分支目标缓存（BTB）中取出目标指令的地址，然后将要执行的指令提前预取到CPU的指令预取指令队列中。这样，显然大大提高了效率。举个例子，一个10次的一层循环在执行时，除了在第一次和最后一次会预测错误外，其他8次都会预取成功，避免了执行转移指令时重新取出新指令造成的时间浪费。 

所以，当有两层循环，外层循环数为A，内层为B，A远大于B，那么最终造成的预测错误数为A*2+2，而如果外层数为B，内层数为A，预测错误数为B*2+2，显然后者要节省更多时间，而且这个时间是很可观的。A比B越大，这个时间差越明显。 

 

代码优化原则

*************************************************************************************************

优化原则：

最最首先要考虑的问题是：我选择的核心算法是否可以改进，然后考虑算法的实现是否完整，有没有与原始算法存在出入的地方，最
后优化代码，如下：

1.优化最为核心的代码-->1.最为常用的函数，2.计算量很大的函数，3.实现核心算法的函数

2.优化嵌套for循环，尽量减少循环的层次，尽量让小循环在外层，大循环在内层，尽量不要在for循环内部执行if语句，尽量不在

  for循环内部创建临时变量（在外面创建临时变量），尽量不重复计算相同的表达式（用临时变量存储），例如下面的代码就不好
 
  for（int i = 0;i<100;i++）
  {
      a = (c*d/f-e)*2;
      b = (c*d/f-e)*2;
  }
  上面的代码中“(c*d/f-e)*2”就是重复计算，我们可以将它改为：
  int temp = (c*d/f-e)*2;
  for（int i = 0;i<100;i++）
  {
      a = temp;
      b = temp;
  }
  在我的印象中：赋值运算比四则运算要块！上面的优化策略虽然提高了速度，但是可能造成代码很难理解！需要权衡，当然建议尽  
  量优化，同时增加必要的注释！
 

3.优化if语句，如果是单条件，尽量让表达式简单，例如：“if(condition == true){...}”应该改为“if(condition){...}”

  如果是多条件，尽量优化这些条件排放的顺序，因为：（条件1 && 条件2）语句中
  
  当 条件1 不成立的时候是不会判断 条件2 的，（条件1 || 条件2）语句中，当 条件1 成立的时候是不会判断 条件2 的！

4.优化return语句，尽量不产生临时变量然后返回，这样计算量会加大。如果可以，尽量直接返回表达式。例如：不要出现如下代码 
 
  int a;
  a = b+c;
  return a;

  将上面的代码直接改为：return a+b;可以提高速度！

  又例如：不要出现如下的代码：

  if（condition）
     return true;
  else
     return false;

  应该直接改为：return condition;

5.优化所有的 *2 或 /2语句，改为左移或者右移。当然编译器如果能自动将 *2 或者 /2 转化为左移或者右移就另当别论！

6.优化所有的 a = a + b;语句，改为 a += b;

7.如果可以，尽量以 “引用传递” 的方式将参数传入函数体，尽量以“引用传递”的方式返回结果！

8.检查所有的 new 语句，一定要有配套的 delete 语句与之对应！防止因为没有及时释放内存而导致内存泄漏！

9.优化指针，for循环中如果有指针操作，如果可能，尽量通过移动指针来直接对内存中的数据进行处理，而不要采用指针首地址+偏
  移量的方式来访问数据，简单点儿就是，p[i] = a;是可以优化的，例如：

  int *p = &a[0];
  for(int i = 0;i<100;i++)
  {
      p[i] = 1;
      //本质是 *（p+i） = 1;   一个加法运算，一个赋值运算 
  }
  上面的代码中p指针没有变化，其实“p[i] = 1” 会转化为“ *（p+i） = 1”;
  
  所以上面的代码可以这样改：

  int *p;
  for(p = &a[0];p-&a[0]<100;p++)
  {
      *p = 1;
  }
  优化后的代码比源代码计算次数少了一次！也就是原始代码的三分之二！

****************************************************************************************************************