摘要

本书收录的是软件设计领域中的一组大师级作品。每一章都是由一位或几位著名程序员针对某个问题给出的完美的解决方案，并且细述了这些解决方案的巧妙之处。

代码之美 内容简介

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

代码之美 目录

前言

第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 进一步阅读

后记

代码之美 精彩文摘

第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有关，特别是对这个算法的性能分析。我将在下一节给出详细介绍。