详情
本书是计算机科学方面的经典名著《编程珠玑》的姊妹篇，讲述了对于程序员有共性的知识。本书延续了《编程珠玑》的特色,通过一些精心设计的有趣而又颇具指导意义的程序，对实用程序设计技巧及基本设计原则进行透彻而睿智的描述，为复杂的编程问题提供清晰而完备的解决思路。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例，这些内容结合成一个有机的整体，如一串串珠玑展示给程序员。
书名：编程珠玑（续）
ISBN：978-7-115-51629-9
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美]乔恩•本特利（Jon Bentley）
译 钱丽艳 刘 田 等
责任编辑 杨海玲
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
Authorized translation from the English language edition, entitled MORE PROGRAMMING PEARLS: CONFESSIONS OF A CODER, 1st Edition, ISBN: 0201118890 by BENTLEY, JON, published by Pearson Education, Inc, Copyright © 1988 by AT&T Bell Laboratories.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from Pearson Education, Inc.
CHINESE SIMPLIFIED language edition published by POSTS & TELECOM PRESS, Copyright © 2019.
本书中文简体字版由Pearson Education Inc授权人民邮电出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。
本书封面贴有Pearson Education（培生教育出版集团）激光防伪标签，无标签者不得销售。
版权所有，侵权必究。
本书是计算机科学方面的经典名著《编程珠玑》的姊妹篇，讲述了对于程序员有共性的知识。本书延续了《编程珠玑》的特色，通过一些精心设计的有趣而又颇具指导意义的程序，对实用程序设计技巧及基本设计原则进行透彻而睿智的描述，为复杂的编程问题提供清晰而完备的解决思路。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例，这些内容结合成一个有机的整体，如一串串珠玑展示给程序员。
本书对各个层次的程序员都具有很高的阅读价值。
本书作者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章至第4章描述操纵程序的技术；第5章至第8章给出了一些程序员的实用技巧，这是本书技术性最低的部分；第9章至第12章讲解输入和输出设计；第13章至第15章介绍了3个有用的子程序。这些分类主题在每个部分的引言中进行了详细说明。
本书大多数章都是以我在《ACM通讯》杂志中的“编程珠玑”（Programming Pearls）专栏文章为基础的。各部分的引言中描述了这些文章的发表历史。既然已经发表过，为什么我还要费劲写这本书呢？自首次发表以来，这些专栏文章发生了很大变化，有了数千处小改进：有了新的问题和解决方案，纠正了小错误，并采纳了很多读者的意见。与此同时，我删除了一些旧的内容以免重复，并加入了很多新的内容，其中有一章是全新的。
然而，写本书的最大理由是，我想把各章组成一个有机的整体，我想展示一整串珠玑。我1986年出版的《编程珠玑》是类似的13篇短文的结集，围绕性能这个中心主题来组织，该主题在最早两年的《ACM通讯》专栏中占据了突出位置。本书中也有几章再次谈及效率的话题，但全书考察的编程领域范围要大得多。
读者阅读本书时不要太快，一次一章，仔细地读。试解一下书中提出的问题——有些问题并不像看起来那样容易。有些章末尾的“深入阅读”并不是学术意义上的参考文献列表，而是我推荐的一些好书，这些书是我个人藏书的重要部分。
我很高兴能借此机会感谢许多人所作的重要贡献。感谢Al Aho、Peter Denning、Brian Kernighan和Doug McIlroy对各章提出了详细的意见。我还要感谢以下诸位提出有益的见解：Bill Cleveland、Mike Garey、Eric Grosse、Gerard Holzmann、Lynn Jelinski、David Johnson、Arno Penzias、Ravi Sethi、Bjarne Stroustrup、Howard Trickey和Vic Vyssotsky。感谢允许我引用他们信件的几个人，特别是Peter Denning、Bob Floyd、Frank Starmer、Vic Vyssotsky和Bruce Weide。我特别要感谢ACM鼓励我把专栏文章出版成书，还要感谢《ACM通讯》的许多读者，他们对原始专栏文章提出了不少意见，使得本书这个扩充版本的出版十分必要。贝尔实验室（特别是其计算科学研究中心）在我写这些专栏文章时，提供了极佳的支持环境。感谢所有的人。
Jon Bentley
于新泽西州Murray Hill
本书由异步社区出品，社区（https://www.epubit.com/）为您提供后续服务。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可（见下图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。
如果您来自学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
我可没有耐心把最好的留到最后，这4章讨论程序员工作中最精彩的部分：你盯着计算机屏幕，敲着键盘度过的那些美好时光。
第1章说明如何使用性能监视工具（profiler）洞察程序的动态行为，第2章讨论一种强大的数据结构——关联数组（associative array），第3章描述用来测试和调试小的子程序的脚手架（scaffolding），第4章给出让数据文件自描述（self-describing）的方法。
这些技术都是用来处理真实程序的，所以要用真实系统上的真实语言来说明。第1章用C语言，第2章和第3章包含几个Awk程序。所有例子都使用了上述某种语言。附录A为不熟悉这些程序的读者简单描述了C和Awk。虽然本书只使用了上述语言进行说明，但所介绍的技术可用在任何系统上。
第1章发表在1987年7月的《ACM通讯》，第2章、第3章与附录A和附录B的早期版本一起发表于1985年6月和7月两期，第4章发表在1987年6月那一期。
本部分内容
听诊器是一种简单工具，却给医生的工作带来了革命：它让内科医生能有效地监控病人的身体。性能监视工具（profiler）对程序起着同样的作用。
你现在用什么工具来研究程序？复杂的分析系统很多，既有交互式调试器，又有程序动画系统。正如CT扫描仪永远代替不了听诊器一样，复杂的软件也永远代替不了程序员用来监控程序的最简单工具——性能监视工具，我们用它了解程序各部分的执行频率。
本章先用两种性能监视工具来加速一个小程序（记住真正的目的是说明性能监视工具）。后续各节简要介绍性能监视工具的各种用途、非过程语言的性能监视工具，以及开发性能监视工具的技术。
程序P1是个ANSI标准C程序，依次打印所有小于1 000的素数（如果读者不了解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()
{ int i, n；
1 n = 1000；
1 for (i = 2; i <= n; i++)
999 if (prime(i))
168 printf("%d\n", i);
}如果整型参数n是素数，上述prime函数返回1（真），否则返回0。这个函数检验2到n−1之间的所有整数，看其是否整除n。上述main过程用prime子程序来依次检查整数2～1 000，发现素数就打印出来。
我像写任何一个C程序那样写好程序P1，然后在性能监视选项下进行编译。在程序运行之后，只要一个简单的命令就生成了前面所示的列表。（我稍微改变了一些输出的格式。）每行左侧的数由性能监视工具生成，用于说明相应的行执行了多少次。例如，main函数调用了1次，其中测试了999个整数，找出了168个素数。函数prime被调用了999次，其中168次返回1，另外831次返回0（快速验证：168+831=999）。prime函数共测试了78 022个可能的因子，或者说为了确定素数性，对每个整数检查了大约78个因子。
程序P1是正确的，但是很慢。在VAX-11/750上，计算出小于1 000的所有素数约需几秒钟，但计算出小于10 000的所有素数却需要3分钟。对这些计算的性能监视表明，大多数时间花在了测试因子上。因而下一个程序只对n考虑不超过
的可能的整数因子。整型函数root先把整型参数转换成浮点型，然后调用库函数sqrt，最后再把浮点型结果转换回整型。程序P2包含两个旧函数和这个新函数root。
程序P2
int root(int n)
5456 { return (int) sqrt((float) n); }
int prime(int n)
{ int i;
999 for (i = 2; i <= root(n); 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 (prime(i))
168 printf("%d\n", i);
}修改显然是有效的：程序P2的行计数显示，只测试了5 288个因子（程序P1的1/14），总共调用了5 456次root（测试了5 288次整除性，168次由于i超出了root(n)而终止循环）。不过，虽然计数大大减少了，但是程序P2运行了5.8秒，而程序P1只运行了2.4秒（本节末尾的表中含有运行时间的更多细节）。这说明什么呢？
迄今为止，我们只看到了行计数（line-count）性能监视。过程时间（procedure-time）性能监视给出了较少的控制流细节，但更多地揭示了CPU时间：
%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时间的最多：该函数共被调用5 456次，for循环的每次测试都要调用一次sqrt。程序P3通过把sqrt调用移到循环之外，使得在prime的每次调用中只调用一次费时的sqrt过程。
程序P3
int prime(int n)
{ 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 = 1 000时，程序P3的运行速度大约是程序P2的4倍，而当n = 100 000时则超过10倍。以n = 100 000的情形为例，过程时间性能监视显示，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(int n)
265 { return (int) sqrt((float) n); }
int prime(int 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 = 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\n", i);
}先前的程序找到168个素数，而程序P4只找到165个。丢失的3个素数在哪里？对了，我把3个数作为特殊情形，每个数都引入了一处错误：prime报告2不是素数，因为它被2整除。对于3和5，存在类似的错误。正确的检验是
if (n % 2 == 0)
return (n == 2);依次类推。如果n被2整除，如果n是2就返回1，否则返回0。对于n = 1 000、10 000和100 000，程序P4的过程时间性能监视结果总结在下表中。
| n | 时间百分比 | ||
|---|---|---|---|
sqrt |
prime |
其他 | |
| 1 000 | 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 = 1 000时，49%的运行时间花在prime和main上（其余是输入/输出）；而当n = 100 000时，88%的运行时间花在这两个过程上。
下面这个表总结了我们已经看到的这几个程序。表中还包含另外两个程序作为测试基准。程序Q1用习题答案2中的埃氏筛法程序计算素数。程序Q2测量输入/输出开销。对于n=1 000，它打印整数1, 2,…, 168；对于一般的n，它打印整数1, 2,…, P(n)，其中P(n)是比n小的素数的个数。
| 程序 | 运行时间（秒），n = | ||
|---|---|---|---|
| 1 000 | 10 000 | 100 000 | |
| P1，简单版本 | 2.4 | 169 | ? |
| P2，只检验平方根以下 | 5.8 | 124 | 2 850 |
| 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 |
本节集中讲述了性能监视的一种用途：当你调优单个子过程或函数的性能时，性能监视工具能告诉你运行时间都花在了哪里。
对于小程序来说，性能监视很容易实现，因此性能监视工具是可有可无的；但是对于开发大软件来说，性能监视工具则是不可或缺的。Brian Kernighan[1]曾经使用行计数性能监视工具，研究了一个用于解释Awk语言程序的4 000行的C程序。那时这个Awk解释程序已广泛使用了多年。扫描该程序75页长的程序清单就会发现，大多数计数都是成百上千的，有些甚至上万。一段晦涩的初始化代码，计数接近百万。Kernighan对一个6行的循环做了几处修改，程序速度就提高了一倍。他自己可能永远也猜不出程序的问题源头所在，但是性能监视工具引导他找到了。
Kernighan的这一经历是相当典型的。在1.7节引用的论文中，Don Knuth[2]给出了Fortran程序许多方面（包括性能监视）的经验研究。该论文中有一个被经常引用（而且常常是被错误地引用）的命题：“一个程序中不到4%的语句通常占用了一半以上的运行时间。”对许多语言和系统的大量研究表明，对于不处理I/O密集型的大多数程序，大部分的运行时间花在了很小一部分代码上。这种模式是下述经验的基础：
Knuth在论文中描述了用行计数性能监视工具进行自我分析的结果。性能监视结果表明，一半的运行时间花在了两个循环上。结果花了不到一小时修改了几行代码，就让这个性能监视工具的速度提高了一倍。
第14章描述的性能监视结果说明，一个1 000行的程序把80%的时间花在一个5行的子程序上。把这个子程序改写成十几行，就让程序的速度提高了一倍。
1984年贝尔实验室的Tom Szymanski打算给一个大系统提速，结果却使该系统慢了10%。他删除了修改的部分，然后多打开了一些性能监视选项以查明失败原因。他发现占用的存储空间增加到了原来的20倍，行计数显示存储空间的分配次数远多于释放次数。接下来用一条指令就纠正了错误，正确的实现让系统加速了一倍。
性能监视表明，操作系统一半的时间花在一个只有少数几条指令的循环上。改写微代码中的这个循环带来一个量级的提速，但是系统的吞吐量不变：性能组已经优化了系统的空闲循环！
这些经历引出了上一节粗略提到过的一个问题：应当在什么输入上监视程序的性能？查找素数的程序只有一个输入n，该输入强烈影响到时间性能监视：对于小的n，输入/输出占大头；对于大的n，计算占大头。有的程序的性能监视结果对输入数据非常不敏感。我猜想大多数计算薪水的程序都有相当一致的性能监视结果，至少从2月到11月如此。但有的程序的性能监视结果会随输入不同有巨大变化。难道你从没有察觉到，你的系统被调整得在制造商的基准数据上运行起来风驰电掣，而处理起你的重要作业时却慢如蜗牛？仔细挑选你的输入数据吧。
性能监视工具对于性能之外的任务也有用。在找素数的练习中，它指出了程序P4的一个错误。行计数在估计测试覆盖面时极有价值，比如，如果出现零，则说明有代码未测试。DEC公司的Dick Sites这样描述性能监视的其他用途：“(1) 在两层微存储实现中，决定哪些微代码放到芯片上；(2) 贝尔北方研究院（Bell Northern Research）的一位朋友某个周末在带有多重异步任务的实时电话交换软件系统上实现了语句计数。通过查看异常计数，他发现了现场安装的代码中存在6处错误，所有错误都涉及不同任务之间的交互。其中一处错误用常规调试技术无法成功追踪到，其余错误还没有被当作问题（也就是说，这些错误症状可能已经发生，但是没有人能够将其归结为具体的软件错误）。”
到目前为止我们所看到的性能监视工具的原理，适用于从汇编和Fortran直到Ada这样的程序设计语言，但是很多程序员现在使用更强大的语言。如何监视Lisp或APL程序的计算性能？又如何监视网络或数据库语言程序的计算性能？
我们打算用UNIX的管道（pipeline）作为更有趣的计算模型的例子。管道是一系列的过滤程序（filter）：当数据流经每个过滤程序时，对数据施加变换。下面这个经典的管道按照频率递减顺序打印某文件中使用最多的25个单词[3]。
cat $* ¦
tr -cs A-Za-z '\012' ¦
tr A-Z a-z ¦
sort ¦
uniq -c ¦
sort -r -n ¦
sed 25q当用这个管道在一本大约6万字的书中寻找25个最常见的单词时，我们监视这个管道的性能。输出的前6行是：
3463 the
1855 a
1556 of
1374 to
1166 in
1104 and
...下面是对VAX-11/750上计算的“管道性能监视”：
lines words chars times
10717 59701 342233 14.4u 2.3s 18r tr -cs A-Za-z \012
57652 57651 304894 11.9u 2.2s 15r tr A-Z a-z
57652 57651 304894 104.9u 7.5s 123r sort
57652 57651 304894 24.5u 1.6s 27r uniq -c
4731 9461 61830 27.0u 1.6s 31r sort -rn
4731 9461 61830 0.0u 0.2s 0r sed 25q
25 50 209左边几列说明每个阶段的数据：行数、单词数、字符数。右边部分描述了数据阶段之间的过滤程序：用秒表示的用户时间、系统时间以及真实时间，后面是命令本身。
这个性能监视结果给出了程序员感兴趣的许多信息。这个管道是快速的，处理150页的书只需3.5分钟。第一次排序花了这个管道57%的运行时间，这种经过仔细调优的实用程序很难再提速了。第二次排序只花了这个管道14%的时间，但是还有调优的余地[4]。这个性能监视结果还发现了管道中隐藏的一处小错误。UNIX高手们会乐于找出引入空行的地方。
这个性能监视结果也透露了文件中单词的信息：共有57 651个单词，但只有4 731个不同的单词。在第一个翻译程序之后，每个单词有4.3个字母。输出表明，最常见的单词是“the”，占了文件的6%。6个最常见的单词占了文件的18%。对英语中最常见的100个单词做专门处理也许还能提高速度。试试看从这些计数中找出其他有趣的表面规律。
跟许多UNIX用户一样，我过去也用手工监视管道的性能，利用单词计数（wc）命令来统计文件，用time命令来统计进程。“管道性能监视工具”让这个任务自动化了。 用管道和一些输入文件的名称作为输入， 产生性能监视结果作为输出。 2小时和50行代码就足以建立这个性能监视工具。下一节详细阐述这个话题。
开发一个真正的性能监视工具是件困难的事情。Peter Weinberger[5]开发了C行计数性能监视工具，我们前面看到的输出就是这个工具产生的。他在几个月时间内断断续续干了好几周才完成这个项目。本节描述如何更容易地开发一个简化版本。
Dick Sites声称他的朋友“在某个周末实现了语句计数”。我觉得这简直难以置信，于是我决定要试着为附录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）的修改。但对于所有这些缺点来说，搭起一个能运行的性能监视工具，花几小时并不算什么大投入。在AWK Programming Language一书的7.2节给出了一个类似的Awk性能监视工具的细节，本书2.6节引用了这本书。
人们实现过一些快速性能监视工具，但鲜见报道。下面举几个例子。
在1983年8月的BYTE杂志上，Leas和Wintz描述了一个性能监视工具，用一个20行的6 800汇编语言程序来实现。
贝尔实验室的Howard Trickey在一小时内用Lisp实现了函数计数，办法是修改defun，在进入每个函数时给计数器加1。
1978年，Rob Pike[6]用20行Fortran程序实现了一个时间性能监视工具。在CALL PROFIL(10)之后，后续的CPU时间被计入计数器10。
在这些系统和许多其他系统上，在一晚上写出一个性能监视工具是可能的。在你第一次使用所得到的性能监视工具时，这个工具轻易就能节省超过一个晚上的工作量。
本章只浮光掠影地介绍了性能监视。我介绍了最基础的内容，忽略了搜集数据的其他方式（比如硬件监视器）和其他显示方式（比如动画系统）。本章所要传达的信息同样是基本的。
1．假设数组X[1..1000]中散布着随机实数。下面这个例程计算最小值和最大值：
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的函数是什么样子的？找出一个运行时间为O(n)的算法。
d．给出一个非常大的整数（比如说几百比特长），你如何检验其是否为素数？
3．一种简单的语句计数性能监视工具为每条语句设置一个计数器。描述一下如何使用更少的计数器来减少内存和运行时间。（我曾经用过Pascal系统监视一个程序的性能，结果把程序变慢为原来的1/100；本章描述的行计数性能监视工具采用了本题的技巧，只让程序变慢几个百分点。）
4．一种简单的过程时间性能监视工具这样估计每个过程所花的时间：在有规律的间隔下观察程序计数器（在我的系统上是每秒60次）。这个信息给出了程序文本每个部分所花的时间，但是没有给出哪个过程最费时间。有些性能监视工具给出了每个函数及其动态调用的子函数所花的时间。说明如何从运行时栈中搜集更多信息，以区分出调用函数和被调用函数所花的时间。给定这些数据后，你如何以有用的形式来显示这些数据？
5．准确的数值有助于解释程序在单个数据集上的性能监视结果。但是当有很多数据时，长长的一串数字则可能掩盖数值中的信息。你如何显示程序或管道在100个不同输入上的性能监视结果？特别考虑一下数据的图形显示。
6．1.4节中的程序P6是个正确的程序，其正确性却难以证明。问题出在哪里？如何解决这个问题？
Don Knuth的“Empirical Study of Fortran Programs”发表在1971年Software ——Practice and Experience第一卷上（第105～133页）。关于“动态统计”的第3节讨论了行计数和过程时间计数，以及用这两种计数搜集的统计数据。第4节调优了17个关键的内循环，获得了从1.5~13.1倍的加速。在过去的十几年中，我每年至少要读一遍这篇经典论文，越读越觉得好，因此我强烈推荐这篇论文。
[1] Brian Kernighan（1942—），著名计算机科学家，现为普林斯顿大学教授。他与人合作创造了Awk和AMPL编程语言，对Unix和C语言的设计也有很大贡献。他还与人合写了多部计算机名著，包括与Ritchie合著的The C Programming Language。——编者注
[2] Don Knuth（1938—），中文名高德纳，著名计算机科学家，斯坦福大学荣休教授。因对算法分析和编程语言设计领域的贡献获1974年图灵奖。他是名著《计算机程序设计艺术》的作者，设计了TEX排版系统。——编者注
[3] 这7个过滤程序执行下列任务：(1) 连接所有输入文件；(2) 让每行包含一个单词，办法是把字母表以外的符号（-c）翻译成新行（ASCII八进制12），去掉重复的空行（-s）；(3) 把大写翻译成小写；(4) 排序，以便把相同的单词归并在一起；(5) 把连续的相同单词换成一个代表单词及其计数（-c）；(6) 按照数值（-n）递减（-r）顺序来排序；(7) 经过一个流编辑器，在打印25行后退出（q）。本书10.5节用图片描述了上述第(4)、(5)、(6)步中的sort ¦ uniq –c ¦ sort组合。
[4] 第二次排序花了第一次排序25%的时间，却只处理了输入行数的8%——数值（-n）标记很费时间。当我们在单列输入上监视这个管道的性能时，第二次排序几乎与第一次排序花一样的时间。这个性能监视的结果对输入数据很敏感。
[5] Peter Weinberger，著名计算机科学家，现在谷歌任职。他是Awk语言的设计者之一（Awk中的w），曾任贝尔实验室计算机科学研究部主任。——编者注
[6] Rob Pike（1956—），著名计算机科学家，现任职于谷歌。他参与了Unix操作系统的开发，并领导了分布式操作系统Plan 9和Inferno以及Limbo语言的设计。他与Kernighan合撰了名著《程序设计实战》。——编者注
人类学家说，语言深刻地影响了世界观。一般把这个观察结果称为“Whorf假说”[1]，也经常把它总结为“语言塑造了人的思想”。
跟大多数程序员一样，我使用的Algol系列的语言塑造了我的计算思维。对于像我这样的程序员来说，PL/1、C和Pascal看起来都很相似，我们不难把这样的代码翻译成COBOL或Fortran的代码。用这些语言能轻易地表达我们旧的、习以为常的思维模式。
另外一些语言则挑战了我们对于计算的看法。我们感到惊奇的是：Lisp用户们用S表达式和递归来神奇地工作，APL迷们用一组长向量的外积来为世界建模，Snobol程序员把任何问题都变成一个很大的字符串。我们这些Algol系列的程序员可能会发现，研究这些“异族文化”是痛苦的，但是这种体验一般会增长我们的见识。
本章讨论Algol传统之外的一种语言特性：关联数组（associative array）。我们熟悉的数组都用数值作下标，而关联数组则允许像count [“cat”]这样的引用。这样的数据结构出现在Snobol和Rexx（一种IBM命令解释器）这样的语言中，它允许我们用简单的程序来表达复杂的算法。这些数组与Algol相似到可以很快被理解的程度，又新到足以挑战我们思维习惯的程度。
本章将讨论Awk语言提供的关联数组。虽然Awk的大多数成分都来自Algol传统，但是关联数组和其他几个特性还是值得研究的。下面这一节介绍Awk的关联数组；后续几节描述两个重要的程序，这两个程序用大多数Algol系列的语言来写都是很麻烦的，却可以用Awk优雅地表达出来。
附录A中概述了Awk语言。我们将通过研究一个程序来简要复习一下这个语言，这个程序找出姓名文件中可疑的项。这个程序的每一行都是一个“模式-动作”对。对于每个输入行，如果这个输入行与左侧的一个模式匹配，则执行右侧括号中包含的动作。这个完整的Awk程序只包含3行代码：
length($1) > 10 { e++; print "long name in line", NR}
NF != 1 { e++; print "bad name count in line", NR}
END { if (e > 0) print "total errors: ", e }第一个模式捕捉长的名字。如果第一个字段（名为$1）超过10个字符，则相应的行为是对e增1，并使用内建变量NR（记录个数或行数）打印一条警告信息。变量e统计错误个数，Awk通常将所有变量初始化为零。第二个“模式-动作”对捕捉那些没有恰好包含一个名字的行（内建变量NF统计输入行中字段的数量）。第三个动作在输入的结尾执行，用于打印错误的个数。
关联数组并不在Awk内核之中，许多Awk程序并不使用它。但这些数组很巧妙地集成到了语言之中：如同其他变量一样，数组不用被声明，它在第一次使用时自动初始化。
现在转向有关名字的第二个问题：给定包含n个名字的文件，生成全部n2个名字对。我知道一些人曾用这样的程序为他们的孩子选取名和中名。如果输入文件包含名字Billy、Bob和Willy，那么输出将引导父母为孩子选择一个更悦耳的名字，比如Billy Bob而不是Billy Willy。
这个程序使用变量n计数当前已看到的名字个数。和所有Awk变量一样，其初始值为零。第一个语句在输入的每一行上都执行，注意n在使用之前加1。
{ name[++n] = $1 }
END { for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
print name[i], name[j]
}输入文件被读取后，名字存储在name[1]到name[n]中。END动作用两层for循环打印名字对。注意，尽管该程序只使用数值下标[2]，但却不必事先声明name数组的大小。
程序产生许多输出，特别是在输入文件中多次出现某些名字的情况下。因此，下一个程序使用一个字符串索引的数组来清理输入文件。完整的程序如下：
{ if ( count[$1]++ == 0 ) print $1 }一个名字第一次读取时它的count值为零，于是它被输出，并增加相应的数组元素。该名字的后续出现被读到时，其count值变大但不做任何额外动作。程序结束后，count的下标恰好代表了名字的集合。
这一事实让我们可以将之前的两个程序合为一个：给定一个名字文件（可能有重复的），下面的程序打印所有的名字对。
{ name[$1] = 1 }
END { for (i in name)
for (j in name)
print i, j
}关联数组name代表名字集合，其中所有值都是1。信息包含在数组索引中，可以用下述形式的循环来检索：
for ( i in name ) statement该循环在所有i值上重复执行statement。作为name的下标，i恰好代表输入文件里的名字。该循环以任意的顺序列举所有的名字，名字通常是不排序的。（Awk的确为UNIX系统排序提供了一个方便的接口，但这已经超出了本章的范围。）
下一个程序将应用从托儿所转移到了厨房。购物清单
chips 3
dip 2
chips 1
cola 5
dip 1其实应按项合并得到更简便的形式：
dip 3
cola 5
chips 4下面的程序完成这一任务：
{ count[$1] = count[$1] + $2 }
END { for (i in count) print i, count[i] }1.3节给出了一个程序，统计文档中每个单词出现的次数。下面的程序用Awk中的字段非常简单地定义单词为用空白分隔的字符序列。因此，字符串"Words"、"words"和"words;"是3个不同的单词。
{ for (i = 1; i <= NF; i++) count[$i]++ }
END { for (i in count) print count[i], i }这个程序在VAX-11/750上用了40秒的CPU时间来处理本章的一份草稿中的4 500个单词。出现频率最高的3个单词是“the”（213次）、“to”（110次）和“of”（104次）。11.1节将回到有关这个程序运行时间的问题上来。
下面这个简单的拼写检查器报告输入文件中所有不在字典文件dict中的单词。预处理使用Awk的getline命令将字典读入数组goodwords中：
BEGIN { while (getline <"dict") goodwords[$1] = 1 }
{ for (i = 1; i <= NF; i++)
if (!($i in goodwords))
badwords[$i] = 1
}
END { for (i in badwords) print i }主要的处理过程收集badwords，后处理过程打印违例的词。测试
if ( $i in goodwords ) ...当第i个字段是数组goodwords的下标时为真，而非运算符!将这一条件取反。不熟悉Awk的程序员或许用过更简单的条件测试
if ( goodwords[$i] == 0 ) ...这一条件测试的答案是一样的，但却会产生不必要的副作用——向goodwords数组中插入一个新的零值元素。过量的元素会明显增加程序的时间和空间开销。
有这些小例子作为背景，我们将继续看两个大一点的程序。好在我们不需要研究太大的程序。
有穷状态机（FSM）是计算的一种优雅的数学模型和有用的实践工具，它在程序设计语言的词法分析、通信协议以及简单硬件设备等许多应用领域都有广泛的用途。Wulf、Shaw、Hilfinger和Flon在他们合著的Fundamental Structures of Computer Science[3]一书（Addison-Wesley出版社1981年出版）的1.1节讨论了这一主题。
作为例子，他们考虑这样一个简单的任务——“抑制”比特流中所有新出现的1：
Input: 011010111
Output: 001000011紧跟在0后面的1被改成0，输入流中的所有其他比特位不变。
下面的两状态自动机在其状态中对最后一个输入比特进行编码：“LIZ”表示“Last Input Zero”，而“LIO”表示“Last Input One”。
指向LIZ的横向箭头表明这是初始状态。从LIZ到LIO的弧线的意思是，如果自动机当前处于状态LIZ且输入是一个1，则输出一个0并进入状态LIO。
执行FSM的程序使用两个主要数据结构。如果FSM包含弧线
那么下面的等式成立：
trans[State1, InSym] == State2
out[State1, InSym] == OutSym名字trans表示状态转换，out表示输出符号。
上面描述的自动机和输入编码如下：
LIZ 0 LIZ 0
LIZ 1 LIO 0
LIO 0 LIZ 0
LIO 1 LIO 1
start LIZ
0
1
1
0
...前4行表示FSM中的4条边。第一行说，如果自动机当前状态为LIZ且输入为0，那么下一个状态是LIZ并输出0。第五行确定初始状态，之后的行是输入数据。
下面的程序按上面描述的形式执行FSM。
run == 1 { print out[s, $1]; s = trans[s, $1] }
run == 0 { if ($1 == "start") { run = 1; s = $2 }
else { trans[$1, $2] = $3; out[$1, $2] = $4 }
}该程序有两个主要的模式。起初，变量run值为零。在这个模式下，将自动机的转换添加到数组trans和out中。当输入的某一行的第一个字段是字符串"start"时，程序将相应的初始状态存放到s中，然后切换到运行模式。然后每步的执行都将产生输出并改变状态，每步转换后的状态可以看成是当前输入（$1）和当前状态（s）的函数。
这个微型的程序有很多缺点。例如，对于未定义的转换，它做出的反应将是灾难性的。事实上，这个程序顶多适合个人使用。另一方面，它为创建更健壮的程序提供了便利的基础，见习题2。
拓扑排序算法的输入是一个有向无环图，例如：
如果图中包含从A到B的边，那么A就是B的祖先而B是A的后代。算法必须对图中结点排序以使得所有祖先出现在它们的后代之前，下图是许多可能排序中的一种。
算法还必须能够处理输入图中包含回路因此无法完成排序的可能情况。
这样的算法可以应用于绘制物体的三维场景。如果物体B在视图中处于物体A的前面，那么A就在B之前，因为A必须在B之前完成绘制。下图左边由4个矩形构成的场景能够导出右边的偏序。
图2-5中有两种对顶点的有效排序，即A B C D 和A C B D。每种排序都恰当地给出了物体的覆盖图。拓扑排序的其他应用包括对技术文档进行布局（术语在使用之前必须先定义）以及处理层次化VLSI设计（算法在处理一个部件之前必须先处理其组成部分）。继续阅读之前，请花一分钟思考你将如何编写对有向图进行拓扑排序的程序。
我们将研究一个拓扑排序算法，该算法引自Knuth的《计算机程序设计艺术，卷1：基本算法》[4]一书的2.2.3节。该算法的循环步骤如下：选出一个没有祖先的结点T，将T写到输出文件中，然后从图中删除从T出发的所有边。下图显示了这个算法如何应用在之前的四结点场景图上。算法的各阶段从左向右进行，每一阶段选出的结点T都画了圈。
排序结果是A B C D。
这个算法的一种低效的实现在每一步都要扫描整个图以找到没有祖先的结点。现在来研究一个更简单也更高效的算法。对每个结点，新算法都存储它的祖先数量以及后代结点集合。比如，上面所画的四结点图表示如下：
| 结点 |
祖先数量 |
后代 |
|---|---|---|
| A |
0 |
B C |
算法的循环步骤每次选出一个祖先结点数为零的结点，把它写到输出文件中，其所有后代结点的祖先数量全部减少1。然而，算法必须仔细记住不同顶点其祖先计数变为零的先后顺序，这里使用了一个结点队列。（如果在所有结点的祖先计数变为零之前队列为空，那么程序报告图中存在回路。）
下面的伪代码假设输入给程序的图是由一系列（祖先，后代）对表示的，每行一对。
as each (pred, succ) pair is read
increment pred count of succ
append succ to successors of pred
at the end of the input file
initialize queue to empty
for each node i
if pred count of i is zero then append i to queue
while queue isn't empty do
delete t from front of queue; print t
for each successor s of t
decrement pred count of s
if that goes to zero then append x to queue
if some nodes were not output then report a cycle算法的运行时间与图中的边数成比例，只比最理想的情况多出一个常数因子。（每条边处理两次：一次是读，一次是从队列中将其删除。）
Awk程序使用一个索引范围是1..n的数组来实现队列。整型变量qlo是队列首元素的索引，qhi是尾元素的索引。后代集合由两个数组实现。如果A有后代B、C、D，那么下面的关系成立：
succct["A"] == 3
succlist["A", "1"] == "B"
succlist["A", "2"] == "C"
succlist["A", "3"] == "D"这个Awk程序的输入是一个祖先-后代对文件，其输出是排序好的结点列表或关于这样的列表不存在的警告。
{ ++predct[$2] # record nodes in predct,
predct[$1] = predct[$1] # even those with no preds
succlist[$1, ++succcnt[$1]] = $2
}
END { qlo = 1
for (i in predct) {
n++; if (predct[i] == 0) q[++qhi] = i
}
while (qlo <= qhi) {
t = q[qlo++]; print t
for (i = 1; i <= succcnt[t]; i++) {
s = succlist[t, i]
if (--predct[s] == 0) q[++qhi] = s
}
}
if (qhi != n) print "tsort error: cycle in input"
}
程序第二行保证所有结点都作为predct的索引出现，即便没有祖先的结点也一样。
本程序的关联数组表示了几种不同的抽象数据类型：一个结点名字的符号表、一个记录数组、一个二维的后代集合序列以及一个结点队列。本程序小巧、便于理解，但在较大的程序中无法清楚分辨不同的抽象数据类型就会降低程序可读性。
Awk可以使程序员事半功倍。我们目前看到的多数程序如果使用传统的语言编写，代码量恐怕会多出一个数量级。规模的减小归功于Awk的几个特性：输入行之上的隐式循环、自动分隔成字段、变量的初始化和转换，以及关联数组。
关联数组是Awk将字符串和数值这样的基本数据类型结合起来的唯一机制，别无他法。幸而关联数组可以很自然地表示许多数据结构。
除了教学，Awk及其关联数组还有什么实际价值吗？Awk程序很小，这并不总是优点（像APL单行程序一样，Awk程序会使人费解，令人不胜其烦），但10行代码几乎总是要胜过100行代码。不幸的是，Awk代码运行起来似乎很慢。符号表的效率相对比较高，但以整数为索引的数组却要比传统实现慢上几个数量级。在什么情况下小而慢的程序才有用呢？
1．选择本章的一个Awk程序，然后用另外一种语言重新编写。两个程序在源代码规模和运行时效率上相比如何？
2．用各种方式加强FSM模拟器。考虑加入错误（坏状态、坏输入等）检查、默认转换以及字符类（例如整数和字母）。编写程序对一个简单的程序设计语言进行词法分析。
3．本章的拓扑排序程序在输入图有回路的情况下给出报告。修改这个程序以打印回路，让它在出现错误时更健壮一些。
4．说明由三维场景导出的图可能包含回路。给出可以保证无回路的限制条件。
5．为下面的任务设计程序。怎样使用关联数组来简化这些程序？
a．树。编写程序创建并遍历二叉树。
b．图。用深度优先搜索重写拓扑排序程序。给定一个有向图和一个结点x，返回所有从x可以到达的结点。给定一个带权图和两个结点x、y，返回从x到y的最短路径。
c．文档。使用一个简单的字典把一种自然语言翻译成另外一种自然语言（英-法字典中的一行可能包含两个单词“hello bonjour”）。为课本或程序文件准备交叉引用表，每个单词的所有引用都要用行号列出。Awk程序员可以试着使用输入字段分隔符和替换命令来完成对单词的更现实的定义。
d．随机句子生成。本程序的输入是一个如下的上下文无关文法：
S → NP VP
NP → AL N | N
N → John | Mary
AL→ A | A AL
A → Big | Little | Tiny
VP → V AvL
V → runs | walks
AvL → Av | AvL Av
Av → quickly | slowly
程序应当生成随机的句子，如“John walks quickly”或“Big Little Mary runs slowly quickly slowly”。
e．过滤器。第二个“名字”程序从文件里过滤出重复的单词，而拼写检查程序则过滤出字典中的单词。编写其他的单词过滤器，比如删除不在“批准列表”中的单词，按原来的顺序留下批准的单词。（当输入排好序时这些任务更容易。）
f．棋盘游戏。实现Conway的“生存游戏”。你可能会用到Awk的delete x[i]语句来删除旧的棋盘位置。
6．描述关联数组的多种实现，并分析每个元素的访问时间和存储成本。
Aho、Kernighan和Weinberger在1977年设计并创建了最初的Awk语言。（无论如何，都不要重新排列他们姓氏的首字母！[5]）在Addison-Wesley出版社1988年出版的AWK Programming Language一书中，他们详细讲述了该语言及其高明的用法。该书第7章说明Awk如何成为实验算法的一个有用工具，我们将在本书的第3章、第13章和第14章以这样的目的来使用Awk；该书第6章把Awk作为一个小语言处理器来讲述，我们将在本书第9章这样使用Awk。该书其他章节提供了一个参考指南并将Awk应用于数据处理、数据库和文字处理中。这本Awk的书是对一门有趣而实用的语言的出色导论。
[1] 由美国语言学家Benjamin Whorf（1897—1941）提出，也称Sapir-Whorf假说，认为语言本身会影响人的概念形成，从而影响人的思维模式和世界观，进而影响社会文化。——编者注
[2] Snobol中区分数组和表：数组用数值作下标，而表用字符串作下标。Awk只有一种数组，数值下标在存储之前先转换成字符串。下标可能有多重索引——Awk把多重索引连接成一个单键，索引之间用一个特殊字符分隔。
[3] 该书中译版曾于1987年由科学出版社出版，中文书名《计算机科学的基本结构》。——编者注
[4] 该书第3版英文影印版已由人民邮电出版社于2010年出版，中译版也由人民邮电出版社出版。——编者注
[5] Awk语言的名称来源于三个开发者姓氏的首字母，若按字母顺序排列，就应当是Akw，但是Awk更像一个英文单词，而且还有“难用的”（Awkward）诙谐意味在里面。——译者注
