编程珠玑：续

多年以来，当程序员们推选出最心爱的计算机图书时，《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺，计算机科学大师JonBentley以其独有的洞察力和创造力，从磨砺程序员的实际问题中凝结出一篇篇不朽的编程“珠玑”，发表在《ACM通讯》最受欢迎的专栏中，最终结集为两部不朽的计算机科学经典名著，影响和激励着一代又一代程序员和计算机科学工作者。本书为续集，秉承了《编程珠玑》的风格，但涉及的主题更广，包括文档、小语言、性能监视、图形输出等。
　　作者选取许多具有典型意义的复杂编程和算法问题，生动描绘了计算机大师们在探索解决方案过程中发生的轶事、走过的弯路和不断精益求精的历程，引导读者像真正的程序员和软件工程师那样富有创新性地思考，并透彻阐述和总结了许多独特而精妙的设计原则、思考和解决问题的方法以及实用程序设计技巧。每章后所附习题极具挑战性和启发性，书末给出了简洁的解答。

作者：
Jon Bentley世界著名计算机科学家，被誉为影响算法发展的十位大师之一。他先后任职于卡内基-梅隆大学（1976~1982）、贝尔实验室（1982~2001）和Avaya实验室（2001年至今）。在卡内基-梅隆大学担任教授期间，他培养了包括Tcl语言设计者JohnOusterhout、Java语言设计者James Gosling、《算法导论》作者之一CharlesLeiserson在内的许多计算机科学大家。2004年荣获Dr. Dobb’s程序设计卓越奖。

第一部分  编 程 技 术
第1 章  性能监视工具　　3
1.1 计算素数　　3
1.2 使用性能监视工具　　7
1.3 专用的性能监视工具　　 8
1.4 开发性能监视工具　　10
1.5 原理　　11
1.6 习题　　11
1.7 深入阅读　　12
第2 章  关联数组　　13
2.1 Awk 中的关联数组　　 13
2.2 有穷状态机模拟器　　 16
2.3 拓扑排序　　17
2.4 原理　　20
2.5 习题　　21
2.6 深入阅读　　22
第3 章  程序员的忏悔　　 23
3.1 二分搜索　　24
3.2 选择算法　　26
3.3 子程序库　　28
3.4 原理　　30
3.5 习题　　31
第4 章  自描述数据　　33
4.1 名字—值对　　33
4.2 记录来历　　36
4.3 排序实验　　37
4.4 原理　　39
4.5 习题　　39
第二部分  实 用 技 巧
第5 章  劈开戈尔迪之结 43
5.1 小测验　　43
5.2 解答　　44
5.3 提示　　44
5.4 原理　　47
5.5 习题　　48
5.6 深入阅读　　49
5.7 调试（边栏） 　　49
第6 章  计算机科学箴言集 51
6.1 编码　　52
6.2 用户界面　　53
6.3 调试　　53
6.4 性能　　54
6.5 文档　　56
6.6 软件管理　　56
6.7 其他　　58
6.8 原理　　58
6.9 习题　　58
6.10 深入阅读　　60
第7 章  粗略估算　　61
7.1 头脑热身　　61
7.2 性能的经验法则　　62
7.3 Little 定律　　64
7.4  原理　　65
7.5 习题　　66
7.6 深入阅读　　67
7.7 日常速算（边栏）　　 67
第8 章  人员备忘录　　69
8.1 备忘录　　69
8.2 原理　　71
8.3 深入阅读　　71
第三部分  人性化I\/O
第9 章  小语言　　75
9.1 Pic 语言　　76
9.2 ?角　　79
9.3 Pic 预处理器　　81
9.4 用来实现Pic 的小语言83
9.5 原理　　87
9.6 习题　　88
9.7 深入阅读　　89
第10 章  文档设计　　91
10.1 表格　　92
10.2 三条设计原则　　94
10.3 插图　　94
10.4 文本　　96
10.5 合适的媒介　　98
10.6 原理　　100
10.7 习题　　101
10.8 深入阅读　　101
10.9 次要问题目录（边栏） 101
第11 章  图形化输出　　103
11.1 实例研究　　103
11.2 显示结果取样　　105
11.3 原理　　107
11.4 习题　　108
11.5 深入阅读　　110
11.6 拿破仑远征莫斯科（边栏） 110
第12 章  对调查的研究113
12.1 有关民意调查的问题113
12.2 语言　　114
12.3 图片　　117
12.4 原理　　119
12.5 习题　　120
第四部分  算 法
第13 章  绝妙的取样　　123
13.1 取样算法一瞥　　123
13.2 Floyd 算法　　124
13.3 随机排列　　125
13.4 原理　　127
13.5 习题　　127
13.6 深入阅读　　128
第14 章  编写数值计算程序129
14.1 问题　　129
14.2 牛顿迭代　　130
14.3 良好的起点　　132
14.4 代码　　133
14.5 原理　　135
14.6 习题　　135
14.7 深入阅读　　137
14.8 数值算法的力量（边栏） 137
第15 章  选择　　141
15.1 问题　　141
15.2 程序　　142
15.3 运行时间分析　　145
15.4 原理　　148
15.5 习题　　149
15.6 深入阅读　　151
附录A C 和Awk 语言　　153
附录B 子程序库　　157
部分习题?案　　165
索引　　　　181/p>

  序
