《编程珠玑》学习笔记：小书大道理，问题求解的完整闭环

目标读者：会写代码、刷过一些算法题，但想知道"真实工程里高手是怎么想问题"的程序员。
参考书籍：Jon Bentley《编程珠玑》（Programming Pearls）
阅读目标：提炼全书的问题求解闭环，把几个经典案例变成自己的思维肌肉。

0. 写在前面：一本"中间点"的书

如果给程序员的案头书排一条光谱：

• 一端是吴军《数学之美》：讲的是大思想——数学模型如何降维打击真实世界的问题，视野宏大，但离每天的代码有点远。
• 另一端是波利亚《怎样解题》：讲的是纯方法论——“看清问题、拟定计划、执行、回顾”，放之四海皆准，但抽象到几乎不给具体例子。

《编程珠玑》正好卡在中间：用一个个小而真的问题，走完"定义 → 估算 → 设计 → 验证 → 调优"的完整闭环。

它的出身就很"工程"：1983 年起，Jon Bentley 在贝尔实验室工作期间，为《ACM 通讯》（Communications of the ACM）主持 “Programming Pearls” 专栏，每期挑一个看似不起眼的小问题，带着读者从头到尾把它想透、写对、调快。专栏后来结集成书（1986 年初版，2000 年第二版），薄薄两百多页，却影响了整整几代程序员。

这本书的"珠玑"（pearls）不是奇技淫巧，而是一种工作方式：

把问题定义清楚，用估算摸清规模，设计正确的算法，证明它是对的，最后再谈调优。顺序不能乱。

下面我按这条主线，把书里最值得带走的几个案例提炼出来。

1. 全书主线：问题求解的完整闭环

先看一张全景图。这本书十五个专栏（第二版按五部分组织），其实都在打磨同一个闭环：

flowchart LR
    A["1 定义问题<br/>真正的输入输出是什么"] --> B["2 估算规模<br/>信封背面算一算"]
    B --> C["3 设计算法<br/>数据结构 + 算法策略"]
    C --> D["4 程序验证<br/>断言、边界、测试"]
    D --> E["5 代码调优<br/>测量驱动的优化"]
    E -.->|"发现假设不对"| A
    C -.->|"规模估算变了"| B

几个要点：

• 闭环是环，不是直线。调优时发现瓶颈，可能要回到算法设计；设计时发现规模估计错了，要回到估算；甚至写着写着发现"问题本身定义错了"——回到起点。
• 每一步都有"便宜可占"。定义清楚了，问题可能消失（位图排序）；估算做对了，方案直接收敛；验证做扎实了，能躲过标准库级别的 bug。
• 大部分程序员只在"设计"一环花力气，这正是这本书要纠正的。

下面五个案例，分别对应闭环上的关键环节。

2. 定义问题 + 算法设计：开篇的旋转数组

2.1 问题

把一个有 n 个元素的数组向左循环移动 i 位。比如 n=8、i=3：

原数组：  [1, 2, 3, 4, 5, 6, 7, 8]
左移 3 位：[4, 5, 6, 7, 8, 1, 2, 3]

约束：尽量少的额外空间（最好 O(1)），时间也要快。

2.2 解法一：逐一移动（正确但慢）

最直觉的做法：把 x[0] 存到临时变量，整体左移一位，把临时变量放到末尾；重复 i 次。

移动 1 次：[2, 3, 4, 5, 6, 7, 8, 1]
移动 2 次：[3, 4, 5, 6, 7, 8, 1, 2]
移动 3 次：[4, 5, 6, 7, 8, 1, 2, 3]  ✓

代码好写、肯定对，但时间是 O(n·i)——n 和 i 都是百万级时就是万亿次操作，直接出局。它的价值是当"对照组"：先有一个肯定正确的慢版本，后面所有快版本都可以拿它对拍。

2.3 解法二：求逆三次（全书的第一个"啊哈"）

把数组看成两段：AB（A 是前 i 个元素，B 是剩下的）。我们要 BA。

看一个神奇的操作序列（X’ 表示把 X 反转）：

