编程珠玑读书笔记（2）

第二部分 性能

当程序实现了用户的需求时，下一步就是关心提高程序的性能了。

第六章 程序性能分析

计算机系统是可以从很多层面上进行设计，从高层的软件结构一直到硬件中的晶体管。 如：

1. 问题定义，如重复定义，或过度需求。
2. 系统结构，将大的系统分成模块，也许是决定性能的最重要的单个元素。设计者需要完成简单的“粗略估计”，以确保程序的性能在正确的范围之内。
3. 算法和数据结构 O(n*log(n))和O(n^2)还是有很大的区别的。
4. 代码调优 这个就是经验了，比如提前申请内存啊，循环优化，顺序访问内存，内存对齐等等。
5. 系统软件 是否启用了所有的编译器优化？还有线程的优先级是否有保证？等等
6. 硬件 最近项目上需要做很多的优化工作，在经历了算法优化、代码优化和硬件优化等方案后，发现如果财大气粗的话，换硬件是优化的第一选择。

Note：如果仅需要做少量更改的时候，找到性能瓶颈后再做修改。

第七章 粗略估算

和第四章“编写正确的程序”一样，这一章也留给我很深的印象。

想想坊间流传的微软面试题吧：

密西西比河（长江）一天流出多少水？

第一次看到类似题目的时候，心想这大公司还对脑筋急转弯有爱好，果然是要找聪明的人。直到项目上在对整个框架优化的时候，才发现这类题目需要的“粗略估算”方法，对于分析大型软件框架时非常有作用。

作者给出的答复为， 河的出口为1英里（1.6公里）宽，20英尺（1英尺=0.305米）深，河水的流速是5英里/h，即120英里/天，则得到:

1英里1/250英里120英里/天 = 1/2英里³/天

如果是原来的我，可能看到这里就开始恍然大悟，抛下书本得意洋洋了。

可是这个答案真的对吗？我们有什么方法可以验证吗？ 书中给出了验证答案的几个方法：

1. 两个答案比一个答案好。 通过另一个角度，当然还是粗略估算，来计算结果。如上题可以通过：密西西比河的面积密西西比河每年的降水量/每年的天数，10001000*1/5000英里/年/400天/年 = 1/2英里³/天。
2. 快速检验。 这里介绍了“如何解题”中的“量纲检验”，即只有相同量纲的各项才能运算，否则不能运算。如之前的两个答案都是：英里*英里*英里/天 = 英里^3/天。
3. 经验法则。又称“72法则”，用于估算指数过程的增长非常方便。如果以年利率r%投资一笔钱y年，如果r*y=72，那么你的投资差不多会翻倍。

这些对于我们的粗略估算很有帮助，不过要记住，即使我们有了上面的方法，也不能保证我们的估算与实际结果一致，所以还要为我们的估算留下余地。

这样即使在我们的估算有误时，也不会过于影响我们的判断。

Little定律，队列中物体的平均数量为进入速率与平均停留时间的乘积。

第八章 算法设计技巧

本章通过解决一个经典问题“求连续子向量的最大和”，总结了一些算法设计的技巧。

• 保存状态，避免重复计算。

这也就是所谓的“空间换时间”吧。

• 将信息预处理至数据结构中

将能预先计算的内容提前运算，不要等到收到数据再做计算。

• 分治算法

• 扫描算法。与数组相关的问题经常可以通过思考“如何将x[0..i-1]的解扩展为x[0..i]的解”来解决。

• 累积

• 下界。只有确定完算法的下界后，才能确定自己的算法是最佳算法。

第九章 代码调优

过早的优化是万恶之源。 -- Donald Knuth

尽管我们的上帝说了这句话，但是boss和客户可不管你的万恶之源，只要产品慢，那就必须优化。当然，如果因为其他需要导致算法更改，那就意味着之前的工作可以重做了。

代码调优首先确定程序中开销最大的部分，然后进行少量的修改，以提高其运行速度。

自己在平时也看过一些优化方面的书，第一条都是确认"性能瓶颈"。毕竟，有了正确的目标，才能到达目的地嘛。

忘记之前在哪里看过一篇优化的文章，大概意思是，一个程序有A、B两部分，其中A耗时80%，B耗时20%。那么对某一部分优化之后的结果应该为:(tA*p + tB)/(tA+tB)，其中p为优化后的时间与优化之前的性能之比。 如果对B进行优化，p = 20%，那么整体优化后与优化前的比例为: (0.8+0.2*0.2)/(0.8+0.2) = 0.84。如果对A进行优化，可得(0.8*0.2+0.2)/(0.8+0.2)=0.36。 相比优化B，优化A有了一倍多的提升。

下面给出书中几个代码优化的例子：

问题1. 整数取模。由于取模运算耗时100ns，而其他算术运算只需10ns，所以可将取模运算替换为“减法”。

问题2. 函数、宏和内联代码。 对于有些编译器而言，将函数改为宏可以提升性能，然后对于另一些编译器，这种代码优化可能没有任何作用。不过对于C++程序员可以将某一函数进行编译，从而可以兼得函数的简洁语义和宏的低廉开销。

问题3. 顺序搜索。 可通过展开循环来提高性能。如：

for( i = 0; ; i += 8)
    if(x[i  ] == t ) { break}
    if(x[i+1] == t ) { i += 1; break}
    ...

在作者的机器上，性能提高了56%。对于老式计算机来说，降低开销可以加速10%~20%。对于现代计算机来说，将循环展开有助于避免管道阻塞，减少分值，增加指令级的并行。

问题4. 计算球面距离。修改数据结构，使用开销较低的欧氏距离而不是角度距离。

即，修改原有算法，采用速度更快的算法。