本书作者JonBentley是美国著名的程序员和计算机科学家，他于20世纪70年代前后在很有影响力的《ACM通讯》（Communicationsof theACM）上以专栏的形式连续发表了一系列短文，成功地总结和提炼了自己在长期的计算机程序设计实践中积累下来的宝贵经验。这些短文充满了真知灼见，而且文笔生动、可读性强，对于提高职业程序员的专业技能很有帮助，因此该专栏大受读者欢迎，成为当时该学术期刊的王牌栏目之一。可以想象当时的情形，颇似早年金庸先生在《明报》上连载其武侠小说的盛况。后来在ACM的鼓励下，作者经过仔细修订和补充整理，对各篇文章做了精心编排，分别在1986年和1988年结集出版了ProgrammingPearls（《编程珠玑》）和More ProgrammingPearls（《编程珠玑（续）》）这两本书，二者均成为该领域的名著。《编程珠玑（第2版）》在2000年问世，书中的例子都改用C语言书写，并多处提到如何用C++和Java中的类来实现。《编程珠玑（续）》虽未再版，例子多以Awk语言写成，但其语法与C?近，容易看懂。
作者博览群书，旁征博引，无论是计算机科学的专业名著，如《计算机程序设计艺术》，还是普通的科普名著，如《啊哈！灵机一动》，都在作者笔下信手拈来、娓娓道出，更不用说随处可见的作者自己的真知灼见了。如果说《计算机程序设计艺术》这样的巨著代表了程序员们使用的“坦克和大炮”一类的重型武器，这两本书则在某种程度上类似于鲁迅先生所说的“匕首与投枪”一类的轻型武器，更能满足职业程序员的日常需要。或者说前者是武侠小说中提高内力修为的根本秘籍，后者是点拨临阵招数的速成宝典，二者同样都是克敌制胜的?宝，缺一不可。在无止境地追求精湛技艺这一点上，程序员、数学家和武侠们其实是相通的。
在美国，这两本书不仅被用作大学低年级数据结构与算法课程的教材，还用作高年级算法课程的辅助教材。例如，美国著名大学麻省理工学院的电气工程与计算机科学开放式核心课程算法导论就将这两本书列为推荐读物。这两本书覆盖了大学算法课程和数据结构课程的大部分内容，但是与普通教材的侧重点又不一样，不强调单纯从数学上进行分析的技巧，而是强调结合实际问题来进行分析、应用和实现的技巧，因此可作为大学计算机专业的算法、数据结构、软件工?等课程的教师参考用书和优秀课外读物。书中有许多真实的历史案例和许多极好的练习题以及部分练习题的提示与解答，非常适合自学。正如作者所建议的那样，阅读这两本书时，读者需要备有纸和笔，最好还有一台计算机在手边，边读边想、边想边做，这样才能将阅读这两本书的收益最大化。
人民邮电出版社引进版权，同时翻译出版了《编程珠玑（第2版）》和《编程珠玑（续）》，使这两个中译本珠联璧合，相信这不仅能极大地满足广大程序员读者的需求，还有助于提高国内相关课程的授课质量和学生的学习兴趣。
本书主要由钱丽艳和刘田翻译，翻译过程中得到了严浩、李梁、任铁男三位研究生的帮助，在此一并表示感谢。由于本书内容深刻，语言精妙，而译者的水平和时间都比较有限，错误和不当之处在所难免，敬请广大读者批评指正。/p>

 /p>