原数组：  AB
反转 A：  A'B
再反转 B：A'B'
整体反转：(A'B')' = BA  ✓

手摇上面的例子（i=3）：

[1, 2, 3 | 4, 5, 6, 7, 8]   反转前 3 个
[3, 2, 1 | 4, 5, 6, 7, 8]   反转后 5 个
[3, 2, 1 | 8, 7, 6, 5, 4]   整体反转
[4, 5, 6, 7, 8, 1, 2, 3]    ✓

代码只需一个 reverse 函数加三次调用，O(n) 时间、O(1) 空间，短到几乎不可能写错：

reverse(0, i-1);
reverse(i, n-1);
reverse(0, n-1);

优雅在哪？ 旋转是个"整体"操作，我们却一直想逐个元素去搬；而反转是数组上最廉价、最不容易出错的局部操作，三次廉价的局部操作拼出了整体效果。Bentley 借这个例子想说的是：换个视角看问题，难题会塌缩成 trivial 的三行代码。 Brian Kernighan 评价这类代码是"既正确又明显地正确"——这是软件里最高级的状态。

2.4 解法三：块交换 / 杂耍算法

还有第三条路：把数组按 gcd(n, i) 分成若干"循环链"，每条链上的元素像杂耍一样依次归位（juggling algorithm）；或者递归地做块交换。时间同样是 O(n)，移动次数比求逆法略少，但代码明显复杂、边界更容易错。

三种解法摆在一起，就是一堂微型的方法论课：

一句话理解：先写"蠢但对"的版本建立信心，再找"巧且短"的版本上线，复杂版本只用于学习。

3. 重新定义问题：位图排序（1MB 排 900 万个电话号码）

这是全书第一章 “Cracking the Oyster”（撬开牡蛎）的核心案例，也是"定义问题"环节最漂亮的一次示范。

3.1 问题（来自真实场景）

一个文件里有至多 900 万个整数，每个都是 7 位数（即 0 ~ 9,999,999），没有重复。要把它们排序输出。可用内存大约 1 兆字节，磁盘空间充足。

3.2 第一反应：归并排序

标准答案是多路归并：内存里一次读一批，排序后写回磁盘，再多趟归并。正确、通用，但要好几趟磁盘读写，代码也不少。

在动手之前，Bentley 追问了一句：这个问题里有哪些信息被我忽略了？

• 每个数恰好出现一次（无重复）；
• 数值范围是已知的、有限的（10^7 种可能）；
• 除了排序之外没有其他操作；
• 没有关联数据（不像学生记录要跟着学号走）。

3.3 关键洞察：用"位"表示"存在"

如果把这些约束用足，答案呼之欲出：不存数字本身，只存"这个数出现过没有"。

用一个 10^7 位的位图（bitmap），第 j 位为 1 表示整数 j 在输入里。10^7 位 = 1,250,000 字节 ≈ 1.19 MB，刚好塞进那点可怜的内存。整个排序变成三趟：

1. 把所有位置 0；
2. 读入每个整数 i，把第 i 位置 1；
3. 从头到尾扫一遍位图，把为 1 的位依次输出——天然有序。

flowchart TD
    A["输入文件<br/>至多 900 万个 7 位整数<br/>无重复"] --> B["阶段一<br/>10^7 位的位图全部置 0"]
    B --> C["阶段二<br/>每读到一个整数 i<br/>把第 i 位置 1"]
    C --> D["阶段三<br/>从 0 到 10^7-1 扫描位图<br/>位为 1 就输出下标"]
    D --> E["输出文件<br/>已排序"]

没有比较、没有交换、没有归并——排序问题被转化成了表示问题。时间 O(n)，磁盘只顺序读写两遍，代码量远小于归并方案。

3.4 这个案例真正教的东西

