书 · 1986 · 乔恩·本特利（Jon Bentley）

《编程珠玑》

一句话结论

好程序往往始于重新理解问题，再用合适的数据表示、算法和验证方法，把原本困难的工作变简单。

值得读完整本，尤其适合已经会写程序、希望提高解题能力的读者：它训练的是怎样找到好方案，而不只是怎样实现一个已知算法。

用户提出的任务名称往往太宽泛。先问清输入范围、重复情况、资源限制和输出要求，才能知道实际需要解决的是什么问题。

为什么：通用问题必须照顾许多可能情况，因此通用解法也承担了相应成本。明确约束后，一些原来必须处理的情况可能根本不会出现，问题就能改写成更简单的形式。省下来的工作来自对需求的理解，而不是把同一个程序写得更快。

数据结构不仅负责存东西，也决定程序需要做哪些工作。把规律放进恰当的数据表示里，可以消除大量比较、分支和重复描述。

为什么：程序复杂，有时是因为数据没有把问题的结构表达出来。将共同特征提取成统一表示后，原本逐一判断的关系可以通过排序、分组或查表处理。把变化的规则放进表格，也能让同一段处理逻辑反复使用。紧凑表示还可能减少存储需求，但要同时检查访问成本和适用条件。

不要只凭几个成功运行的例子相信程序正确。应明确程序开始时的条件、循环始终维持的事实，以及结束时必须得到的结果。

为什么：循环可能执行很多次，但每轮都应保持某个不变的关系。证明这个关系在开始时成立、执行一步后仍成立，再结合终止条件，就能解释程序为什么得到目标结果。这会迫使程序员处理区间端点、空输入和进度等容易含混的地方。推理仍须对应实际实现，不能遗漏机器整数和语言运算的限制。

遇到慢程序，先检查它是否反复计算了可以保留的结果。逐步比较朴素解法、复用中间结果的解法和更好的整体结构，比直接寻找神奇技巧更有用。

为什么：朴素算法通常容易理解，却可能对高度重叠的子问题反复求解。保存部分结果，或者把大问题拆成能够有效合并的小问题，就能减少重复计算。在顺序扫描中，如果少量状态足以概括此前的相关信息，就不必重新遍历过去的数据。由此减少的是运算次数随输入规模增长的速度，收益可能远大于局部指令优化。

性能改进有多个层次：问题定义、系统组织、算法、数据结构和具体代码。先估算量级，再测量实际成本，才知道哪个层次值得动手。

为什么：一个程序的耗时由不同部分共同构成，局部操作变快并不意味着整体明显变快。粗略估算能提前排除资源上不可行的方案，也能揭示结果是否偏离常识。测量则用来发现实际时间花在哪里，并检验优化是否有效。代码调优应放在这些判断之后，因为它通常增加实现复杂度，却未必触及主要成本。

排序、搜索、堆和压缩各有适用条件；好方案取决于用户需要哪些操作，以及时间、空间和结果质量之间怎样取舍。完整工具还需要通过实际使用逐步改进。

为什么：维护全体元素的完整顺序，与反复取出当前最小元素，需要维护的信息不同，因此不应自动采用同一种结构。批量处理与交互处理的需求不同，也会改变搜索和存储方案。原型能够先暴露哪些功能真正有用，再决定是否值得投入复杂实现。最后应比较整个工具的效用，而不是孤立地追求某个指标最好。

Bloch在2006年的文章中指出，本书讨论过正确性论证的二分查找，仍可能在计算中点时发生整数溢出；他自己的实现也犯过同类错误。具体问题是，数学意义上的整数推理没有完整覆盖机器整数的行为。他主张让证明、测试、审查和分析工具相互补充，而不是因此放弃证明。

Bendersky在2008年的书评中高度推荐本书，同时明确批评其部分代码风格，尤其不认可其中一些C++写法。这篇评论针对他所读的版本，不能直接当成对1986年首版全部代码的评价；它提醒读者，应把算法教学的价值与具体代码示范分开判断。

McIlroy在1986年的《A Review》中评价Knuth的词频程序：程序的表达和数据结构令人欣赏，但从工程角度看，可以用现成的Unix工具组合完成任务，避免重新实现已有功能的成本。他直接评论的是同名专栏中的程序，并非整本书；这一意见适合用来检验读者是否把学习算法误解成凡事都要从头实现。