多年以来，当让程序员推选喜爱的计算机图书时，《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺，计算机科学大师乔恩·本特利以其独有的洞察力和创造力，从磨砺程序员的实际问题中凝结出一篇篇编程“珠玑”，成为世界计算机界名刊《ACM通讯》历史上最受欢迎的专栏，最终结集为两部计算机科学经典名著，影响和激励着一代又一代程序员和计算机科学工作者。本书为第一卷，主要讨论计算机科学中最本质的问题：如何正确选择和高效地实现算法。

在书中，作者选取许多具有典型意义的复杂编程和算法问题，生动描绘了历史上大师们在探索解决方案中发生的轶事、走过的弯路和不断精益求精的历程，引导读者像真正的程序员和软件工程师那样富于创新性地思考，并透彻阐述和总结了许多独特而精妙的设计原则、思考和解决问题的方法以及实用程序设计技巧。解决方案的代码均以C/C++语言编写，不仅有趣，而且有很大的实战示范意义。每章后所附习题极具挑战性和启发性，书末给出了简洁的解答。 

01

计算机编程有很多方面。Fred *s在《人月神话》一书中为我们描绘了全景，他的文章强调了管理在大型软件项目中所起的关键作用。而Steve McConnell在《代码大全》一书中更具体地传授了良好的编程风格。这两本书所讨论的是好软件的关键因素和专业程序员应有的特征。遗憾的是，仅仅熟练地运用这些可靠的工程原理，不见得一定能够如期完成软件并顺利运行。

关于本书

本书描述了计算机编程更具魅力的一面：在可靠的工程之外，在洞察力和创造力范围内结晶而出的编程珠玑。正如自然界中的珍珠来自于磨砺牡蛎的细沙一样，这些编程珠玑来自于磨砺程序员的实际问题。书中的程序都很有趣，传授了重要的编程技巧和基本的设计原理。

本书大部分内容最初发表在《ACM通讯》中我主持的“编程珠玑”专栏。这些内容经过汇总和修订，在1986年结集出版，成为本书的第1版。第1版的13篇文章中，有12篇都在本版中做了大幅修订；此外，本版还补充了3篇新的内容。

阅读本书所需的唯一背景知识就是某种高级语言的编程经验。书中偶尔会出现一些高级技术（如C++中的模板等），对此不熟悉的读者可以跳过这些内容，基本上不影响阅读。

本书每一章都独立成篇，各章之间却又有着逻辑分组。第1章至第5章构成本书的第一部分，这部分回顾了编程的基本原理：问题定义、算法、数据结构以及程序验证和测试。第二部分围绕效率这个主题展开。效率问题有时本身很重要，又永远都是进入有趣编程问题的绝佳跳板。第三部分用这些技术来解决排序、搜索和字符串等重要问题。

阅读本书的一个提示：不要读得太快。要仔细阅读，一次读一章。要尝试解答书中提出的问题——有些问题需要集中精力思考一两小时才会变得容易。然后，要努力解答每章末尾的习题：当读者写下答案时，从本书学到的大部分知识就会跃然纸上。如有可能，要先与朋友和同事讨论一下自己的思路，再去查阅本书末尾的提示和答案。每章末尾的“深入阅读”并不算是学术意义上的参考文献表，而是我推荐的一些好书，这些书是我个人藏书的重要部分。

本书是为程序员而写的。我希望书中的习题、提示、答案和深入阅读对每个人都有用。本书已用作算法、程序验证和软件工程等课程的教材。附录A中的算法分类可供实际编程人员参考，该附录同时还说明了如何在算法和数据结构课程中使用本书。

02

一位程序员曾问我一个很简单的问题：“怎样给一个磁盘文件排序？”想当年我是一上来就犯了错误，现在，在讲这个故事之前，先给大家一个机会，看看能否比我当年做得更好。你会怎样回答上述问题呢？

1　一次友好的对话

我错就错在马上回答了这个问题。我告诉他一些有关如何在磁盘上实现归并排序的简要思路。我建议他深入研究算法教材，他似乎不太感冒。他更关心如何解决这个问题，而不是深入学习。于是我告诉他在一本流行的程序设计书里有磁盘排序的程序。那个程序有大约200行代码和十几个函数，我估计他最多需要一周时间来实现和测试该代码。