• 问题的表象 ≠ 问题的本质。 嘴上说的是"排序"，实质是"有限集合的表示与枚举"。一旦换了表示法，排序"消失"了。
• 追问约束是最大的杠杆。 “无重复"和"范围有限"这两句话，价值千金。真实工作里，甲方给的条件往往比我们用上的多。
• 思想有长长的影子。 位图索引、Bloom Filter（布隆过滤器）、Redis 的 bitmap、Roaring Bitmap，都是"用位表示存在性"这条线上的后代。今天在海量数据去重、用户签到、UV 统计里天天在用。

一句话理解：当值域有限且无重复时，“存在性位图"可以把排序、去重、判重全部压成 O(n) 的位操作。

4. 算法设计：最大子数组和的复杂度演进

如果说位图排序展示的是"重新定义问题”，最大子数组展示的就是闭环里"设计"环节的完整教科书：同一个问题，四个算法，复杂度连降三级。

4.1 问题

输入一个有 n 个数的数组（有正有负），找出连续子数组中和最大的那个，返回这个最大和。

小例子：[-2, 11, -4, 13, -5, -2]，答案是 20（子数组 [11, -4, 13]）。

这个问题不是编造的智力题。它源自布朗大学 Ulf Grenander 做模式识别时遇到的二维问题：在数字图像里找"最像某个模式"的子区域。二维版本太贵，他先把它化简到一维——化简本身就是设计的一部分。

4.2 四个版本的演进

版本一：O(n³) 暴力。 枚举所有起点 i 和终点 j，对每对 (i, j) 把中间的数加起来。n=1000 时约 10^9 次加法，已经没法用了。

版本二：O(n²)。 注意到 sum(i..j+1) = sum(i..j) + x[j+1]——内层循环不用从头加，带着上一次的累加和走就行。一次"重用已有计算”，干掉一个数量级。

版本三：O(n log n) 分治。 把数组从中点劈开。最大子数组只有三种可能：全在左半、全在右半、跨过中点。前两种递归解决；跨中点的答案 = 从中点向左扫描的最大后缀和 + 向右扫描的最大前缀和，O(n) 内搞定。T(n) = 2T(n/2) + O(n)，总共 O(n log n)。

版本四：O(n) 扫描线。 从左到右扫一遍，维护"以当前元素结尾的最大子数组和"：

ending_here = max(x[i], ending_here + x[i])
so_far      = max(so_far, ending_here)

直觉：一个负数前缀对后面只有拖累。当累加和变成负数，果断扔掉，从下一个元素重新开始。手摇上面的例子：

i  x[i]  ending_here  so_far
0   -2       -2          0   (负数前缀，扔掉)
1   11       11         11
2   -4        7         11
3   13       20         20   ← 答案
4   -5       15         20
5   -2       13         20

这就是后来大名鼎鼎的 Kadane 算法。

flowchart LR
    subgraph 演进["同一个问题的四次设计"]
        V1["版本一 暴力枚举<br/>O(n³)"] -->|"重用累加和"| V2["版本二 前缀复用<br/>O(n²)"]
        V2 -->|"分而治之"| V3["版本三 分治<br/>O(n log n)"]
        V3 -->|"负数前缀果断丢弃"| V4["版本四 扫描线<br/>O(n)"]
    end
    V4 --> R["n=10^6 时<br/>从'算到宇宙热寂'<br/>到毫秒级"]

4.3 真实掌故：高手也不是一步到位的

Bentley 在书里交代了这段历史，非常值得记住：Grenander 把一维问题抛给卡内基梅隆的 Michael Shamos，Shamos 一夜之间设计出 O(n log n) 的分治算法——当时他们都觉得这大概就是极限了。后来在一次研讨会上，统计学家 Jay Kadane 听了一分钟，当场给出了 O(n) 算法。

这个故事的两层启示：

• 连 Shamos 这个级别的算法专家，第一反应也不是最优解。 算法设计是迭代的，不是顿悟的。
• 每降一个数量级，靠的都是一个新视角：重用计算、分治、负数前缀丢弃——而不是更卖力的实现。

工程连接：这个 O(n) 扫描思想今天活在很多地方——股票最大收益、信号处理里的峰值检测、乃至面试最高频题。而"版本二"的累加和技巧，就是前缀和数组，是区间查询类问题的通用武器。

