《编程珠玑》学习笔记-第5、6章

第五章 编程小事

1、从伪代码到C程序：

 int binarysearch(DataType t){

int l,u,m;

l=0;

u=n-1;

while(l<=u){

m=(l+u)/2;

if(x[m]<t)

l=m+1;

else if(x[m]==t)

return m;

else if(x[m]>t)

u=m-1;

}

return -1;

2、测试工具:

(1) 手动测试，输入一些小实例、单步跟踪调试、print语句

(2) 自动测试：添加断言、编写测试程序

3、计时：计算N个不同元素构成的数组中进行一次成功的二分搜索所需要的平均运行时间。

while read(algnum,n,numtests)

for i=[0,n)

x[i]=i  /*初始化数组*/

starttime=clock()

for testnum=[0,numtests)  /*对数组中每一个元素执行numtests次搜索*/

for i=[0,n)

switch(algnum)  /*选择要测试的算法*/

case 1:assert(binarysearch1(i)==i)

case 2:assert(binarysearch2(i)==i)

click=clock()-starttime

print algnum,n,numteats,clicks,

clicks/(le9*CLOCKS_PER_SEC * n * numtests)

4、完成的程序：（1）将伪代码转换为编程语言（2）分析其正确性（3）实例测试，给定输入观察输出（4）设置断言（5）运行程序测试

5、原理：脚手架、编码、测试、调试、计时

第二部分性能

第六章 程序性能分析

本章由一个特定的程序引入，用系统化观点来研究系统设计的各个层面。

1、实例：计算重力场中多个物体相互作用的经典“n”体问题，给定物体的质量、初始位置和速度，该程序可以对三维空间中n个物体的运动进行仿真。

2、解决办法：程序需要计算每一个物体对任一其他物体的引力影响，因此每一时间步的移动计算时间复杂度为O(n²);

              n = 10000, t = 1000(时间步数)时，耗时约1年；    

Andrew Appel的论文将以上程序的运行时间由一年缩减为一天（加速系数= 400）。

3、提升程序效率：

>>算法和数据结构（二叉树）[加速系数 = 12]

>>算法调优（特殊函数识别处理粒子对）[加速系数 = 2]

>>数据结构重组（每个时间步对数据结构进行重新配置）[加速系数 = 2]

>>代码调优（32位单精度浮点数代替64位双精度浮点数、汇编语言改写关键函数）[加速系数 = 2、2.5]

>>硬件（浮点加速器）[加速系数 = 2]

其中各方面的加速系数分比为12，2，2，2，2.5，2，由此可见算法和数据结构的调整对于程序的加速共享最大。

4、总结而言，在设计层面上，若要对算法的性能进行改进，有以下几个层次：良好的问题定义– 系统结构 – 算法和数据结构 –代码调优–系统软件– 硬件；

5、原理:对于效率，改变算法或是调整队列规则都可以考虑，但是要先考虑一下所有可能的设计层面，然后选择性价比最高的那一个，投入最小的精力就可以获得最大加速系数的那个设计层面。但如果需要较大的加速，就需要对多个层面进行改进了。要有全局意识。