编程珠玑2-第1章 性能监视工具

winston

本章是从一个计算素数的问题开始，请看程序P1，右边的数字由性能监视工具生成，用于说明相应的行执行了多少次。
1 int prime(int n)
2 {    int i;
3     for(i=2;i<n;i++)        999
4         if(n%i==0)        78022
5             return 0;        831
6         return 1;        168
7     }
8     main()
9     {
10         int i,n;
11         n=1000;        1
12         for(i=2;i<=n;i++)        1
13             if(prime(i))        999
14                 printf("%d\n",i);        168
15     }
16     
刚看到这个代码我的的反应是，这本书不会就是捣鼓这些小东西吧，一眼望去，果不其然。改进后的程序P2如下
1 int root(int n)
2 {    return (int)sqrt((float)n);}        5456
3 int prime(int n)
4 {    int i;
5     for(i=2;i<=root(n);i++)        999
6         if(n%i==0)        5288
7             return 0;        831   
8         return 1;        168
9 }
接下来的一个改进就有点意思了，文中指出这个root(n)放在for循环里每次都需计算，故添加一个bound=root(n)，
然后改为for(i=2;i<=bound;i++)即为程序P3。我在想对于早期的编译器和程序设计，里面的优化机制还很少。
这种改进很可能提升效率，但是当前的编译器我就不好说了，就像是数据库里的sql查询优化一样，很多都添加了部分优化机制。
但是我相信针对程序内容本身的优化，还得人工进行，比如程序P4
1 int root(int n)
2 {    return (int)sqrt((float)n);}        
3 int prime(int n)
4 {    int i,bound;
5     if(n%2==0)
6         return n==2;   
7     if(n%3==0)
8         return n==3;
9     if(n%5==0)
10         return n==5;
11     bound=root(n);
12     for(i=7;i<=bound;i=i+2)   265
13         if(n%i==0)
14             return 0;
15         return 1;
16 }
17 main()
18 {        int i,n;
19         n=1000;
20         for(i=2;i<=n;i++)
21             if(prime(i))
22                 printf("%d\n",i);
23 }
由组合里的容斥原理可知，2到1000中能被2或3或5整除的数占了近3/4，这样以来可以减少3/4的开方，只执行了265次。
那个return n==也设计的相当巧妙，忍不住叫好。
最后作者还提出了把开方换成乘法的改进，即
for(i=7;i*i<=n;i=i+2)
本章例举了很多例子强调了使用性能监视工具在优化和调错方面的意义，但是没有给出设计性能监视工具的可行方法。
我不太清楚现成的监视工具比如C语言的 是否有。
一种非通用的方法是主动在代码中添加计数器用于记录执行次数。
其实在很多规律性算法中，某行代码的执行次数都可以估计出来，比如查找与排序算法。

本文链接