程序优化 |

程序优化是指程序效率的优化。一般来说，程序优化主要是以下三个步骤：

算法优化

算法上的优化是必须首要考虑的，也是最重要的一步。
一般我们需要分析算法的时间复杂度，即处理时间与输入数据规模的一个量级关系，
一个优秀的算法可以将算法复杂度降低若干量级，
那么同样的实现，其平均耗时一般会比其他复杂度高的算法少（这里不代表任意输入都更快）。

比如说排序算法，快速排序的时间复杂度为O(nlogn)，
而插入排序的时间复杂度为O(n*n)，那么在统计意义下，快速排序会比插入排序快，
而且随着输入序列长度n的增加，两者耗时相差会越来越大。
但是，假如输入数据本身就已经是升序(或降序)，那么实际运行下来，快速排序会更慢。

代码优化一般需要与算法优化同步进行，代码优化主要是涉及到具体的编码技巧。
同样的算法与功能，不同的写法也可能让程序效率差异巨大。
一般而言，代码优化主要是针对循环结构进行分析处理。

能把运算放在循环外的尽量提出去放在外部，循环内部不必要的乘除法可使用加法来替代等。

关于CPU流水线技术可google/baidu，循环结构内部计算或逻辑过于复杂，将导致cpu不能流水，
那这个循环就相当于拆成了n段重复代码的效率。

for(int i = 0; i < N; i++)
{
    if(i < 100) a[i] += 5;
    else if(i < 200) a[i] += 10;
    else a[i] += 20;
}

优化为：

for(int i = 0; i < 100; i++)
{
    a[i] += 5;
}
for(int i = 100; i < 200; i++)
{
    a[i] += 10;
}
for(int i = 200; i < N; i++)
{
    a[i] += 20;
}

定点化的思想是将浮点运算转换为整型运算，
定点化的做法是将数据乘上一个很大的数后，将所有运算转换为整数计算。
例如某个乘法我只关心小数点后3位，那把数据都乘上10000后，进行整型运算的结果也就满足所需的精度了。

空间换时间最经典的就是查表法了，某些计算相当耗时，但其自变量的值域是比较有限的，
这样的情况可以预先计算好每个自变量对应的函数值，存在一个表格中，每次根据自变量的值去索引对应的函数值即可。

预分配内存主要是针对需要循环处理数据的情况的。
比如视频处理，每帧图像的处理都需要一定的缓存，如果每帧申请释放，则势必会降低算法效率

略。

程序热点是指程序中最耗时的部分，一般程序优化工作都是优先去优化热点部分，那么如何来定位程序热点呢？

一般而言，主要有2种方法，一种是通过观察与分析，通过分析算法，自然能知道程序热点；
另一方面，观察代码结构，一般具有最大循环的地方就是热点，这也是前面那些优化手段都针对循环结构的原因。
另一种方法就是利用工具来找程序热点。