我以为已经解决了他的问题，但是他的踌躇使我返回到了正确的轨道上。其后就有了下面的对话，楷体部分是我的问题。

为什么非要自己编写排序程序呢？为什么不用系统提供的排序功能呢？

我需要在一个大系统中排序。由于不明的技术原因，我不能使用系统中的文件排序程序。

需要排序的内容是什么？文件中有多少条记录？每条记录的格式是什么？

文件最多包含1000万条记录，每条记录都是7位的整数。

等一下，既然文件这么小，何必非要在磁盘上进行排序呢？为什么不在内存里进行排序呢？

尽管机器有许多兆字节的内存，但排序功能只是大系统中的一部分，所以，估计到时只有1 MB的内存可用。

你还能告诉我其他一些与记录相关的信息吗？

每条记录都是7位的正整数，再无其他相关数据。每个整数最多只出现一次。

这番对话让问题更明确了。在美国，电话号码由3位“区号”后再跟7位数字组成。拨打含“免费”区号800（当时只有这一个号码）的电话是不收费的。实际的免费电话号码数据库包含大量的信息：免费电话号码、呼叫实际中转到的号码（有时是几个号码，这时需要一些规则来决定哪些呼叫在什么时间中转到哪里）、主叫用户的姓名和地址等。

这位程序员正在开发这类数据库的处理系统的一小部分，需要排序的整数就是免费电话号码。输入文件是电话号码的列表（已删除所有其他信息），号码重复出现算出错。期望的输出文件是以升序排列的电话号码列表。应用背景同时定义了相应的性能需求。当与系统的会话时间较长时，用户大约每小时请求一次有序文件，并且在排序未完成之前什么都干不了。因此，排序最多只允许执行几分钟，10秒钟是比较理想的运行时间。

2　准确的问题描述

对程序员来说，这些需求加起来就是：“如何给磁盘文件排序？”在试图解决这个问题之前，先将已知条件组织成一种更客观、更易用的形式。

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出：按升序排列的输入整数的列表。

约束：最多有（大约）1 MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。

请花上一分钟思考一下该问题的规范说明。现在你打算给程序员什么样的建议呢？

3　程序设计

显而易见的方法是以一般的基于磁盘的归并排序程序为起点，但是要对其进行调整，因为我们是对整数进行排序。这样就可以将原来的200行程序减少为几十行，同时也使得程序运行得更快，但是完成程序并使之运行可能仍然需要几天的时间。

另一种解决方案更多地利用了该排序问题的特殊性。如果每个号码都使用7字节来存储，那么在可用的1 MB存储空间里大约可以存143 000个号码。如果每个号码都使用32位整数来表示的话，在1 MB存储空间里就可以存储250 000个号码。因此，可以使用遍历输入文件40趟的程序来完成排序。在第一趟遍历中，将0至249 999之间的任何整数都读入内存，并对这（最多）250 000个整数进行排序，然后写到输出文件中。第二趟遍历排序250 000至499 999之间的整数，依此类推，到第40趟遍历的时候对9 750 000至9 999 999之间的整数进行排序。对内存中的排序来说，快速排序会相当高效，而且仅仅需要20行代码。于是，整个程序就可以通过一两页纸的代码实现。该程序拥有所期望的特性——不必考虑使用中间磁盘文件；但是，为此所付出的代价是要读取输入文件40次。

归并排序读入输入文件一次，然后在工作文件的帮助下完成排序并写入输出文件一次。工作文件需要多次读写。

40趟算法读入输入文件多次，写输出文件仅一次，不使用中间文件。

下图所示的方案更可取。我们结合上述两种方法的优点，读输入文件仅一次，且不使用中间文件。

只有在输入文件中的所有整数都可以在可用的1 MB内存中表示的时候才能够实现该方案。于是问题就归结为是否能够用大约800万个可用位来表示最多1 000万个互异的整数。考虑一种合适的表示方式。

4　实现概要

由是观之，应该用位图或位向量表示集合。可用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合。例如，可以用如下字符串来表示集合{1, 2, 3, 5, 8, 13}：

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

代表集合中数值的位都置为1，其他所有的位都置为0。

