贵州公务员考试阶段违规违纪制度

免费在线版本 （非印刷免费在线版） 登录China-Pub网站购买此书完整版 了解本书更多信息请登录本书的官方网站 InfoQ 中文站出品 本书由 InfoQ 中文站免费发放，如果您从其他渠道获取本书，请注册 InfoQ 中文站以支持作者 和出版商，并免费下载更多 InfoQ 企业软件开发系列图书。 本书主页为 http://infoq.com/cn/minibooks/beautiful-code © 2008 C4Media Inc. 版权所有 C4Media 是 InfoQ.com 这一企业软件开发社区的出版商 本书属于 InfoQ 企业软件开发丛书 如果您打算订购 InfoQ 的图书，请联系 books@c4media.com 未经出版者预先的书面许可，不得以任何方式复制或者抄袭本书的任何部分，本书任何部分不 得用于再印刷，存储于可重复使用的系统，或者以任何方式进行电子、 机械、复印和录制等形 式传播。 本书提到的公司产品或者使用到的商标为产品公司所有。 如果读者要了解具体的商标和注册信息，应该联系相应的公司。 本书在征得华章出版公司许可下制作，以电子文档形式发布。 欢迎共同参与 InfoQ 中文站的建设工作，包括原创投稿和翻译等，请联系 editors@cn.infoq.com。 序 Greg Wilson 我在1982年夏天获得了第一份程序员工作。在我工作了两个星期后，一位系统管理员借给 了我两本书：Kernighan和Plauger编写的《The Elements of Programming Style》(McGraw-Hill 出版社)和Wirth编写的《Algorithms + Data Structures = Programs》 (Prentice Hall出版 社)。这两本书让我大开眼界——我第一次发现程序并不仅仅只是一组计算机执行的指令。它们 可以像做工优良的橱柜一样精致，像悬索吊桥一样漂亮，或者像George Orwell的散文一样优美。 自从那个夏天以来，我经常听到人们感叹我们的教育并没有教会学生看到这一点。建筑师 们需要观摩建筑物，作曲家们需要研习他人的作品，而程序员——他们只有在需要修改bug时才 会去阅读其他人的代码；即使在这个时候，他们也会尽可能减少阅读量。我们曾告诉学生使用 有意义的变量名，曾向他们介绍过一些基本的设计模式，但很奇怪，为什么他们编写的大多数 代码都是很难看的呢！ 本书将试图改变这种状况。2006年5月，我邀请了一些著名的（以及不太著名的）软件设计 师来分析和讨论他们所知道的漂亮代码。正如在本书中将要介绍的，他们在许多不同的地方发 现了代码的漂亮性。有些漂亮性存在于手工精心打造软件的细微之处，而有些漂亮性是蕴涵在 大局之中——那些使程序能够持续发展的架构，或者用来构造程序的技术。 无论他们是在什么地方发现的这些漂亮性，我都非常感谢我们的投稿人抽出时间为我们奉 献了这样的一次学习旅程。我希望你能够享受阅读此书的乐趣，就像Andy和我非常享受编辑这 本书的过程，此外，我还希望这本书能激发你创建出一些漂亮的作品。 i 前言 《Beautiful Code》是由Greg Wilson在 2006 年构思的，本书的初衷是希望从优秀的软件 开发人员和计算机科学家中提炼出一些有价值的思想。他与助理编辑Andy Oram一起走访了世界 各地不同技术背景的专家。本《代码之美》精选版是从原书中精选出其中的 6 章。 本书章节内容的组织 第 1 章，正则表达式匹配器，作者 Brian Kernighan，介绍了对一种语言和一个问题的深入分 析以及由此产生的简洁而优雅的解决。 第 2 章，我编写过的最漂亮代码，作者 Jon Bentley，介绍了如何在无需执行函数的情况下测 试函数的性能。 第 3 章，美丽的测试，作者 Alberto Savoia，介绍了一种全新的测试方法，不仅能够消除 bug， 还可以使你成为一个更优秀的程序员。 第 4 章，NASA 火星漫步者任务中的高可靠企业系统，作者 Ronald Mak，介绍了如何使用工业标 准，最佳实践和 Java 技术来满足 NASA 探险任务的高可靠性需求。 第 5 章，美丽的并发，作者 Simon Peyton Jones，通过软件事务内存（Software Transactional Memory）来消除大多数并发程序中的困难，在本章中使用 Haskell 语言来说明。 第 6 章，以 REST 方式集成业务伙伴，作者 Andrew Patzer，通过根据需求来设计一个 B2B Web Service 从而表现出设计者对程序开发人员的尊重。 ii 目录 序 .............................................................................................................................................................i 前言 ....................................................................................................................................................... ii 第 1 章 正则表达式匹配器...................................................................................................................1 1.1 编程实践..........................................................................................................................................2 1.2 实现..................................................................................................................................................3 1.3 讨论..................................................................................................................................................4 1.4 其他的方法......................................................................................................................................5 1.5 构建..................................................................................................................................................6 1.6 小结..................................................................................................................................................8 第 2 章 我编写过的最漂亮代码.........................................................................................................10 2.1 我编写过的最漂亮代码................................................................................................................10 2.2 事倍功半........................................................................................................................................11 2.3 观点................................................................................................................................................16 2.4 本章的中心思想是什么？............................................................................................................18 2.5 结论................................................................................................................................................18 2.6 致谢................................................................................................................................................20 第 3 章 美丽测试.................................................................................................................................21 3.1 讨厌的二分查找............................................................................................................................22 3.2 JUnit 简介 ....................................................................................................................................27 3.3 将二分查找进行到底....................................................................................................................29 3.4 结论................................................................................................................................................47 第 4 章 NASA 火星漫步者任务中的高可靠企业系统 .....................................................................49 4.1 任务与 CIP ....................................................................................................................................49 4.2 任务需求........................................................................................................................................50 4.3 系统架构........................................................................................................................................51 4.4 案例分析：流服务........................................................................................................................54 4.5 可靠性............................................................................................................................................57 iii 4.6 稳定性............................................................................................................................................66 4.7 结束语............................................................................................................................................67 第 5 章 美丽的并发.............................................................................................................................68 5.1 一个简单的例子............................................................................................................................68 5.2 软件事务内存................................................................................................................................71 5.3 圣诞老人问题................................................................................................................................80 5.4 对 Haskell 的一些思考 .................................................................................................................90 5.5 结论................................................................................................................................................91 5.6 致谢................................................................................................................................................92 第 6 章 以 REST 方式集成业务伙伴 .................................................................................................93 6.1 项目背景........................................................................................................................................93 6.2 把服务开放给外部客户................................................................................................................93 6.3 使用工厂模式转发服务................................................................................................................97 6.4 用电子商务来交换数据........................................................................................................98 6.5 结束语..........................................................................................................................................104 后记 ....................................................................................................................................................106 iv 第 1 章 正则表达式匹配器 Brian Kernighan 正则表达式是描述文本模式的表示法，它可以有效地构造一种用于模式匹配的专用语言。 虽然正则表达式可以有多种不同的形式，但它们都有着共同的特点：模式中的大多数字符都是 匹配字符串中的字符本身，但有些元字符（metacharacter）却有着特定的含义，例如*表示某 种重复，而[...]表示方括号中字符集合的任何一个字符。 实际上，在文本编辑器之类的程序中，所执行的查找操作都是查找文字，因此正则表达式 通常是像“print”之类的字符串，而这类字符串将与文档中所有的“printf”或者“sprintf” 或者“printer paper”相匹配。在Unix和Windows中可以使用所谓的通配符来指定文件名，其 中字符*可以用来匹配任意数量的字符，因此匹配模式*.c就将匹配所有以.c结尾的文件。此外， 还有许许多多不同形式的正则表达式，甚至在有些情况下，这些正则表达式会被认为都是相同 的。Jeffrey Friedl编著的《Mastering Regular Expressions》一书对这一方面问题进行了广 泛的研究。 Stephen Kleene在20世纪50年代的中期发明了正则表达式，用来作为有限自动机的表示法， 事实上，正则表达式与其所表示的有限自动机是等价的。20世纪60年代年代中期，正则表达式 最初出现在Ken Thompson版本的QED文本编辑器的程序设置中。1967年Thompson申请了一项基于 正则表达式的快速文本匹配机制的专利。这项专利在1971年获得了批准，它是最早的软件专利 之一[U.S. Patent 3,568,156, Text Matching Algorithm, March 2, 1971]. 后来，正则表达式技术从QED移植到了Unix的编辑器ed中，然后又被移植到经典的Unix工具 grep中，而grpe正是由于Thompson对ed进行了彻底地修改而形成的。这些广为应用的程序使得 正则表达式为早期的Unix社群所熟知。 Thompson最初编写的匹配器是非常快的，因为它结合了两种独立的思想。一种思想是在匹 配过程中动态地生成机器指令，这样就可以以机器指令执行的速度而不是解释执行的速度来运 行。另一种思想是在每个阶段中都尽可能地执行匹配操作，这样无需回朔（backtrack）就可以 查找可能的匹配。在Thompson后来编写的文本编辑器程序中，例如ed，匹配代码使用了一种更 为简单的算法，这种算法将会在必要的时候进行回朔。从理论上来看，这种方法的运行速度要 更慢，但在实际情况中，这种模式很少需要进行回朔，因此，ed和grep中的算法和代码足以应 付大多数的情况。 在后来的正则表达式匹配器中，例如egrep和fgrep等，都增加了更为丰富的正则表达式类 1 型，并且重点是要使得匹配器无论在什么模式下都能够快速执行。功能更为强大的正则表达式 正在被越来越多地使用，它们不仅被包含在用C语言开发的库中，而且还被作为脚本语言如Awk 和Perl的语法的一部分。 1.1 编程实践 在1998年，Rob Pike和我还在编写《The Practice of Programming》（Addison-Wesley） 一书。书中的最后一章是“记法”，在这一章中收录了许多示例代码，这些示例都很好地说明 了良好的记法将会带来更好的程序以及更好的设计。其中包括使用简单的数据规范（例如 printf）以及从表中生成代码。 由于我们有着深厚的Unix技术背景以及在使用基于正则表达式记法的工具上有着近30年的 经验，我们很自然地希望在本书中包含一个对正则表达式的讨论，当然包含一个实现也是必须 的。由于我们强调了工具软件的使用，因此似乎最好应该把重点放在grep中的正则表达式类型 上——而不是，比方说，在shell的通配符正则表达式上——这样我们还可以在随后再讨论grep 本身的设计。 然而，问题是现有的正则表达式软件包都太庞大了。grep中的代码长度超过500行（大约10 页书的长度），并且在代码的周围还有复杂的上下文环境。开源的正则表达式软件包则更为庞 大——代码的长度几乎布满整本书——因为这些代码需要考虑通用性，灵活性以及运行速度； 因此，所有这些正则表达式都不适合用来教学。 我向Rob建议我们需要一个最小的正则表达式软件包，它可以很好地诠释正则表达式的基本 思想，并且能够识别出一组有用的并且重要类的模式。理想的情况是，所需代码长度只有一页 就够了。 Rob听了我的提议后就离开了他的办公室。我现在还记得，一，两个小时后他回来了，并且给了 我一段大约30行的C代码，在《The Practice of Programming》一书的第9章中包含了这段代码。 在这段代码实现了一个正则表达式匹配器，用来处理以下的模型。 字符 含义 c 匹配任意的字母c .（句点） 匹配任意的单个字符 ^ 匹配输入字符串的开头 $ 匹配输入字符串的结尾 * 匹配前一个字符的零个或者多个出现 这是一个非常有用的匹配器，根据我在日常工作中使用正则表达式的经验，它可以轻松解 决95％的问题。在许多情况下，解决正确的问题就等于朝着创建漂亮的程序迈进了一大步。Rob 2 值得好好地表扬，因为他从大量可选功能集中选出了一组非常小但却重要的，并且是明确的以 及可扩展的功能。 Rob的实现本身就是漂亮代码的一个极佳示例：紧凑，优雅，高效并且实用。这是我所见过 的最好的递归示例之一，在这段代码中还展示了C指针的强大功能。虽然当时我们最关心的是通 过使程序更易于使用（同时也更易于编写）来体现良好记法的重要性，但正则表达式代码同样 也是阐述算法，数据结构，测试，性能增强以及其他重要主题的最好方式。 1.2 实现 在《The Practice of Programming》一书中，正则表达式匹配器是一个模拟grep程序中的 一部分，但正则表达式的代码完全可以从编写环境中独立出来。这里我们并不关心主程序；像 许多Unix工具一样，这个程序将读取其输入或者一组文件，然后输出包含与正则表达式匹 配的文本行。 以下是匹配算法的代码： /* match: search for regexp anywhere in text */ int match(char *regexp, char *text) { if (regexp[0] == '^') return matchhere(regexp+1, text); do { /* must look even if string is empty */ if (matchhere(regexp, text)) return 1; } while (*text++ != '\0'); return 0; } /* matchhere: search for regexp at beginning of text */ int matchhere(char *regexp, char *text) { if (regexp[0] == '\0') return 1; if (regexp[1] == '*') return matchstar(regexp[0], regexp+2, text); if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text)) return matchhere(regexp+1, text+1); return 0; 3 } /* matchstar: search for c*regexp at beginning of text */ int matchstar(int c, char *regexp, char *text) { do { /* a * matches zero or more instances */ if (matchhere(regexp, text)) return 1; } while (*text != '\0' && (*text++ == c || c == '.')); return 0; } 1.3 讨论 函数match(regexp，text)用来判断文本中是否出现正则表达式；如果找到了一个匹配的正 则表达式则返回1，否则返回0。如果有多个匹配的正则表达式，那么函数将找到文本中最左边 的并且最短的那个。 match函数中的基本操作简单明了。如果正则表达式中的第一个字符是（^固定位置的匹配）， 那么匹配就一定要出现在字符串的开头。也就是说，如果正则表达式是^xyz，那么仅当xyz出现 在文本的开头而不是中间的某个位置时才会匹配成功。在代码中通过把正则表达式的剩余部分 与文本的起始位置而不是其他地方进行匹配来判断。如果第一个字符不是^，那么正则表达式就 可以在字符串中的任意位置上进行匹配。在代码中通过把模式依次与文本中的每个字符位置进 行匹配来判断。如果存在多个匹配，那么代码只会识别第一个（最左边的）匹配。也就是说， 如果则在表达式是xyz，那么将会匹配第一次出现的xyz，而且不考虑这个匹配出现在什么位置 上。 注意，对输入字符串的推进操作是在一个do-while循环中进行的，这种结构在C程序中使用 相对较少。在代码中使用do-while而不是while通常会带来疑问：为什么不在循环的起始处判断 循环条件，而是在循环末尾当执行完了某个操作之后才进行判断呢？不过，这里的判断是正确 的：由于*运算符允许零长度的匹配，因此我们首先需要判断是否存在一个空的匹配。 大部分的匹配工作是在matchhere(regexp，text)函数中完成的，这个函数将判断正则表达 式与文本的开头部分是否匹配。函数matchhere把正则表达式的第一个字符与文本的第一个字符 进行匹配。如果匹配失败，那么在这个文本位置上就不存在匹配，因此matchhere将返回0。然 而，如果匹配成功了，函数将推进到正则表达式的下一个字符和文本的下一个字符继续进行匹 配。这是通过递归地调用matchhere函数来实现的。 由于存在着一些特殊的情况，以及需要设置终止递归的条件。因此实际的处理过程要更为 4 复杂些最简单的情况就是，当正则表达式推进到末尾时(regexp[0] == '\0')，所有前面的判断 都成功了，那么这个正则表达式就与文本匹配。 如果正则表达式是一个字符后面跟着一个*，那么将会调用matchstar来判断闭包（closure） 是否匹配。函数matchstar(c, regexp, text)将尝试匹配重复的文本字符c，从零重复开始并且 不断累加，直到匹配text的剩余字符，如果匹配失败，那么函数就认为不存在匹配。这个算法 将识别出一个“最短的匹配”，这对简单的模式匹配来说是很好的，例如grep，这种情况下的 主要问题是尽可能快地找到一个匹配。而对于文本编辑器来说，“最长的匹配”则是更为直观， 且肯定是更好的，因为通常需要对匹配的文本进行替换。在目前许多的正则表达式库中同时提 供了这两种方法，在《The Practice of Programming》一书中给出了基于本例中matchstar函 数的一种简单变形，我们在后面将给出这种形式。 如果在正则表达式的末尾包含了一个$，那么仅当text此时位于末尾时才会匹配成功： if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; 如果没有包含$，并且如果当前不是处于text字符串的末尾（也就是说，*text!='\0'）并 且如果text字符串的第一个字符匹配正则表达式的第一个字符，那么到现在为止都是没有问题 的；我们将接着判断正则表达式的下一个字符是否匹配text的下一个字符，这是通过递归调用 matchhere函数来实现的。这个递归调用不仅是本算法的核心，也是这段代码如此紧凑和整洁的 原因。 如果所有这些匹配尝试都失败了，那么正则表达式和text在这个位置上就不存在匹配，因 此函数matchhere将返回0。 在这段代码中大量地使用了C指针。在递归的每个阶段，如果存在某个字符匹配，那么在随 后的递归调用中将执行指针算法（例如，regexp+1 and text+1），这样在随后的函数调用中， 参数就是正则表达式的下一个字符和text的下一个字符。递归的深度不会超过匹配模式的长度， 而通常情况下匹配模式的长度都是很短的，因此不会出现耗尽内存空间的危险。 1.4 其他的方法 这是一段非常优雅并且写得很好的代码，但并不是完美的。我们还可以做哪些其他的工作？ 我可能对matchhere中的操作进行重新安排，在处理*之前首先处理$。虽然这种安排不会对函数 的执行带来影响，但却使得函数看上去要自然一些，而在编程中一个良好的规则就是：在处理 复杂的情况之前首先处理容易的情况。 不过，通常这些判断的顺序是非常重要的。例如，在matchstar的这个判断中： } while (*text != '\0' && (*text++ == c || c == '.')); 5 无论在什么情况下，我们都必须推进text字符串中的一个或多个字符，因此在text++中的 递增运算一定要执行。 该代码对终止条件进行了谨慎的处理。通常，匹配过程的成功与否，是通过判断正则表达 式和text中的字符是不是同时处理完来决定的。如果是同时处理完了，那么就表示匹配成功， 如果其中一方在另一方之前被处理完了，那么就表示匹配失败。在下面这行代码中很明显地说 明了这个判断。 if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; 但在其他的情况下，还有一些微妙的终止条件。 如果在matchstar函数中需要识别最左边的以及最长的匹配，那么函数将首先识别输入字符 c的最大重复序列。然后函数将调用matchhere来尝试把匹配延伸到正则表达式的剩余部分和 text的剩余部分。每次匹配失败都会将cs的出现次数减1，然后再次开始尝试，包括处理零出现 的情况： /* matchstar: leftmost longest search for c*regexp */ int matchstar(int c, char *regexp, char *text) { char *t; for (t = text; *t != '\0' && (*t == c || c == '.'); t++) ; do { /* * matches zero or more */ if (matchhere(regexp, t)) return 1; } while (t-- > text); return 0; } 我们来看一下正则表达式(.*)，它将匹配括号内任意长度的text。假设给定了text： for (t = text; *t != '\0' && (*t == c || c == '.'); t++) 从开头位置起的最长匹配将会识别整个括号内的表达式，而最短的匹配将会停止在第一次 出现右括号的地方。（当然，从第二个左括号开始的最长匹配将会延伸到text的末尾） 1.5 构建 《The Practice of Programming》一书主要讲授良好的程序设计。在编写该书时，Rob和 我还在贝尔实验室工作，因此我们知道在课堂上使用这本书有什么样的效果。令人高兴的是， 6 我们发现这本书中的某些内容在课堂上确实有着不错的效果。从2000年教授程序设计中的重点 要素时，我们就使用了这段代码。 首先，这段代码以一种全新的形式展示了递归的强大功能及其带来的整洁代码。它既不是 另一种版本的快速排序（或者阶乘！）算法，也不是某种树的遍历算法。 这段代码同时还是性能试验的一个很好示例。其性能与系统中的grep并没有太大的差异， 这表明递归技术的开销并不是非常大的，因此没有必要对这段代码进行调整。 此外，这段代码还充分说明了优良算法的重要性。如果在模式中包含了几个.*序列，那么 在简单的实现中将需要进行大量的回溯操作，并且在某些情况下将会运行得极慢。 在标准的Unix grep中有着同样的回朔操作。例如，下面这个命令： grep 'a.*a.*a.*a.a' 在普通的机器上处理一个4 MB的文本文件要花费20秒的时间。 如果某个实现是基于把非确定有限自动机转换为确定有限自动机，例如egrep，那么在处理 恶劣的情况时将会获得比较好的性能；它可以在不到十分之一秒的时间内处理同样的模式和同 样的输入，并且运行时间通常是独立于模式的。 对于正则表达式类型的扩展将形成各种任务的基础。例如： 1．增加其他的元字符，例如+用于表示前面字符的一个或多个出现，或者?用于表示零个或 一个字符的匹配。还可以增加一些方式来引用元字符，例如\$表示在模式中的$字符。 2．将正则表达式处理过程分成编译阶段和执行阶段。编译阶段把正则表达式转换为内部形 式，使匹配代码更为简单或者使随后的匹配过程运行得更为迅速。对于最初设计中的简单的正 则表达式来说，这种拆分并不是必须的，但在像grep这样的程序中，这种拆分是有意义的，因 为这种类型的正则表达式要更为丰富，并且同样的正则表达式将会用于匹配大量的输入行。 3．增加像[abc]和[0-9]这样的类型，这在传统的grep中分别匹配a或b或c和一个数字。可 以通过几种方式来实现，最自然的方式似乎就是把最初代码中的char*变量用一个结构来代替： typedef struct RE { int type; /* CHAR, STAR, etc. */ int ch; /* the character itself */ char *ccl; /* for [...] instead */ int nccl; /* true if class is negated [^...] */ } RE; 并且修改相应的代码来处理一个结构数组而不是处理一个字符数组。在这种情况下，并不 一定要把编译阶段从执行阶段中拆分出来，但这里的拆分过程是非常简单的。如果学生们把匹 7 配代码预编译成这个结构，那么总会比那些试图动态地解释一些复杂模式数据结构的学生要做 得更好。 为字符类型编写清晰并且无歧义的规范是件有难度的工作，而要用代码完美地实现处理更 是难上加难，这需要大量的冗长并且晦涩的编码。随着时间的推移，我简化了这个任务，而现 在大多数人会要求像Perl那样的速记，例如\d表示数字，\D表示非数字，而不再像最初那样在 方括号内指定字符的范围。 4．使用不透明的类型来隐藏RE结构以及所有的实现细节。这是在C语言中展示面向对象编 程技术的好方法，不过除此之外无法支持更多的东西。在实际情况中，将会创建一个正则表达 式类，其中类中成员函数的名字像RE_new( )和RE_match( )这样，而不是使用面向对象语言 的语法。 5．把正则表达式修改为像各种shell中的通配符那样：匹配模式的两端都被隐含地固定了， *匹配任意数量的字符，而?则匹配任意的单个字符。你可以修改这个算法或者把输入映射到现 有的算法中。 6．将这段代码转换成Java。最初的代码很好地使用了C指针，并且把这个算法在不同的语 言中实现出来是一个很好的实践过程。在Java版本的代码中将使用String.charA（使用索引而 不是指针）或者String.substring（更接近于指针）。这两种方法都没有C代码整洁，并且都不 紧凑。虽然在这个练习中性能并不是主要的问题，但有趣的是可以发现了Java版本比C版本在运 行速度上要慢6到7倍。 7．编写一个包装类把这种类型的正则表达式转换成Java的Patter类和Matcher类，这些类 将以一种与众不同的方式来拆分编译阶段和匹配阶段。这是适配器（Adapter）模式或者外观 （Façade）模式的很好示例，这两种模式用来在现有的类或者函数集合外部设置不同的接口。 我曾经大量地使用了这段代码来研究测试技术。正则表达式非常的丰富，而测试也不 是无足轻重的，但正则表达式又是很短小的，程序员可以很快地写出一组测试代码来执行。对 于前面所列出的各种扩展，我要求学生用一种紧凑的语言写出大量的测试代码（这是“记法” 的另一种示例），并且在他们自己的代码中使用这些测试代码；自然我在其他学生的代码中也 使用了他们的测试代码。 1.6 小结 当Rob Pike最初写出这段代码时，我被它的紧凑性和优雅性感到惊讶——这段代码比我以 前所想像的要更为短小并且功能也更为强大。通过事后分析，我们可以看到为什么这段代码如 此短小的众多原因。 首先，我们很好地选择了功能集合，这些功能是最为有用的并且最能从实现中体现出核心 8 思想，而没有多余的东西。例如，虽然固定模式^和$的实现只需要写3～4行代码，但在统一处 理普通情况之前，它展示了如何优雅地处理特殊情况。闭包操作*必须出现，因为它是正则表达 式中的基本记号，并且是提供处理不确定长度的惟一方式。增加+和?并不会有助于理解，因此 这些符号被留作为练习。 其次，我们成功地使用了递归。递归这种基本的编程技巧通常会比明确的循环带来更短、 更整洁的以及更优雅的代码，这也正是这里的示例。从正则表达式的开头和tex的开头剥离匹配 字符，然后对剩余的字符进行递归的思想，模仿了传统的阶乘或者字符串长度示例的递归结构， 但这里是用在了一种更为有趣和更有用的环境中。 第三，这段代码的确使用了基础语言来达到良好的效果。指针也可能被误用，但这里它们 被用来创建紧凑的表达式，并且在这个表达式中自然地表达了提取单个字符和推进到下一个字 符的过程。数组索引或者子字符串可以达到同样的效果，但在这段代码中，指针能够更好的实 现所需的功能，尤其是当指针与C语言中的自动递增运算和到布尔值的隐式转换结合在一起使用 时。 我不清楚是否有其他的方法能够在如此少的代码中实现如此多功能，并且同时还要提供丰 富的内涵和深层次的思想。 9 第 2 章 我编写过的最漂亮的代码 Jon Bentley 我曾经听一位大师级的程序员这样称赞到，“我通过删除代码来实现功能的提升。”而 法国著名作家兼飞行家 Antoine de Saint-Exupéry 的说法则更具代表性，“只有在不仅没 有任何功能可以添加，而且也没有任何功能可以删除的情况下，设计师才能够认为自己的工 作已臻完美。” 某些时候，在软件中根本就不存在最漂亮的代码，最漂亮的函数，或者最 漂亮的程序。 当然，我们很难对不存在的事物进行讨论。本章将对经典 Quicksort（快速排序）算法 的运行时间进行全面的分析，并试图通过这个分析来说明上述观点。在第一节中，我将首先 根据我自己的观点来回顾一下 Quicksort，并为后面的内容打下基础。第二节的内容将是本 章的重点部分。我们将首先在程序中增加一个计数器，然后通过不断地修改，从而使程序的 代码变得越来越短，但程序的功能却会变得越来越强，最终的结果是只需要几行代码就可以 使算法的运行时间达到平均水平。在第三节将对前面的技术进行小结，并对二分搜索树的运 行开销进行简单的分析。最后的两节将给出学完本章得到的一些启示，这将有助于你在今后 写出更为优雅的程序。 2.1 我编写过的最漂亮代码 当Greg Wilson最初告诉我本书的编写时，我曾自问编写过的最漂亮的代码是什么。 这个有趣的问题在我脑海里盘旋了大半天，然后我发现答案其实很简单：Quicksort 算法。 但遗憾的是，根据不同的表达方式，这个问题有着三种不同的答案。 当我撰写关于分治（divide-and-conquer）算法的论文时，我发现 C.A.R. Hoare 的 Quicksort 算法（“Quicksort”，Computer Journal 5）无疑是各种 Quicksort 算法的鼻 祖。这是一种解决基本问题的漂亮算法，可以用优雅的代码实现。我很喜欢这个算法，但我 总是无法弄明白算法中最内层的循环。我曾经花两天的时间来调试一个使用了这个循环的复 杂程序，并且几年以来，当我需要完成类似的任务时，我会很小心地复制这段代码。虽然这 段代码能够解决我所遇到的问题，但我却并没有真正地理解它。 我后来从 Nico Lomuto 那里学到了一种优雅的划分（partitioning）模式，并且最终编 写出了我能够理解，甚至能够证明的 Quicksort 算法。William Strunk Jr.针对英语所提出 的“良好的写作风格即为简练”这条经验同样适用于代码的编写，因此我遵循了他的建议， “省略不必要的字词”（来自《The Elements of Style》一书）。我最终将大约 40 行左右 的代码缩减为十几行的代码。因此，如果要回答“你曾编写过的最漂亮代码是什么？”这个 问题，那么我的答案就是：在我编写的《Programming Pearls, Second Edition》 (Addison-Wesley)一书中给出的 Quichsort 算法。在示例 2-1 中给出了用 C 语言编写的 Quicksort 函数。我们在接下来的章节中将进一步地研究和改善这个函数。 【示例】 2-1 Quicksort 函数 void quicksort(int l, int u) { int i, m; if (l >= u) return; 10 swap(l, randint(l, u)); m = l; for (i = l+1; i <= u; i++) if (x[i] < x[l]) swap(++m, i); swap(l, m); quicksort(l, m-1); quicksort(m+1, u); } 如果函数的调用形式是 quicksort(0, n-1)，那么这段代码将对一个全局数组 x[n]进行 排序。函数的两个参数分别是将要进行排序的子数组的下标：l 是较低的下标，而 u 是较高 的下标。函数调用 swap(i,j)将会交换 x[i]与 x[j]这两个元素。第一次交换操作将会按照 均匀分布的方式在 l 和 u 之