1章性能监视工具/p>

听诊器是一种简单工具，却给医生的工作带来了革命：它让内科医生能有效地监控病人的身体。性能监视工具（profiler）对程序起着同样的作用。
你现在用什么工具来研究程序？复杂的分析系统很多，既有交互式调试器，又有程序动画系统。正如CT扫描仪永远代替不了听诊器一样，复杂的软件也永远代替不了程序员用来监控程序的最简单工具——性能监视工具，我们用它了解程序各部分的执行频率。
本章先用两种性能监视工具来加速一个小程序（记住真正的目的是说明性能监视工具）。后续各节简要介绍性能监视工具的各种用途、非过程语言的性能监视工具，以及开发性能监视工具的技术。
1.1  计算素数
程序P1是个ANSI标准C程序，依次打印所有小于1000的素数（如果读者不了解C，请看附录A）。
程序P1
        int prime(int n)
        { int i;
999         for (i = 2; i< n; i++)
78022  if(n%i == 0)
831   return 0;
168         return 1;
        }
        main()
        {    inti, n；
1           n = 1000；
1           for (i = 2; i <= n; i++)
999  if (prime(i))
168   printf(\"%d\\", 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-11\/750上，计算出小于1000的所有素数约需几秒钟，但计算出小于10000的所有素数却需要3分钟。对这些计算的性能监视表明，大多数时间花在了测试因子上。因而下一个程序只对n考虑不超过的可能的整数因子。整型函数root先把整型参数转换成浮点型，然后调用库函数sqrt，最后再把浮点型结果转换回整型。程序P2包含两个旧函数和这个新函数root。
程序P2
         int root(intn)
5456    { return (int) sqrt((float) n);  }/p>

         int prime(intn)
         {   inti;
999          for (i =2;  i <= root(n);  i++)
5288            if (n % i == 0)
831                  return 0;
168          return1;
}/p>

         main()
        {    int i, n;
1            n = 1000;
1            for (i = 2;  i <= n;  i++)
999              if (prime(i))
168                   printf(\"%d\\", i);
}
修改显然是有效的：程序P2的行计数显示，只测试了5288个因子（程序P1的1\/14），总共调用了5456次root（测试了5288次整除性，168次由于i超出了root(n)而终止循环）。不过，虽然计数大大减少了，但是程序P2运行了5.8秒，而程序P1只运行了2.4秒（本节末尾的表中含有运行时间的更多细节）。这说明什么呢？
迄今为止，我们只看到了行计数（line-count）性能监视。过程时间（procedure-time）性能监视给出了较少的控制流细节，但更多地揭示了CPU时间：/p>

    %time   cumsecs      #call    ms\/call       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 prime(intn)
        {    int i, bound;
999          bound = root(n);
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整除的特殊检验，避免了近3\/4的开方运算。语句计数表明，被2整除的性质大约把一半的输入归入合数，被3整除把剩余输入的1\/3归入合数，被5整除再把剩下的这些数的1\/5归入合数。其次，只考虑奇数作为可能的因子，在剩余的数中避免了大约一半的整除检验。它比程序P3大约快两倍，但是也比P3的错误更多。下面是（带错的）程序P4，你能通过检查语句计数看出问题吗？
程序P4
         int root(intn)
265     {    return (int)sqrt((float) n);  }/p>

         int prime(intn)
        {    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 = root(n);
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 (prime(i))
165                   printf(\"%d\\", i);
     }
先前的程序找到168个素数，而程序P4只找到165个。丢失的3个素数在哪里？对了，我把3个数作为特殊情形，每个数都引入了一处错误：prime报告2不是素数，因为它被2整除。对于3和5，存在类似的错误。正确的检验是/p>

if (n % 2 == 0)
return (n  == 2);
依此类推。如果n被2整除，如果n是2就返回1，否则返回0。对于n=1000、10000和100000，程序P4的过程时间性能监视结果总结在下表中。
n 时间百分比
 sqrt prime 其他
1000 45 19 36
10 000 39 42 19
100 000
31 56 13
程序P5比程序P4快，并且有个好处：正确。它把费时的开方运算换成了乘法，如以下程序片段所示。
程序P5的片段
265            for  (i  = 7;  i*i  <= n;  i  =i+2)
1530                 if (n % i == 0)
100                       return 0;
165            return 1;
它还加入了对被2、3、5整除的正确检验。程序P5总的加速大约有20%。
最后的程序只对已被判定为素数的整数检验整除性；程序P6在1.4节，用Awk语言写成。C实现的过程时间性能监视结果表明，在n=1000时，49%的运行时间花在prime和main上（其余是输入\/输出）；而当n=100000时，88%的运行时间花在这两个过程上。
下面这个表总结了我们已经看到的这几个程序。表中还包含另外两个程序作为测试基准。程序Q1用习题答案2中的埃氏筛法程序计算素数。程序Q2测量输入\/输出开销。对于n=1000，它打印整数1, 2,…, 168；对于一般的n，它打印整数1, 2,…,P(n)，其中P(n)是比n小的素数的个数。
程    序 运行时间（秒），n=
 1000 10 000 100 000
P1，简单版本 2.4 169 ?
P2，只检验平方根以下 5.8 124  2850
P3，只计算一次开方 1.4 15 192
P4，特殊情形2、3、5 0.5 5.7 78
P5，用乘法代替开方 0.3 3.5 64
P6，只检验素数 0.3 3.3 47
Q1，简单筛法 0.2 1.2 10.4
Q2，打印1..P(n) 0.1 0.7 5.3
本节集中讲述了性能监视的一种用途：当你调优单个子过程或函数的性能时，性能监视工具能告诉你运行时间都花在了哪里。
1.2  使用性能监视工具
对于小程序来说，性能监视很容易实现，因此性能监视工具是可有可无的；但是对于开发大软件来说，性能监视工具则是不可或缺的。BrianKernighan曾经使用行计数性能监视工具，研究了一个用于解释Awk语言程序的4000行的C程序。那时这个Awk解释程序已广泛使用了多年。扫描该程序75页长的程序清单就会发现，大多数计数都是成百上千的，有些甚至上万。一段晦涩的初始化代码，计数接近百万。Kernighan对一个6行的循环做了几处修改，程序速度就提高了一倍。他自己可能永远也猜不出程序的问题源头所在，但是性能监视工具引导他找到了。
Kernighan的这一经历是相当典型的。在1.7节引用的论文中，Don Knuth给出了Fortran程序许多方面（包括性能监视）的经验研究。该论文中有一个被经常引用（而且常常是被错误地引用）的命题：“一个程序中不到4%的语句通常占用了一半以上的运行时间。”对许多语言和系统的大量研究表明，对于不处理I\/O密集型的大多数程序，大部分的运行时间花在了很小一部分代码上。这种模式是下述经验的基础：/p>

Knuth在论文中描述了用行计数性能监视工具进行自我分析的结果。性能监视结果表明，一半的运行时间花在了两个循环上。结果花了不到一小时修改了几行代码，就让这个性能监视工具的速度提高了一倍。
第14章描述的性能监视结果说明，一个1000行的程序把80%的时间花在一个5行的子程序上。把这个子程序改写成十几行，就让程序的速度提高了一倍。
1984年贝尔实验室的TomSzymanski打算给一个大系统提速，结果却使该系统慢了10%。他删除了修改的部分，然后多打开了一些性能监视选项以查明失败原因。他发现占用的存储空间增加到了原来的20倍，行计数显示存储空间的分配次数远多于释放次数。接下来用一条指令就纠正了错误，正确的实现让系统加速了一倍。
性能监视表明，操作系统一半的时间花在一个只有少数几条指令的循环上。改写微代码中的这个循环带来一个量级的提速，但是系统的吞吐量不变：性能组已经优化了系统的空闲循环！
这些经历引出了上一节粗略提到过的一个问题：应当在什么输入上监视程序的性能？查找素数的程序只有一个输入n，该输入强烈影响到时间性能监视：对于小的n，输入\/输出占大头；对于大的n，计算占大头。有的程序的性能监视结果对输入数据非常不敏感。我猜想大多数计算薪水的程序都有相当一致的性能监视结果，至少从2月到11月如此。但有的程序的性能监视结果会随输入不同有巨大变化。难道你从没有察觉到，你的系统被调整得在制造商的基准数据上运行起来风驰电掣，而处理起你的重要任务时却慢如蜗牛？仔细挑选你的输入数据吧。
性能监视工具对于性能之外的任务也有用。在找素数的练习中，它指出了程序P4的一个错误。行计数在估计测试覆盖面时极有价值，比如，如果出现零，则说明有代码未测试。DEC公司的DickSites这样描述性能监视的其他用途：“(1) 在两层微存储实现中，决定哪些微代码放到芯片上；(2) 贝尔北方研究院（BellNorthernResearch）的一位朋友某个周末在带有多重异步任务的实时电话交换软件系统上实现了语句计数。通过查看异常计数，他发现了现场安装的代码中存在6处错误，所有错误都涉及不同任务之间的交互。其中一处错误用常规调试技术无法成功追踪到，其余错误还没有被当作问题（也就是说，这些错误症状可能已经发生，但是没有人能够将其归结为具体的软件错误）。”
1.3  专用的性能监视工具
到目前为止我们所看到的性能监视工具的原理，适用于从汇编和Fortran直到Ada这样的程序设计语言，但是很多程序员现在使用更强大的语言。如何监视Lisp或APL程序的计算性能？又如何监视网络或数据库语言程序的计算性能？
我们打算用UNIX的管道（pipeline）作为更有趣的计算模型的例子。管道是一系列的过滤程序（filter）：当数据流经每个过滤程序时，对数据施加变换。下面这个经典的管道按照频率递减顺序打印某文件中使用最多的25个单词。/p>

cat  $*  ?
tr -cs A-Za-z ''\\012''  ?
tr A-Z a-z  ?
sort  ?
uniq   -c  ?
sort -r –n ?
sed 25q
当用这个管道在一本大约6万字的书中寻找25个最常见的单词时，我们监视这个管道的性能。输出的前6行是：/p>

3463 the
1855 a
1556 of
1374 to
1166 in
1104 and
   ...
下面是对VAX-11\/750上计算的“管道性能监视”：/p>

lines    words    chars
 10717 59701 342233
 57652 57651 304894
 57652 57651 304894
 57652 57651 304894
 4731 9461 61830
 4731 9461 61830
 25 50 209
左边几列说明每个阶段的数据：行数、单词数、字符数。右边部分描述了数据阶段之间的过滤程序：用秒表示的用户时间、系统时间以及真实时间，后面是命令本身。
这个性能监视结果给出了程序员感兴趣的许多信息。这个管道是快速的，处理150页的书只需3.5分钟。第一次排序花了这个管道57%的运行时间，这种经过仔细调优的实用程序很难再提速了。第二次排序只花了这个管道14%的时间，但是还有调优的余地。这个?能监视结果还发现了管道中隐藏的一处小错误。UNIX高手们会乐于找出引入空行的地方。
这个性能监视结果也透露了文件中单词的信息：共有57651个单词，但只有4731个不同的单词。在第一个翻译程序之后，每个单词有4.3个字母。输出表明，最常见的单词是“the”，占了文件的6%。6个最常见的单词占了文件的18%。对英语中最常见的100个单词做专门处理也许还能提高速度。试试看从这些计数中找出其他有趣的表面规律。
跟许多UNIX用户一样，我过去也用手工监视管道的性能，利用单词计数（wc）命令来统计文件，用time命令来统计进程。“管道性能监视工具”让这个任务自动化了。用管道和一些输入文件的名称作为输入，产生性能监视结果作为输出。2个小时和50行代码就足以建立这个性能监视工具。下一节详细阐述这个话题。
1.4  开发性能监视工具
开发一个真正的性能监视工具是件困难的事情。Peter Weinberger开发了C行计数性能监视工具，我们前面看到的输出就是这个工具产生的。他在几个月时间内断断续续干了好几周才完成这个项目。本节描述如何更容易地开发一个简化版本。
DickSites声称他的朋友“在某个周末实现了语句计数”。我觉得这简直难以置信，于是我决定要试着为附录A描述的Awk语言（这种语言还没有性能监视工具）开发一个性能监视工具。几小时后，当我运行程序P6的Awk版本时，我的性能监视工具生成了如下输出。
程序P6及性能监视工具生成的输出
BEGIN  {  <<<1>>>
     n =  1000
     x[0] = 2; xc = 1
     print 2
     for (i  =  3;  i <= n;  i++)  {  <<<998>>>
          if (prime(i))   {  <<<167>>>
               print i
          }
     }
     exit
}
function prime(n,   i)  { <<<998>>>
     for  (i=0; x[i]*x[i]<=n;  i++)  { <<<2801>>>
          if  (n % x[i]  ==  0)  { <<<831>>>
 return 0
          }
     }
     {  <<<167>>> }
     x[xc++]  = n
     return 1
}
在左花括号后尖括号内的数显示该语句块被执行了多少次。幸运的是，这些计数与C行计数器产生的计数一样。
我的性能监视工具包含两个5行的Awk程序。第一个程序读Awk源程序并且写一个新程序，其中在每个语句块开始的地方给不同的计数器加1；而在执行结束时，一个新的END动作（见附录A）把所有计数写入一个文件。当这样得出的程序运行时，就生成一个计数文件。第二个程序读出这些计数，把这些计数合并到源文本中。带性能监视的程序大约比原来的程序慢25%，而且并不是所有的Awk程序都能正确处理——为了监视几个程序的性能，我不得不做出整行（one-line）的修改。但对于所有这些缺点来说，搭起一个能运行的性能监视工具，花几小时并不算什么大投入。在AWKProgramming Language一书的7.2节给出了一个类似的Awk性能监视工具的细节，本书2.6节引用了这本书。
人们实现过一些快速性能监视工具，但鲜见报道。下面举几个例子。/p>

在1983年8月的BYTE杂志上，Leas和Wintz描述了一个性能监视工具，用一个20行的6800汇编语言程序来实现。
贝尔实验室的HowardTrickey在一小时内用Lisp实现了函数计数，办法是修改defun，在进入每个函数时给计数器加1。
1978年，Rob Pike 用20行Fortran程序实现了一个时间性能监视工具。在CALLPROFIL(10)之后，后续的CPU时间被计入计数器10。
在这些系统和许多其他系统上，在一晚上写出一个性能监视工具是可能的。在你第一次使用所得到的性能监视工具时，这个工具轻易就能节省超过一个晚上的工作量。
1.5  原理
本章只浮光掠影地介绍了性能监视。我介绍了最基础的内容，忽略了搜集数据的其他方式（比如硬件监视器）和其他显示方式（比如动画系统）。本章所要传达的信息同样是基本的。
? 使用性能监视工具。让本月成为性能监视工具月。请在随后几周内至少监视一个程序片段的性能，并且鼓励你的伙伴们也这样做。记住，当一个程序员屈尊来帮助一个小程序时，并不总是高瞻远瞩的。
? 开发性能监视工具。如果你还没有方便的性能监视工具，就自造一个吧。大多数系统都提供基本的性能监视操作。20世纪60年代不得不观察控制台灯光来获得信息的程序员，现在可从个人工作站的图形窗口获得同样的信息。一个小程序通常足以把系统的命令特性包装成方便的工具。
1.6  习题
1. 假设数组X[1..1000]中散布着随机实数。下面这个例程计算最小值和最大值：/p>

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先生注意到，如果一个元素是新的最大值，则这个元素不可能是最小值。因而他把两次比较写成/p>

if       X[I] > Max then Max :=X[I]
else if X[I] < Min then Min := X[I]/p>

这样平均起来将节省多少次比较？先猜猜答案，再通过实现和监视程序性能来找出答案。你猜得怎么样？
2. 下列问题与计算素数有关。
a. 程序P1到P6把运行时间缩短了两个数量级。你能进一步提高写出比性能吗？
b. 实现简单的埃氏筛法（Sieve ofEratosthenes）来计算所有小于n的素数。这个程序的主要数据结构是一个n比特的数组，初始值都为真。每发现一个素数时，数组中所有这个素数的倍数就设置为假。下一个素数就是数组中下一个为真的比特。
c. 上述筛法的运行时间作为n的函数是什么样子的？找出一个运行时间为O(n)的算法。
d. 给出一个非常大的整数（比如说几百比特长），你如何检验其是否为素数？
3. 一种简单的语句计数性能监视工具为每条语句设置一个计数器。描述一下如何使用更少的计数器来减少内存和运行时间。（我曾经用过Pascal系统监视一个程序的性能，结果把程序变慢为原来的1\/100；本章描述的行计数性能监视工具采用了本题的技巧，只让程序变慢几个百分点。）
4. 一种简单的过程时间性能监视工具这样估计每个过程所花的时间：在有规律的间隔下观察程序计数器（在我的系统上是每秒60次）。这个信息给出了程序文本每个部分所花的时间，但是没有给出哪个过程最费时间。有些性能监视工具给出了每个函数及其动态调用的子函数所花的时间。说明如何从运行时栈中搜集更多信息，以区分出调用函数和被调用函数所花的时间。给定这些数据后，你如何以有用的形式来显示这些数据？
5. 准确的数值有助于解释程序在单个数据集上的性能监视结果。但是当有很多数据时，长长的一串数字则可能掩盖数值中的信息。你如何显示程序或管道在100个不同输入上的性能监视结果？特别考虑一下数据的图形显示。
6. 1.4节中的程序P6是个正确的程序，其正确性却难以证明。问题出在哪里？如何解决这个问题？
1.7  深入阅读
Don Knuth的“Empirical Study of FortranPrograms”发表在1971年Software——Practice andExperience第一卷上（第105～133页）。关于“动态统计”的第3节讨论了行计数和过程时间计数，以及用这两种计数搜集的统计数据。第4节调优了17个关键的内循环，获得了从1.5~13.1倍的加速。在过去的十几年中，我每年至少要读一遍这篇经典论文，越读越觉得好，因此我强烈推荐这篇论文。/p>

 /p>

装　　帧：平装

开　　本：16开

纸　　张：胶版纸