序
本书作者Jon
Bentley是美国著名的程序员和计算机科学家，他于20世纪70年代前后在很有影响力的《ACM通讯》（Communications
of the
ACM）上以专栏的形式连续发表了一系列短文，成功地总结和提炼了自己在长期的计算机程序设计实践中积累下来的宝贵经验。这些短文充满了真知灼见，而且文笔生动、可读性强，对于提高职业程序员的专业技能很有帮助，因此该专栏大受读者欢迎，成为当时该学术期刊的王牌栏目之一。可以想象当时的情形，颇似早年金庸先生在《明报》上连载其武侠小说的盛况。后来在ACM的鼓励下，作者经过仔细修订和补充整理，对各篇文章做了精心编排，分别在1986年和1988年结集出版了Programming
Pearls（《编程珠玑》）和More Programming
Pearls（《编程珠玑（续）》）这两本书，二者均成为该领域的名著。《编程珠玑（第2版）》在2000年问世，书中的例子都改用C语言书写，并多处提到如何用C++和Java中的类来实现。《编程珠玑（续）》虽未再版，例子多以Awk语言写成，但其语法与C相近，容易看懂。
作者博览群书，旁征博引，无论是计算机科学的专业名著，如《计算机程序设计艺术》，还是普通的科普名著，如《啊哈！灵机一动》，都在作者笔下信手拈来、娓娓道出，更不用说随处可见的作者自己的真知灼见了。如果说《计算机程序设计艺术》这样的巨著代表了程序员们使用的“坦克和大炮”一类的重型武器，这两本书则在某种程度上类似于鲁迅先生所说的“匕首与投枪”一类的轻型武器，更能满足职业程序员的日常需要。或者说前者是武侠小说中提高内力修为的根本秘籍，后者是点拨临阵招数的速成宝典，二者同样都是克敌制胜的法宝，缺一不可。在无止境地追求精湛技艺这一点上，程序员、数学家和武侠们其实是相通的。
在美国，这两本书不仅被用作大学低年级数据结构与算法课程的教材，还用作高年级算法课程的辅助教材。例如，美国著名大学麻省理工学院的电气工程与计算机科学开放式核心课程算法导论就将这两本书列为推荐读物。这两本书覆盖了大学算法课程和数据结构课程的大部分内容，但是与普通教材的侧重点又不一样，不强调单纯从数学上进行分析的技巧，而是强调结合实际问题来进行分析、应用和实现的技巧，因此可作为大学计算机专业的算法、数据结构、软件工程等课程的教师参考用书和优秀课外读物。书中有许多真实的历史案例和许多极好的练习题以及部分练习题的提示与解答，非常适合自学。正如作者所建议的那样，阅读这两本书时，读者需要备有纸和笔，最好还有一台计算机在手边，边读边想、边想边做，这样才能将阅读这两本书的收益最大化。
人民邮电出版社引进版权，同时翻译出版了《编程珠玑（第2版）》和《编程珠玑（续）》，使这两个中译本珠联璧合，相信这不仅能极大地满足广大程序员读者的需求，还有助于提高国内相关课程的授课质量和学生的学习兴趣。
本书主要由钱丽艳和刘田翻译，翻译过程中得到了严浩、李梁、任铁男三位研究生的帮助，在此一并表示感谢。由于本书内容深刻，语言精妙，而译者的水平和时间都比较有限，错误和不当之处在所难免，敬请广大读者批评指正。
1章性能监视工具
听诊器是一种简单工具，却给医生的工作带来了革命：它让内科医生能有效地监控病人的身体。性能监视工具（profiler）对程序起着同样的作用。
你现在用什么工具来研究程序？复杂的分析系统很多，既有交互式调试器，又有程序动画系统。正如CT扫描仪永远代替不了听诊器一样，复杂的软件也永远代替不了程序员用来监控程序的最简单工具——性能监视工具，我们用它了解程序各部分的执行频率。
本章先用两种性能监视工具来加速一个小程序（记住真正的目的是说明性能监视工具）。后续各节简要介绍性能监视工具的各种用途、非过程语言的性能监视工具，以及开发性能监视工具的技术。
1.1 计算素数
程序P1是个ANSI标准C程序，依次打印所有小于1000的素数（如果读者不了解C，请看附录A）。
程序P1
int primeint n
{ int i;
999 for i = 2; i
n; i++
78022 ifn%i == 0
831 return 0;
168 return
1;
}
main
{
int i, n；
1
n = 1000；
1
for i = 2; i = n; i++
999 if primei
168 printf"%d\n", i;
}
如果整型参数n是素数，上述prime函数返回1（真），否则返回0。这个函数检验2到n?1之间的所有整数，看其是否整除n。上述main过程用prime子程序来依次检查整数2～1000，发现素数就打印出来。
我像写任何一个C程序那样写好程序P1，然后在性能监视选项下进行编译。在程序运行之后，只要一个简单的命令就生成了前面所示的列表。（我稍微改变了一些输出的格式。）每行左侧的数由性能监视工具生成，用于说明相应的行执行了多少次。例如，main函数调用了1次，其中测试了999个整数，找出了168个素数。函数prime被调用了999次，其中168次返回1，另外831次返回0（快速验证：168+831=999）。prime函数共测试了78022个可能的因子，或者说为了确定素数性，对每个整数检查了大约78个因子。
程序P1是正确的，但是很慢。在VAX-11750上，计算出小于1000的所有素数约需几秒钟，但计算出小于10000的所有素数却需要3分钟。对这些计算的性能监视表明，大多数时间花在了测试因子上。因而下一个程序只对n考虑不超过的可能的整数因子。整型函数root先把整型参数转换成浮点型，然后调用库函数sqrt，最后再把浮点型结果转换回整型。程序P2包含两个旧函数和这个新函数root。
程序P2
int rootint
n
5456 { return int sqrtfloat n;
}
int primeint
n
{
int i;
999 for i
= 2; i = rootn; i++
5288
if n % i == 0
831
return 0;
168 return
1;
}
main
{ int i, n;
1
n = 1000;
1
for i = 2; i = n; i++
999
if primei
168
printf"%d\n", i;
}
修改显然是有效的：程序P2的行计数显示，只测试了5288个因子（程序P1的114），总共调用了5456次root（测试了5288次整除性，168次由于i超出了rootn而终止循环）。不过，虽然计数大大减少了，但是程序P2运行了5.8秒，而程序P1只运行了2.4秒（本节末尾的表中含有运行时间的更多细节）。这说明什么呢？
迄今为止，我们只看到了行计数（line-count）性能监视。过程时间（procedure-time）性能监视给出了较少的控制流细节，但更多地揭示了CPU时间：
%time
cumsecs #call
mscall name
82.7
4.77
_sqrt
4.5
5.03
999
0.26 _prime
4.3
5.28
5456
0.05 _root
2.6
5.43
_frexp
1.4
5.51
_ _doprnt
1.2
5.57
_write
0.9
5.63
mcount
0.6
5.66
_creat
0.6
5.69
_printf
0.4
5.72
1
25.00 _main
0.3
5.73
_close
0.3
5.75
_exit
0.3
5.77
_isatty
过程按照运行时间递减的顺序列出。时间上既显示出总秒数，也显示出占总时间的百分比。编译后记录下源程序中main、prime和root这3个过程的调用次数。再次看到这几个计数是令人鼓舞的。其他过程没有性能监视的库函数，完成各种输入输出和清理维护工作。第4列说明了带语句计数的所有函数每次调用的平均毫秒数。
过程时间性能监视说明，sqrt占用CPU时间的最多：该函数共被调用5456次，for循环的每次测试都要调用一次sqrt。程序P3通过把sqrt调用移到循环之外，使得在prime的每次调用中只调用一次费时的sqrt过程。
程序P3
int primeint
n
{ int i, bound;
999
bound = rootn;
999
for i = 2; i = bound; i++
5288
if n % i == 0
831
return 0;
168
return 1;
}
当n=1000时，程序P3的运行速度大约是程序P2的4倍，而当n = 100 000时则超过10倍。以n =
100000的情形为例，过程时间性能监视显示，sqrt占用了程序P2的88%的运行时间，但是只占用了程序P3的48%的运行时间。这好多了，但仍然是循环的累赘。
程序P4合并了另外两个加速措施。首先，程序P4通过对被2、3和5整除的特殊检验，避免了近34的开方运算。语句计数表明，被2整除的性质大约把一半的输入归入合数，被3整除把剩余输入的13归入合数，被5整除再把剩下的这些数的15归入合数。其次，只考虑奇数作为可能的因子，在剩余的数中避免了大约一半的整除检验。它比程序P3大约快两倍，但是也比P3的错误更多。下面是（带错的）程序P4，你能通过检查语句计数看出问题吗？
程序P4
int rootint
n
265 { return int
sqrtfloat n; }
int primeint
n
{ int i, bound;
999 if n %
2 == 0
500
return 0;
499 if n % 3 == 0
167
return 0;
332 if n % 5 ==
0
67
return 0;
265 bound = rootn;
265
for i = 7; i = bound; i = i+2
1530
if n % i == 0
100
return 0;
165
return 1;
}
main
{ int i, n;
1
n = 1000;
1
for i = 2; i = n; i++
999
if primei
165
printf"%d\n", i;
}
先前的程序找到168个素数，而程序P4只找到165个。丢失的3个素数在哪里？对了，我把3个数作为特殊情形，每个数都引入了一处错误：prime报告2不是素数，因为它被2整除。对于3和5，存在类似的错误。正确的检验是
Max := Min := X[1]
for I := 2 to 1000 do
if X[I] Max then Max :=
X[I]
if X[I] Min then Min := X[I]
B. C. Dull先生注意到，如果一个元素是新的最大值，则这个元素不可能是最小值。因而他把两次比较写成
if X[I] Max then Max :=
X[I]
else if X[I] Min then Min := X[I]
这样平均起来将节省多少次比较？先猜猜答案，再通过实现和监视程序性能来找出答案。你猜得怎么样？
2. 下列问题与计算素数有关。
a. 程序P1到P6把运行时间缩短了两个数量级。你能进一步提高写出比性能吗？
b. 实现简单的埃氏筛法（Sieve of
Eratosthenes）来计算所有小于n的素数。这个程序的主要数据结构是一个n比特的数组，初始值都为真。每发现一个素数时，数组中所有这个素数的倍数就设置为假。下一个素数就是数组中下一个为真的比特。
c. 上述筛法的运行时间作为n的函数是什么样子的？找出一个运行时间为On的算法。
d. 给出一个非常大的整数（比如说几百比特长），你如何检验其是否为素数？
3.
一种简单的语句计数性能监视工具为每条语句设置一个计数器。描述一下如何使用更少的计数器来减少内存和运行时间。（我曾经用过Pascal系统监视一个程序的性能，结果把程序变慢为原来的1100；本章描述的行计数性能监视工具采用了本题的技巧，只让程序变慢几个百分点。）
4.
一种简单的过程时间性能监视工具这样估计每个过程所花的时间：在有规律的间隔下观察程序计数器（在我的系统上是每秒60次）。这个信息给出了程序文本每个部分所花的时间，但是没有给出哪个过程最费时间。有些性能监视工具给出了每个函数及其动态调用的子函数所花的时间。说明如何从运行时栈中搜集更多信息，以区分出调用函数和被调用函数所花的时间。给定这些数据后，你如何以有用的形式来显示这些数据？
5.
准确的数值有助于解释程序在单个数据集上的性能监视结果。但是当有很多数据时，长长的一串数字则可能掩盖数值中的信息。你如何显示程序或管道在100个不同输入上的性能监视结果？特别考虑一下数据的图形显示。
6. 1.4节中的程序P6是个正确的程序，其正确性却难以证明。问题出在哪里？如何解决这个问题？
1.7 深入阅读
Don Knuth的“Empirical Study of Fortran
Programs”发表在1971年Software——Practice and
Experience第一卷上（第105～133页）。关于“动态统计”的第3节讨论了行计数和过程时间计数，以及用这两种计数搜集的统计数据。第4节调优了17个关键的内循环，获得了从1.5~13.1倍的加速。在过去的十几年中，我每年至少要读一遍这篇经典论文，越读越觉得好，因此我强烈推荐这篇论文。
……
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