5. 程序验证：二分查找，一个藏了九年的标准库 bug

闭环里最容易被跳过的一环是"验证"。Bentley 用二分查找给了所有自信的程序员一记耳光。

5.1 一个尴尬的事实

二分查找的思想小学生都懂：有序数组里每次砍一半。但 Bentley 在贝尔实验室和后来的课程里反复做过同一个实验：请专业程序员（给了充足时间、任意语言、可以用高级伪码）写出正确的二分查找，结果大约 90% 的人写错。

这不是个案。他在书里引用过一个考据：第一个二分查找的发表版本出现在 1946 年，而第一个对任意长度数组都正确的发表版本，要等到 1962 年。十六年里，所有人发表的版本都有 bug。

Knuth 在《计算机程序设计艺术》第三卷里说得更直白（大意）：二分查找的思想虽然简单，细节却可能棘手得出乎意料——很多好程序员都在这上面栽过跟头。

5.2 坑都藏在哪

错的从来不是"砍一半"这个思想，而是边界：

• 区间定义不清：while (low < high) 还是 low <= high？mid 算出来之后，新区间是 [low, mid-1] 还是 [low, mid]？两两组合里只有一种自洽。
• 差一位错误（off-by-one）：死循环在 n=2 的小数组上，或者漏查最后一个元素。
• 返回值的语义：没找到时返回 -1？还是返回插入位置？调用方怎么处理？

5.3 标准库级别的翻车：溢出 bug 藏了九年

2006 年，Google 首席 Java 架构师 Joshua Bloch 在官方博客发了一篇著名的文章《Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken》，自曝家丑：

java.util.Arrays.binarySearch 里的这行代码——

int mid = (low + high) / 2;

是错的。 当 low 和 high 都很大时，low + high 会溢出成负数，mid 变成负值，抛 ArrayIndexOutOfBoundsException。更扎心的是：这段代码最初正是 Bloch 自己写的，在他的《Effective Java》里也作为范例出现过；同样的 bug 还潜伏在归并排序的实现里，而且在 JDK 里藏了大约九年才被发现——因为要让 low + high 溢出，数组得大到 10^9 量级，当年的机器根本装不下这么大的数组。

修复方式也很"珠玑"：

int mid = low + (high - low) / 2;        // 减法会溢出吗？low<=high 时不会
int mid = (low + high) >>> 1;            // 或者用无符号右移

5.4 验证环节的正确姿势

Bentley 的对策不是"更聪明"，而是更机械：

• 用循环不变式写程序：写二分查找前先写下"如果目标存在，它一定在 [low, high] 区间内"，每一轮循环保持这个断言为真，程序的正确性就跟着不变式走，而不是靠感觉。
• 断言（assert）进代码：把不变式直接写成断言，测试期全部打开。
• 小数据穷举对拍：n=0、1、2、3 的所有情况手算或穷举，目标值在开头、结尾、中间、不存在各试一遍。
• 拿慢版本对拍：用一个 O(n) 线性查找和二分查找在随机数据上跑几万次，结果必须一致——这就是 2.2 节"蠢但对"版本的真正用途。

一句话理解：简单算法 + 复杂边界 = 专业坟场。正确性不靠自信，靠不变式和机械验证。

6. 估算的艺术：信封背面的算术

闭环里的"估算"环节，Bentley 把它叫做 back-of-the-envelope calculation（信封背面估算）：在餐厅信封背面用粗略数字、心算，三分钟搞清楚问题的规模。它的目的不是精确，而是在投入大量工作之前，先确认方向是不是错的。

6.1 为什么要估算

回到位图排序的例子：那个"大约 1MB 内存"的约束，配合"至多 900 万个 7 位数"，先算一笔——

• 如果每个数存成 32 位整数：900 万 × 4 字节 = 36 MB，内存放不下，所以"全部读进内存排序"这条路当场枪毙；
• 而 10^7 位的位图 ≈ 1.19 MB，勉强塞得下，方案成立。

两笔心算，直接决定了整个方案的形态。这就是估算的价值：它花三分钟，替你省掉三天返工。