在我们的实际问题中，每个7位十进制整数表示一个小于1 000万的整数。我们使用一个具有1 000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。（那个程序员后来找到了200万个稀疏位，习题5研究了最大存储空间严格限制为1 MB的情况。）这种表示利用了该问题的三个在排序问题中不常见的属性：输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一整数外，没有任何其他关联数据。

若给定表示文件中整数集合的位图数据结构，则可以分三个自然阶段来编写程序。第一阶段将所有的位都置为0，从而将集合初始化为空。第二阶段通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。令n为位向量中的位数（在本例中为10 000 000），程序可以使用伪代码表示如下：

1/* phase 1: initialize set to empty */
2    for i = [0, n)
3        bit[i] = 0/* phase 2: insert present elements into the set */
4    for each i in the input file
5        bit[i] = 1/* phase 3: write sorted output */
6    for i = [0, n)
7        if bit[i] == 1
8            write i on the output file

（回想在前言中所提到的，for i=[0, n)表示在从0至n-1的范围内对i进行迭代。）

这个实现概要已经足以解决那个程序员的问题了。习题2、习题5和习题7描述了他会遇到的一些实现细节。

5　原理

那个程序员打电话把他的问题告诉我，然后我们花了大约一刻钟时间明确了问题所在，并找到了位图解决方案。他花了几小时来实现这个几十行代码的程序。该程序远远优于我们在电话刚开始时所担心的需要花费一周时间编写的几百行代码的那个程序。而且程序执行得很快：磁盘上的归并排序可能需要许多分钟的时间，该程序所需的时间只比读取输入和写入输出所需的时间多一点点——大约10秒钟。答案3包含了对完成该任务的几种不同程序的计时细节。

从这些事实中可以总结出该实例研究所得到的第一个结论：对小问题的仔细分析有时可以得到明显的实际益处。在该实例中，几分钟的仔细研究可以大幅削减代码的长度、程序员时间和程序运行时间。Chuck Yeager将军（第一个超音速飞行的人）赞扬一架飞机的机械系统时用的词是“结构简单、部件很少、易于维护、非常坚固”，该程序拥有同样的属性。然而，当规范说明的某些因素发生改变时，该程序的特殊结构将很难修改。除了需要精巧的编程以外，该实例阐明了如下一般原理。

正确的问题。明确问题，这场战役就成功了90%——我很庆幸程序员没有满足于我给出的第一个程序。一旦正确理解了问题，习题10、习题11和习题12的答案都会很优雅。在查看提示和答案以前，请努力思考这些问题。

位图数据结构。该数据结构描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有其他任何数据与该元素相关联。即使这些条件没有完全满足（例如，存在重复元素或额外的数据），也可以用有限定义域内的键作为一个表项更复杂的表格的索引，见习题6和习题8。

多趟算法。这些算法多趟读入其输入数据，每次完成一步。在1.3节已经见到了一个40趟算法，习题5鼓励读者去完成一个两趟算法。

时间—空间折中与双赢。编程文献和理论中充斥着时间—空间的折中：通过使用更多的时间，可以减少程序所需的空间。例如，答案5中的两趟算法让程序运行时间加倍从而使空间减半。但我的经验常常是这样的：减少程序的空间需求也会减少其运行时间。①空间上高效的位图结构显著地减少了排序的运行时间。空间需求的减少之所以会导致运行时间的减少，有两个原因：需要处理的数据变少了，意味着处理这些数据所需的时间也变少了；同时将这些数据保存在内存中而不是磁盘上，进一步避免了磁盘访问的时间。当然了，只有在原始的设计远非最佳方案时，才有可能时空双赢。

简单的设计。Antoine de Saint-Exupéry是法国作家兼飞机设计师，他曾经说过：“设计者确定其设计已经达到了完美的标准不是不能再增加任何东西，而是不能再减少任何东西。”更多的程序员应该使用该标准来检验自己完成的程序。简单的程序通常比具有相同功能的复杂的程序更可靠、更安全、更健壮、更高效，而且易于实现和维护。

程序设计的阶段。

今日荐书 《编程珠玑 第2版》

计算机科学经典著作：编程珠玑 第2版修订版 +编程珠玑（续 修订版）（京东套装共2册）

作者：[美]乔恩·本特利（Jon Bentley）

https://www.epubit.com/bookDetails?id=UB6c87641132d8a

https://item.jd.com/12243652.html

- END -