《编程珠玑》
总体观点
乔恩·本特利是贝尔实验室科学家，这本书是他《ACM 通讯》专栏的结集。“珠玑”就是从真实工程问题里打磨出的智慧珍珠——每章从一个真实难题讲起，带你看高手怎么思考。
核心论点：程序设计的功夫，一大半不在“写代码”，在“想清楚”。数据结构选对，难题自己变简单；动手前先估算，一半性能问题提前避开；先写对，再谈写快。全是案例，不讲大道理。
无数程序员的“算法启蒙书”和“面试圣经”。书很薄，每章读完都有“啊哈，原来还能这样”的顿悟。在“加机器加内存”的时代，它提醒你：聪明的设计永远比粗暴堆料更优雅、更便宜。
核心观点
-
1. 位图：换个数据结构，千万级排序so easy
内存只有 1MB，要给 1000 万个电话号码排序。解法是“位图”：用 1000 万个比特位，第 N 位是 1 就表示号码 N 存在。读一遍标记，扫一遍输出，排序完成。问题没变，换个角度，难题消失。
老师点名不用抄 60 个名字再排序，拿座位表，来的人打个勾，按座位念一遍就行。不存“人是谁”，只存“这个位置有没有人”。 -
2. 动手前，先在信封背面算一算
写代码前先在信封背面估算：数据量、时间、空间。“每天 1 亿请求，一年 365 亿条，一条 100 字节就是 3.6TB”——几秒钟心算，避开“数据比想象大、生产直接爆炸”。数量级对了就行。
请 500 人吃年夜饭：500×200 元=10 万预算，至少 50 桌。先估算再订厅，不会到那天傻眼。五分钟估算，省下五周返工。 -
3. 先度量，再优化：别猜瓶颈在哪
优化第一原则：先用 profiler 实测找到真瓶颈再动手。人的直觉在性能上经常是错的——你觉得慢的地方可能只占 1%，真吃 90% 时间的地方你压根没想到。不度量就优化，等于闭眼开车。
觉得电费高怪罪空调，装分路电表才发现是阳台十年没关的旧冰柜在偷电。不装电表就换空调，钱花了，电费一分没降。 -
4. 二分搜索：人人会写，几乎人人写错
思想三岁小孩都懂（每次砍一半），但绝大多数程序员写不出完全正确的二分搜索：边界、中点、循环不变式，差之一错之千里。写前先把“每轮都成立的断言”想清楚，让程序自己证明自己对。
猜数字 1-100，猜 50 说大了，范围变 1-49。到底是 49 还是 50、下次猜 25 还是 24，稀里糊涂。先立规矩：“要找的数永远在 [low, high] 闭区间里”，每轮检查规矩没破，代码不可能错。 -
5. 数据决定程序结构：先想数据，再想代码
动手写代码前，先把数据的样子想清楚——怎么存、长什么结构，代码结构自然跟出来。先写一堆代码再迁就数据，只会写出别扭的面条代码。好数据结构是好程序的骨架。
整理衣柜：先定“按季节分区、每格一类”，之后找衣服放衣服都顺手。一开始乱塞，之后每次找都得翻箱倒柜，还得贴张“找衣服攻略”。 -
6. “啊哈！”时刻：退一步，问题可能就化了
很多难题难在盯着正面硬刚；退一步换个角度，难题常变成不值一提的小事。比如数组循环移位：与其一个个元素挪，不如三次翻转搞定。顿悟不是运气，是刻意练习换角度的结果。
拧不开瓶盖别跟瓶盖较劲，瓶子倒过来热水冲一下盖子（热胀冷缩），轻轻一拧就开。问题没变，换个维度出手。 -
7. 取样问题：水塘抽样，以小见大
文件太大读不完，怎么从 N 个数均匀随机取 k 个？“水塘抽样”：只读一遍，维护 k 个元素的“水塘”，第 i 个数以 k/i 概率决定是否入选。内存永远只用 k 个位置，每个数被选中的概率完全均等。
从长河随机捞 10 条鱼尝咸淡，不可能抽干河。端个小盆站岸边，鱼游来一条按规矩决定换不换，越到后面换的概率越小。一趟下来，每条鱼被选中的机会均等。
全书思维导图 · 知识脉络树
全书结构
-
第1章 开篇
准确定义问题边界与约束，用位图（Bitmap）在极度受限的内存下秒级完成千万不重复电话号码排序。
在只有 1MB 可用内存的老旧机器上，不用复杂的外部归并排序，而用位图每一位代表一个电话号码，两轮扫描完成排序。 -
第2章 啊哈！算法
巧妙的算法灵感胜过蛮力盲干：如三次向量翻转实现数组极速原地旋转，基于字母排序签名实现秒级变位词字典归类。
把长度为 n 的数组向左旋转 i 位，只需分别翻转前 i 个元素、后 n-i 个元素，再全盘翻转一次，即可在 O(n) 时间 O(1) 空间完成。 -
第3章 数据决定程序结构
数据驱动编程，用结构化的静态表驱动替代复杂嵌套的业务条件判断，大幅缩减代码体积与分支错误。
计算不同阶梯税率或转换不同语言月份名称时，使用简单的静态数组查表，完全省去长达数十行的 if-else 分支。 -
第4章 编写正确的程序
用前置条件、后置条件和循环不变量严格证明程序正确性，防范二分查找在边界条件下的经典死循环与溢出 Bug。
计算二分查找中间位置时使用 `low + (high - low) / 2` 替代容易导致整型溢出的 `(low + high) / 2`。 -
第5章 编程小事
构建轻量级脚手架、先验断言、输入发生器与精确计时代码，支撑起严谨可靠的工程实验与调优验证。
在编写新排序算法前先写一个能自动生成随机数组、逆序数组和全相同数组的测试脚手架，一键对比各算法耗时。 -
第6章 程序性能分析
用性能剖析工具（Profiling）精准定位热点，将优化精力投入到消耗系统90%资源的10%核心瓶颈代码中。
通过火焰图分析发现整个系统耗时集中在一个高频调用中的正则表达式重复编译上，将其提升为常量后吞吐量提升十倍。 -
第7章 粗略估算
掌握费米估算（Fermi Estimation）、安全系数与72法则，在动手编码前快速预估系统吞吐量与存储规模量级。
在设计图片存储系统前，先口算“一千万用户每天上传两张图，每张 1MB，一年需要多少硬盘”，快速推导出存储架构预算。 -
第8章 算法设计技术
以最大子数组和问题为例，系统演示从 O(n^3) 蛮力、O(n^2) 累计和、O(n log n) 分治到 O(n) Kadane 动态规划的飞跃。
面对海量股票走势数据，用 Kadane 算法只需单次遍历同时维护当前和与全局最大和，毫秒级得出收益最大区间。 -
第9章 代码调优
循环展开、消除低效函数调用、预计算结果与使用哨兵值，在关键路径上合理实施底层微优化。
在密集的向量点乘计算中手动将循环展开为四路并发累加，充分利用 CPU 指令级流水线将执行速度提升 40%。 -
第10章 节省空间
设计紧凑的数据结构、稀疏数据压缩编码与缓冲区对象重用，以空间节省换取更好的 CPU 缓存局部性与整体性能。
将几百万个稀疏图节点从二维数组压缩为紧凑的邻接表（Adjacency List），内存占用下降两个数量级且运行更快。 -
第11章 排序
深入探究快速排序与插入排序的工业级实现细节，善用双向扫描、三数取中轴点与小数组切换插入排序的优化技巧。
标准库快排在递归到子数组长度小于 16 时停止快排并统一调用插入排序，有效规避递归开销大幅提升性能。 -
第12章 取样问题
掌握 Knuth 随机取样算法与水塘抽样（Reservoir Sampling），实现从未知总量的流式数据中等概率抽取固定样本。
在海量日志流中随机抽取 100 条用于审计，用蓄水池抽样算法只需遍历一遍，无需提前把全量日志加载进内存。 -
第13章 搜索
二叉搜索树、散列表与自组织链表的高效实现与工程取舍，按查询频率动态调整数据位置以减少比对。
对高频查询的未排序链表，每次查中某个节点就把该节点移到链表头部（LRU思想），使得后续平均查找次数逼近常数。 -
第14章 堆
用连续数组优雅实现二叉堆（优先队列），以极简的代码和 O(log n) 复杂度高效支撑任务调度与堆排序。
在从十亿条实时日志中找出访问耗时最高的 Top 100 请求时，用仅维护 100 个元素的小顶堆完成实时流式过滤。 -
第15章 字符串
散列技术、字典树（Trie）与后缀数组（Suffix Array）在海量文本处理与最长重复子串快速检索中的精妙应用。
在几十兆的基因序列中找出最长的重复片段，构造后缀数组并按字典序排序后，仅需比较相邻后缀即可闪电得出答案。