6.2 随身武器一：72 法则

钱以年利率 r% 复利增长，大约 72/r 年翻一番。年利率 6%，约 12 年翻倍；利率 12%，约 6 年翻倍。

这个法则对程序员的用处远超理财——凡是指数增长的东西都适用：

• 数据量每年涨 40%？72/40 ≈ 1.8 年翻一倍，三年后是现在的 5 倍多，现在的存储架构撑得住吗？
• 程序每慢 1 倍，意味着规模翻倍时要多等一倍时间——反过来，复杂度从 O(n²) 降到 O(n log n) 在 n 翻倍时省多少，心算就能估出来。

6.3 随身武器二：π 秒就是一个纳世纪

Bentley 在书里给了一个极好记的常数：π 秒 ≈ 一纳世纪（nanocentury，10^-9 个世纪 ≈ 3.155 秒）。

用法：程序每秒跑多少操作、跑一世纪要多久，换算成"纳世纪"立刻有直觉。比如一个操作 1 微秒，跑 10^9 次就是 1000 秒 ≈ 318 个纳世纪 ≈ 6 分钟——心里有没有数，决定你要不要现在就换算法。

再配几个该背下来的量级：

• 2^10 ≈ 10^3（千），2^20 ≈ 10^6（百万），2^30 ≈ 10^9（十亿）；
• 磁盘顺序读比随机读快几个数量级；内存比磁盘快约 10^5 倍；
• 一年约 π × 10^7 秒。

6.4 随身武器三：安全系数与双重估算

Bentley 建议的重要习惯：同一个问题用两种不同路径估算，结果应该对得上；对不上就查到哪里错了。

书里举过估算密西西比河日径流量的例子：一条路径从"流域面积 × 降雨"估，另一条从"河道宽度 × 深度 × 流速"估，两个粗算结果在同一个数量级上吻合，估算就可信。工程里的翻版：系统容量规划时，既从"日活 × 人均请求 × 峰值系数"往下算，也从"单机压测 QPS × 机器数"往上顶，两边对上才算完。

工程连接：今天这活叫 capacity planning，面试里叫 Fermi 问题（“北京有多少个加油站”）。内核没变：粗糙但快速的数字直觉，是工程师防止自己被宏大叙事欺骗的唯一武器。

7. 代码调优：闭环的最后一环，也是最危险的一环

7.1 先立规矩

Bentley 对调优的态度非常克制，三条规矩：

1. 先正确，再调优。 调优引入的复杂度会制造 bug，而一个跑得快但算错的程序毫无价值。
2. 先测量，再调优。 瓶颈几乎从不在你以为的地方。用 profiler 找到热点，只调那 5% 的代码。
3. 算法层级收益 » 代码层级收益。 O(n²) 换 O(n log n) 可能快一千倍；循环展开通常只快百分之几十。调优是锦上添花，不是雪中送炭。

7.2 书里反复出现的几招

缓存（避免重复计算）。 如果同一个值被算了很多次，算一次存起来。最现代的版本就是 memoization 和各级缓存体系。书里有个经典场景：频繁计算 c[i][j] 这类昂贵表达式，而它在循环里其实不变——把循环不变式提到循环外，或者干脆预处理一张表。

哨兵（sentinel）。 顺序查找时，先把要查找的值放到数组末尾当"哨兵"，内层循环就可以省掉"是否越界"的判断，比较次数近似减半：

x[n] = t;                    /* 哨兵：保证一定能找到 */
for (i = 0; x[i] != t; i++)  /* 循环里只剩一个比较 */
    ;

查找命中与否分开处理。思想内核：用一次提前的准备，换掉循环里千万次的检查。 今天的 std::string 以 \0 结尾、链表的 dummy head 节点，都是哨兵思想的亲戚。

循环展开。 把循环体复制几份，减少循环控制开销。Bentley 同时警告：展开会让代码变长、指令缓存变挤，而且现代编译器自己会做。手写展开之前，先确认编译器没帮你做，并且 profiler 说这里值得。

