全球38位顶尖高手、众多语言之父经典之作

第3章 我从未编写过的最漂亮的代码
Jon Bentley
我曾经听一位大师级的程序员这样称赞到，“我通过删除代码来实现功能的提升。”而法国著名作家兼飞行家Antoine de Saint-Exupéry的说法则更具代表性，“只有在不仅没有任何功能可以添加，而且也没有任何功能可以删除的情况下，设计师才能够认为自己的工作已臻完美。” 某些时候，在软件中根本就不存在最漂亮的代码，最漂亮的函数，或者最漂亮的程序。
当然，我们很难对不存在的事物进行讨论。本章将对经典Quicksort（快速排序）算法的运行时间进行全面的分析，并试图通过这个分析来说明上述观点。在第一节中，我将首先根据我自己的观点来回顾一下Quicksort，并为后面的内容打下基础。第二节的内容将是本章的重点部分。我们将首先在程序中增加一个计数器，然后通过不断地修改，从而使程序的代码变得越来越短，但程序的功能却会变得越来越强，最终的结果是只需要几行代码就可以使算法的运行时间达到平均水平。在第三节将对前面的技术进行小结，并对二分搜索树的运行开销进行简单的分析。最后的两节将给出学完本章得到的一些启示，这将有助于你在今后写出更为优雅的程序。
3.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算法。在示例3-1中给出了用C语言编写的Quicksort函数。我们在接下来的章节中将进一步地研究和改善这个函数。
【示例】 3-1 Quicksort函数
void quicksort（int l, int u）
{int i, m;
if （l 〉= u） return;
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之间随机地选择一个划分元素。
在《Programming Pearls》一书中包含了对Quicksort算法的详细推导以及正确性证明。在本章的剩余内容中，我将假设读者熟悉在《Programming Pearls》中所给出的Quicksort算法以及在大多数初级算法教科书中所给出的Quicksort算法。
如果你把问题改为“在你编写那些广为应用的代码中，哪一段代码是最漂亮的？”我的答案还是Quicksort算法。在我和M. D. McIlroy一起编写的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原来Unix qsort函数中的一个严重的性能问题。随后，我们开始用C语言编写一个新排序函数库，并且考虑了许多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比较了Quicksort的几种实现方案后，我们着手创建自己的Quicksort算法。在这篇文章中描述了我们如何设计出一个比这个算法的其他实现要更为清晰，速度更快以及更为健壮的新函数——部分原因是由于这个函数的代码更为短小。Gordon Bell的名言被证明是正确的：“在计算机系统中，那些最廉价，速度最快以及最为可靠的组件是不存在的。”现在，这个函数已经被使用了10多年的时间，并且没有出现任何故障。
考虑到通过缩减代码量所得到的好处，我最后以第三种方式来问自己在本章之初提出的问题。“你没有编写过的最漂亮代码是什么？”。我如何使用非常少的代码来实现大量的功能？答案还是和Quicksort有关，特别是对这个算法的性能分析。我将在下一节给出详细介绍。

译者序
序
前言
第1章 正则表达式匹配器
1.1 编程实践
1.2 实现
1.3 讨论
1.4 其他的方法
1.5 构建
1.6 小结

第2章 Subversion中的增量编辑器：像本体一样的接口
2.1 版本控制与目录树的转换
2.2 表达目录树的差异
2.3 增量编辑器接口
2.4 但这是不是艺术？
2.5 像体育比赛一样的抽象
2.6 结论

第3章 我编写过的最漂亮代码
3.1 我编写过的最漂亮代码
3.2事倍功半
3.3 观点
3.4 本章的中心思想是什么？
3.5 结论
3.6致谢

第4章 查找
4.1. 耗时
4.2. 问题：博客数据
4.3. 问题：时间，人物，以及对象？
4.4. 大规模尺度的搜索
4.5. 结论

第5章 正确、优美、迅速(按重要性排序)：从设计XML验证器中学到的经验
5.1 XML验证器的作用
5.2 问题所在
5.3 版本1：简单的实现
5.4 版本2：模拟BNF语法——复杂度O(N)
5.5 版本3：
第一个复杂度O(log N)的优化
5.6 版本4：
第二次优化：避免重复验证
5.7 版本5：
第三次优化：复杂度 O(1)
5.8 版本 6：
第四次优化：缓存(Caching)
5.9 从故事中学到的

第6章 集成测试框架：脆弱之美
6.1. 三个类搞定一个验收测试框架
6.2. 框架设计的挑战
6.3. 开放式框架
6.4. 一个HTML解析器可以简单到什么程度？
6.5. 结论

第7章 美丽测试
7.1 讨厌的二分查找
7.2 JUnit简介
7.3将二分查找进行到底
7.4 结论

第8章 图像处理中的即时代码生成

第9章 自顶向下的运算符优先级
9.1. JavaScript
9.2. 符号表
9.3. 语素
9.4. 优先级
9.5. 表达式
9.6. 中置运算符
9.7. 前置操作符
9.8. 赋值运算符
9.9. 常数
9.10. Scope
9.11. 语句
9.12. 函数
9.13. 数组和对象字面量
9.14. 要做和要思考的事

第 10章 追求加速的种群计数
10.1. 基本方法
10.2. 分治法
10.3. 其他方法
10.4. 两个字种群计数的和与差
10.5. 两个字的种群计数比较
10.6. 数组中的1位种群计数
10.7. 应用

第11章 安全通信：自由的技术
11.1 项目启动之前
11.2剖析安全通信的复杂性
11.3 可用性是关键要素
11.4 基础
11.5 测试集
11.6 功能原型
11.7 清理，插入，继续……
11.8 在喜马拉雅山的开发工作
11.9 看不到的改动
11.10 速度确实重要
11.11 人权中的通信隐私
11.12 程序员与文明

第12章 在BioPerl里培育漂亮代码
12.1. BioPerl和Bio::Graphics模块
12.2. Bio::Graphics的设计流程
12.3. 扩展Bio::Graphics
12.4. 结束语和教训

第13章 基因排序器的设计
13.1 基因排序器的用户界面
13.2 通过Web跟用户保持对话
13.3. 多态的威力
13.4 滤除无关的基因
13.5 大规模美丽代码理论
13.6 结论

第14章 优雅代码随硬件发展的演化
14.1. 计算机体系结构对矩阵算法的影响
14.2 一种基于分解的方法
14.3 一个简单版本
14.4 LINPACK库中的DGEFA子程序
14.5 LAPACK DGETRF
14.6递归LU
14.7 ScaLAPACK PDGETRF
14.8 针对多核系统的多线程设计
14.9 误差分析与操作计数浅析
14.10 未来的研究方向
14.11 进一步阅读

第15章 漂亮的设计会给你带来长远的好处
15.1. 对于漂亮代码的个人看法
15.2. 对于CERN库的介绍
15.3. 外在美（Outer Beauty）
15.4. 内在美（Inner Beauty ）
15.5. 结论

第16章，Linux内核驱动模型：协作的好处
16.1 简单的开始
16.2 进一步简化
16.3 扩展到上千台设备
16.4 小对象的松散结合

第17章 额外的间接层
17.1. 从直接代码操作到通过函数指针操作
17.2. 从函数参数到参数指针
17.3. 从文件系统到文件系统层
17.4. 从代码到DSL（Domain-Specific Language）
17.5. 复用与分离
17.6.分层是永恒之道?

第18章 Python的字典类：如何打造全能战士
18.1. 字典类的内部实现
18.2. 特殊调校
18.3. 冲突处理
18.4. 调整大小
18.5. 迭代和动态变化
18.6. 结论
18.7. 致谢

第19章 NumPy中的多维迭代器
19.1 N维数组操作中的关键挑战
19.2 N维数组的内存模型
19.3NumPy迭代器的起源
19.4 迭代器的设计
19.5 迭代器的接口
19.6 迭代器的使用
19.7 结束语

第20章 NASA火星漫步者任务中的高可靠企业系统
20.1 任务与CIP
20.2 任务需求
20.3 系统架构
20.4 案例分析：流服务
20.5 可靠性
20.6 稳定性
20.7 结束语

第21章 ERP5：最大可适性的设计
21.1 ERP的总体目标
21.2 ERP5
21.3 Zope基础平台
21.4 ERP5 Project中的概念
21.5 编码实现ERP5 Project
21.6 结束语

第22章 一匙污水

第23章 MapReduce分布式编程
23.1 激动人心的示例
23.2 MapReduce编程模型
23.3 其他MapReduce示例
23.4 分布式MapReduce的一种实现
23.5 模型扩展
23.6 结论
23.7 进阶阅读
23.8 致谢
23.9 附录：单词计数解决方案

第24章 美丽的并发
24.2 软件事务内存
24.3 圣诞老人问题
24.4 对Haskell的一些思考
24.6 致谢

第25章 句法抽象：syntax-case 展开器
25.1. syntax-case简介
25.2. 展开算法
25.3. 例子
25.4. 结论

第26章 节省劳动的架构：一个面向对象的网络化软件框架
26.1 示例程序：日志服务
26.2 日志服务器框架的面向对象设计
26.3 实现串行化日志服务器
26.4 实现并行日志服务器
26.5 结论

第27章 以REST方式集成业务伙伴
27.1 项目背景
27.2 把服务开放给外部客户
27.3 使用工厂模式转发服务
27.4 用电子商务协议来交换数据
27.5 结束语

第28章 漂亮的调试
28.1 对调试器进行调试
28.2 系统化的过程
28.3 关于查找的问题
28.4 自动找出故障起因
28.5 增量调试
28.6 最小化输入
28.7 查找缺陷
28.8 原型问题
28.9 结束语
28.10 致谢
28.11 进一步阅读

第29章 把代码当作文章

第30章 当你与世界的联系只有一个按钮
30.1 基本的设计模型
30.2 输入界面
30.3 用户界面的效率
30.4 下载
30.5 未来的发展方向

第31章 Emacspeak：全功能音频桌面
31.1 产生语音输出
31.2 支持语音的Emacs
31.3 对于在线信息的简单访问
31.4 小结
31.5 致谢

第32章 变动的代码
32.1 像书本一样
32.2 功能相似的代码在外观上也保持相似
32.3 缩进带来的危险
32.4 浏览代码
32.5 我们使用的工具
32.6 DiffMerge的曲折历史
32.7 结束语
32.8 致谢
32.9 进一步阅读

第33章 为“The Book”编写程序
33.1 没有捷径
33.2 给Lisp初学者的提示
33.3 三点共线
33.4 不可靠的斜率
33.5 三角不等性
33.6 河道弯曲模型
33.7 “Duh！”——我的意思是“Aha！”
33.8 结束语
33.9 进一步阅读
后记
作者简介

重新擦亮思考的火花
《代码之美》这本书已经成为经典。关于它本身的赞美之辞已经不少了，不过到底从这本书里该读些什么东西，我倒是有些思考。
上世纪九十年代初期，当时正在加州大学埃尔文分校攻读博士学位的Douglas Schmidt在观察了他所参与的软件项目开发实践之后，得出一

《代码之美》介绍了人类在一个奋斗领域中的创造性和灵活性：计算机系统的开发领域。在每章中的漂亮代码都是来自独特解决方案的发现，而这种发现是来源于作者超过既定边界的远见卓识，并且识别出被多数人忽视的需求以及找出令人叹为观止的问题解决方案。《代码之美》33章，有38位作者，每位作者贡献一章。每位作者都将自己心目中对于“美丽的代码”的认识浓缩在一章当中，张力十足。38位大牛，每个人对代码之美都有自己独特的认识，现在一览无余的放在一起，对于热爱程序的每个人都不啻一场盛宴。 虽然《代码之美》的涉猎范围很广，但也只能代表一小部分在这个软件开发这个令人兴奋领域所发生的事情。

http://img10.360buyimg.com/N0/23518/c77c48dc-6e3d-4cf2-870e-d7f0b8fffa14.jpg;http://img10.360buyimg.com/N0/29199/95047e00-1c24-462a-9502-07a812dae5b7.jpg

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和我非常享受编辑这本书的过程，此外，我还希望这本书能激发你创建出一些漂亮的作品。
在学术界，有一种叫“论文集”的东西，把许多人的论文合到一起出版，让读者能够在一本书的篇幅之内，了解某个特定领域的研究状况，是有效的知识传播手段之一。技术界比较少见到类似的出版物，的确是一种遗憾。
《代码之美（Beautiful Code）》就是这样一本书。三十三位大牛人的技术文章汇集到一起，讲述作者们认为“最漂亮的代码”，涉及应用领域虽广，而代码之美却一以贯之。如果我们 承认编程是门艺术——具有高度创造性和人类智慧参与的活动，不是艺术是什么？——那么，这几十篇文章就体现了这门艺术中最高的境界。
别担心！大牛们可不是坐而论道，也没有写什么常人不可索解的奥义，文章主题之朴实无华，比如“查找”，比如“分布式编程”，比如“Linux内核驱动模 型”……几乎要让人以为是不知道什么人编写的大学教材呢。这貌似普通的三个主题，作者分别是XML创始人之一Tim Bray、Google Map/Reduce架构发明人Jeff Dean和Linux内核维护者Greg Kroah-Hartman——吓死人的阵容。其余文章也都类似，小题目中见大手笔。
我深信这帮大牛接受约稿、写这种 “小”文章，实在是出于对编程的热爱，出于对“漂亮代码”的不懈追求。所谓“漂亮代码”，意思远超“规范、好看”，更多地体现出逻辑、思路与架构。一万块 最漂亮砖头堆出来的，不一定是大厦。建筑师在建造大厦之前，胸中早有蓝图在。《代码之美》，正展示了三十三位最优秀建筑师胸中的蓝图。
这本书能出中文版，是中国程序员的福音，其中的每篇文章，都值得读者细细咀嚼、回味。我已经迫不及待，想要看到正式印刷的版本了。
韩磊（CSDN副总经理）
向大师学习美
潘加宇
UMLChina首席执行官
我1989年参加高考时，总分120分的语文才考了71分，这最弱一环差点造成致命打击。最害怕的是写作文，记得当年的题目是写一封信，在右江盆地高温的教室里，我写得汗都滴在试卷上。没想到，后来看的东西多了，“不会作诗也会吟”，居然也能接杂志和出版社的约稿，写一些文章和序言之类。
翻开本书第29章，Ruby之父Yukihiro Matsumoto（松本行弘）说：Treating Code As an Essay。写代码如同写文章一般，多看多研究大师的作品，才能够信手拈来，写出美丽的代码。本书就是33位大师的倾情之作。
本书并不限定于讨论某一种语言的技巧，你能看到大师们使用现在流行的Java、Ruby，也能看到历史悠久的Fortran。讨论的领域从Linux内核，到NASA火星探测器、ERP系统，让我们从不同角度来体会代码之美。
美除了让人欣赏，还能带来金钱。因北京奥运的成功，博尔特的速度之美估计价值上千万美元。美丽的软件也一样。一些软件公司，公司人少且稳定，多年来专注于做某一个小领域里的软件，对软件的打磨可谓是精雕细琢，美丽软件带来的利润自然也很可观。比起那些靠低人力成本、低价格在市场上打拼的“程序员民工”公司，他们要活得滋润得多，安全得多。
享受代码之美
“希望写出漂亮代码的开发者可以向艺术家们学习一些东西。画家常常放下手中的画笔，然后远离画布一段距离，围着它转一转，翘起脑袋，斜着看看，再从不同的角度看看，在不同的光线下看看。在寻求美的过程中，他们需要设计这样一些视角并使它们融为一体。如果你的画布是个集成开发环境（IDE）而你的媒介就是代码，想一想，你如何做到离开画布一段距离，用挑剔的眼光从不同的视角来审视你的作品？──这将使你成为一个更优秀的程序员，并帮你写出美丽的代码。”
写这段话的Alberto Savoia在他的文章里真的没有讲什么令人敬畏的高技术或是大架构，他讲的是每个计算机系的大二学生都熟悉的二分查找。所以Savoia真的是在讲如何写出漂亮的代码，所以才选择了这么一个所有人都清楚得不能再清楚的例子。你会觉得这种事情都是些不谙世事的小程序员才会热衷于干的吧？可这位Savoia却是从Google离职以后开创了Agitar Software公司（http://www.agitar.com/）的不折不扣的创业者。有意思吗？一个胡须花白、在这个行业里厮混了数十年、拥有自己公司的老家伙，还在乐此不疲地谈论“漂亮的代码”。
这本《代码之美》就是由三十多篇像这样有意思的文章组成的。像Brian Kernighan、Tim Bray、Charles Petzold、Douglas Schmidt、Yukihiro Matsumoto这样的名字，你甚至很难想象他们同时出现在同一本书上。或许也只有“漂亮的代码”这样的话题才能激起他们共同的兴趣。于是就有了这本了不起的书：从正则表达式匹配器到图像处理，从通信到基因排序，这些可能是世界上最优秀的程序员毫不吝啬地向读者展示：不论面对什么问题、使用什么语言，代码的美感都是始终存在的，而且这种美感应该是程序员毕其一生不懈追寻的。
作为《重构》的译者，不时有人会问我一些关于重构的问题，其中一个问题让我最感为难：为什么要这样做？真的，如果不是要修改代码，也不是要添加功能，为什么要把这段代码抽取出来呢？让每个方法都保持5行以内的长度到底有什么好处呢？这种时候与其说是有什么利弊权衡，毋宁说就是为了让代码“更漂亮”。当然了，在大部分时间里，软件开发是一项集合了科学、工程和服务的工作，但──至少在我们的内心深处──它多少还有那么一点艺术的成分。除了完成任务以外让自己手上的代码更具美感，也算是对自己作为程序员的梦想的小小坚持吧。
所以，既然你已经拿起了这本书，就暂时放开那些功利的目标吧──别误会，这可不是一本没用的书，通过阅读这些“高手”们的编程心得，对自己的能力提升就算不能立竿见影至少也有潜移默化之功。但那也只是装珍珠的盒子而已。在一个安静的周末，给自己泡上一杯清茶，跟着三十三位顶尖高手畅游在代码世界，在他们的指引下遍赏代码之美，这才是作为一个程序员最大的享受呢。
熊节
ThoughtWorks咨询师
等度的流明
——代码之美·序
一
我上一次印象深刻的美的体验，大概已经是在十年之前了，那只是在午后睡醒，面对窗外的一棵大梧桐树时的感觉。不过这并不是说我这十年来都只看到了丑的事物，而是说我已经忘了去观察既已存在的美。
直到我拿到这本《代码之美》，我忽然地回到了那种仰望着星星烁耀的夜空，或低头沉思于一两句大家文字的日子里。那时刻我既不是在思考，也不是在分析，更不是在解释，而只是在感受自然的、文字的，或将自然蕴于文字之中的，美。
二
有一本书开启了一个时代，而我们如今仍然在这个时代之中而不知觉于这本书的深远影响，那是三位图灵奖得主合著的《结构程序设计》(1)。其中Dijkstra将人“理解一个程序的种种思维方法”归为三种：枚举、数学归纳和抽象。
显然Wirth先生更为深层地看到了程序的本质，他说“程序＝算法+数据结构”(2)。他揭示了这样一个事实：一个未知的、无序的世界是不可能实现“程序”的，于是我们抽象它——使它成为结构，或者对象，或者网，或者某个相对规则的事物。然后，我们再着之以“算法”。
《代码之美》这本书，三十八位大师，在三十三章的内容中详细讨论了代码中抽象的过程、算法的过程和编程的过程。显然的，这些正是程序中最深刻的美。如同花之蕊，叶之脉，以及维系花蕊叶脉的美的，那些汁液。这种对美的触及，使他在我面前闪耀着与前两本书等度的流明。
三
“只有在不仅没有任何功能可以添加，而且也没有任何功能可以删除的情况下，设计师才能够认为自己的工作已臻完美。”(3)然而编程的过程呢？我们最初只是想实现一个功能。但为了实现它，我们写了一段功能代码、一段测试代码、一段功能代码的配置代码，一段功能代码的配置代码的测试代码……
如此往复不休。
我们回到原始的问题，原本只是要做一个“实现某项功能”的代码，我们却为何把代码做到了“往复不休”的绝地？
或者你做的事情并不完美，但是你应该知道所谓完美的终极。代码要不停的测试，以及为测试代码再写测试代码，这一过程也不是美的。或许你认为它“必须”，但你应知道它终究不美。
四
大师们也并没有创生完美的能力，他们只是在一步步地进行着。在这本书里，Adam Kolawa告诉你的，Lincoln Stein告诉你的，以及Elliontte Rusty Harold等等告诉你的，就是那经年累月地或亦步亦趋地进行过程，和那个“终极完美”的定义。
这只是过程和隐于过程中对美的追求。而“美”是什么，还是在你的心底。你心中原本就没有美的感受，如何写得出美的代码？所以代码写到烂处，写到心胸滞涩处，便不如寻一清静所在，捧《代码之美》一册，回顾一下，品味一下，吐故纳新一下了。
看得多远，取决于你站得多高；要想成为他们，你得先知道他们。
这就是我的建议了。