测试重排。 一串 if-else 判断，把命中频率最高的条件放最前面。思想内核和哈夫曼编码一样：高频路径应该最短。

7.3 今天的读者要打个折扣

这本书写于编译器还笨、内存按 KB 算的年代。今天读调优章节要带两个过滤器：

• 编译器已经很强：很多手工强度削减、展开，-O2 会替你做，手写反而碍事；
• 瓶颈换了地方：当年的敌人是指令数，今天的敌人常常是缓存未命中和内存墙——Bentley 的"缓存重复计算"思想没过时，但主战场从 ALU 挪到了 cache line。

不变的元规则：测量驱动。 不调没测过的代码，不信没数字的优化。

8. 番外：Bentley 与 Knuth 的那次交锋

这是计算机科学史上很有名的一段公案，也值得单独记一笔。

1986 年，Bentley 在自己的专栏里请 Donald Knuth 展示他倡导的 literate programming（文学编程，用 WEB 系统把代码和文档织在一起）。Knuth 领的题目很朴素：读一个文本文件，统计并输出出现次数最多的 k 个单词及次数。

Knuth 交出了一篇十多页、结构精妙的 WEB 程序，专为这个问题设计了一个巧妙的数据结构（带计数的有序 trie）。Bentley 把它发了出来，同时请 Unix 之父之一的 Doug McIlroy 写书评。McIlroy 的评论比程序本身更出名——他指出 Knuth 程序的优雅毋庸置疑，但整个问题用 6 行 Unix shell 就能解决：

tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed ${1}q

而且这 6 行是每个工程师随手可写、可改、可组合的。

这场交锋没有输家，它留下的启示是双面的：

• Knuth 展示了为一个值得的问题量身打造工具与文档能达到的深度；
• McIlroy 展示了用已有简单工具组合，可能比重新发明深刻十倍的轮子更工程。

这正是《编程珠玑》整本书的张力所在：深度与简单，各自在什么场合赢。 Bentley 把两篇都发表出来，本身就是"珠玑"。

9. 带走的清单

把全书压成一张可以贴在工位上的清单：

想问题时

• 先把问题用一句话写清楚：输入、输出、约束。约束里往往藏着解法（位图排序）。
• 信封背面先算规模：数据多大、时间预算多少、哪些方案当场出局（36MB vs 1.19MB）。
• 问一句"这个问题有没有更简单的等价形式"——旋转数组的三次求逆就是这么来的。

写代码时

• 先写"蠢但对"的版本，留作对照组，方便对拍。
• 每降一个数量级靠新视角，不靠更卖力：重用计算 → 分治 → 丢弃无用信息。
• 写二分查找这类"简单"算法时，先写循环不变式，再写代码；n=0、1、2 手动过一遍。
• 记住 (low + high) / 2 会溢出：用 low + (high - low) / 2。标准库都翻过车，你没有豁免权。

调优时

• 先 profile，只调热点；调优前后各测一次，没数字不算数。
• 优先换算法和数据结构，再考虑代码级技巧。
• 哨兵、缓存重复计算、循环不变式外提，这三招便宜又安全；循环展开先问编译器。

作为工程师

• 背上 72 法则和 “π 秒 = 纳世纪”，让指数增长在你心里有形状。
• 重要估算走两条独立路径，对上了才信。
• 读 Knuth vs McIlroy 之争：深刻的方案和简单的方案，各自配得上各自的问题。

这本书两百多页，值回票价的理由只有一个：它教的不是答案，而是从拿到问题到交付代码之间，那段大多数人凭感觉乱走的路程，其实每一步都有章法。

参考书籍：Jon Bentley《编程珠玑》（Programming Pearls, 2nd Edition）；Joshua Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, 2006。

• 读书笔记

• 编程珠玑
• 算法
• 问题求解
• 二分查找
• 位图
• 代码调优
• 估算
• Jon Bentley
• 学习笔记

方糖猫（大可）

18 年后端架构，现在独立做 AI 产品。这里记录 AI 视频、AI Agent 与工程实践。