第 16 章　工程实践与综合

本章解决的问题：前面 15 章学的结构与范式，在真实工程里怎么挑、怎么用？以及怎么验证你选的那个真的对，而不是"看起来很快"？

16.1　选型手册：按场景选数据结构

学习目标：学完本节，你能

• 按操作特征（查/增/删/序/范围/最值）快速选定结构，并说出它的代价；
• 认出七种最常见的误用，并说出它们各自慢在哪；
• 在性能之外，把内存、并发、可读性一起纳入选型；
• 用一套四步决策流程处理没见过的场景。

先修：第 1–15 章（本节要把它们汇总起来）。 固定术语：全书术语表（195 条）。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：全书其实只回答了一个问题

前 15 章讲了 12 种数据结构、20 多个算法。如果只能带走一句话，应该是这句：

"这件事，我该用什么装？"

而这句话背后是一个更具体的问题：

"我要对它做的操作，哪个结构做得最快？" —— 这就是"选型"。

小陈在第 1 章问过一个问题："为什么同样的功能，换个写法能差 8.5 万倍？" 15 章之后，他可以自己回答了：因为不同的结构，把不同的操作做成了 O(1)、O(log n) 或 O(n)。

这一节把散落在全书的答案汇总成两张表 —— 一张按"操作"查，一张按"场景"查。

二、按操作查

先问自己："我最频繁的操作是什么？"然后查这张表。

这张表要横着看，也要竖着看：

横着看：每一行都有"首选"和"代价"两列。 没有任何一个结构是免费的全能选手 —— 哈希表快但不能排序，数组能随机访问但插入慢，堆能取最值但不能查任意元素。

竖着看："查找"这一列几乎都被哈希表占了 —— 这就是为什么第 6 章花了整整一节讲它。

一个快速判断法：

如果你的操作清单里"查"占绝对多数 → 先考虑哈希表； 如果还要"有序"或"范围" → 换成 BST； 如果只关心"最值" → 堆； 如果"顺序"本身就是答案（如依赖关系） → 拓扑排序。

三、按场景查

操作清单不好列的时候，从场景反查更快。

四、实测：同一个任务，三种做法

"选型"听起来很虚，所以本节用一个真实任务把它做实。

任务：100 万个订单 ID，找出出现次数最多的前 10 个。

数据分布很关键 —— 按真实日志的样子：90% 的请求打在最热的 100 个 ID 上（重尾分布）。

三种实现：

实测：

    实现                    耗时        前 3 名（ID: 次数）
    --------------------    ---------   ----------------------------
    A. 排序 + 扫描             30.5 ms   89: 9,287,  30: 9,247,  47: 9,211
    B. 哈希表 + 全排序         15.4 ms   89: 9,287,  30: 9,247,  47: 9,211
    C. 哈希表 + 小顶堆         14.2 ms   89: 9,287,  30: 9,247,  47: 9,211

  不同的 ID 实际有 90,199 个
    三者的【次数序列】完全一致：True
    三者的【ID 序列】也完全一致：False   <- 名次有并列，选哪个 ID 是等价的

先看那个 False —— 它是个好提醒：

三种实现选出的"10 个 ID"不完全相同，因为第 10 名附近有并列， 而三种实现的遍历顺序不同，挑出的具体 ID 就不同。

但"次数序列"完全一致 —— 这才是业务真正关心的东西。

这也说明"Top-K"在并列时结果不唯一 —— 和 7.2 节的"排序稳定性"是同一类问题： 一定要事先约定平局规则，否则两次运行的结果可能不一样。

再看耗时：

    C 相对 A：快 2.2 倍
    C 相对 B：基本持平（差异在噪声范围内）

看这三行代码差在哪：

C 相对 B 只快一点点（14.2 vs 15.4 ms，在噪声范围内）—— 这与 11.4 节"Top-K 比全排序快 23.2 倍"并不矛盾：

11.4 节是全排序 100 万个，这里是全排序 9 万个。 排序的规模小了一个数量级，堆的优势也就没那么明显了。

这又一次印证了 13.1 节的规矩：差距不到 2 倍、且复现不了五次以上的，"谁更快"不要写进结论。

再对比一个"没选对结构"的写法

如果不用哈希表，而是"对每一个不同的 ID 都把整个数组扫一遍来数"：

    规模          不同 ID 数    暴力          哈希+堆      暴力慢多少
    ----------    ----------    -----------   ----------   ----------
    50,000        200                 3.4 ms      0.25 ms       13.7 倍
    200,000       800                46.5 ms      0.96 ms       48.7 倍

  注意最后一列【在变大】：规模涨 4 倍，差距从十几倍涨到四十几倍。
    暴力是 O(n × m)，n 和不同 ID 数一起涨 —— 所以是平方级；
    哈希 + 堆是 O(n)，只随 n 线性涨。

这一列"在变大"的数字，就是"复杂度"这一整套理论的实战意义：

它不是告诉你"现在谁快"，而是告诉你"规模涨上去之后谁会被甩开"。

13.4 节那个"Bellman-Ford 在随机图上反而比 Dijkstra 快 5.6 倍"就是这个道理的另一面 —— 在小规模、好数据上，复杂度高的一方可能赢；但那不是可以依赖的。

五、七个最常见的误用

下面每一条，都是本书前面某节真跑出来过的：

前两条最值得背下来 —— 因为它们在真实代码里出现的频率最高，而且改起来最简单：

// 慢：每次查找都是 O(n)，套在循环里就是 O(n²)
if (list.Contains(x)) { ... }

// 快：O(1)
var set = new HashSet<int>(list);
if (set.Contains(x)) { ... }

// 慢：每次出队都要搬移整个数组，O(n)
var q = new List<T>();
var item = q[0]; q.RemoveAt(0);

// 快：O(1)
var q = new Queue<T>();
var item = q.Dequeue();

六、性能之外的三个维度

选型不只看速度。 下面三件事经常一票否决。

1. 内存

同样一件事，内存可能差一个数量级：

内存紧张时，"先选对结构"比"再优化"有效得多 —— 因为这些都是数量级的差距。

2. 并发

本书讲的所有结构都【不是线程安全】的 —— 这一点必须说清楚：

⚠️ 一个容易被忽略的点："只读共享"是安全的，但要求【构造完之后真的不再修改】 —— 如果某处偷偷加了一个元素，就变成了"边读边写"，那是未定义行为。

3. 可读性

最后一条，也最容易被工程师自己忽略：

一个 O(log n) 但没人看得懂的自平衡树，不如一个 O(n) 但一眼能看懂的数组 —— 前提是 n 真的不大。

15.4 节已经说过类似的话：先把二维 DP 写对、跑通、对拍过，再压缩。 选型也一样：先写对，再优化。

七、决策流程

遇到一个新场景，按这四步走：

  第 1 步：把操作清单列出来
          —— 查找？插入？删除？排序？范围？最值？各占多大比例？

  第 2 步：找出【最频繁】的那个操作
          —— 选型的核心是"为最热的操作选结构"，不是"找一个全能选手"

  第 3 步：按第二节的表查首选项，再看它的代价能不能接受
          —— 不能接受就退到次选

  第 4 步：用【实测】验证
          —— 规模、数据分布都按真实情况造；对拍；多轮取最快

第 4 步为什么不能省？ 因为本章后面两节都在讲同一件事：

16.2 节会讲"理论复杂度和实际性能差在哪"（缓存、分支预测、GC）； 16.3 节会把这一整套流程用一个真实项目走一遍。

本书从 1.1 节就在说："看起来该快"和"实际快"是两件事， 而唯一能区分它们的方法是——跑一遍。

八、练习

练习 16.1.1（按操作选型） 为下面的需求各选一个结构，并说出它的代价：

(a) 一个网站要统计"每个 IP 今天访问了多少次"。 (b) 一个游戏要频繁地"取出当前血量最低的单位"。 (c) 一个编辑器要支持"撤销"（可能连续撤销 100 次）。 (d) 一个通讯录要支持"按姓名首字母范围查询"（查所有姓"李"到"林"的人）。 (e) 一个任务队列要支持"两端都能进出"。

练习 16.1.2（误用识别） 下面几段代码都"能跑"，但结构选错了。指出该换成什么，并估算大概快多少倍：

(a) ```csharp var seen = new List(); foreach (var word in words) if (!seen.Contains(word)) seen.Add(word);

```

(b) ```csharp var buffer = new List(); while (buffer.Count > 0) { var j = buffer[0]; buffer.RemoveAt(0); Run(j); }

```

(c) ```csharp var cache = new Dictionary(); // ... 取缓存时按顺序遍历，期望"最近插入的排最后"

```

(d) ```csharp // 一个 10 万层的树，用递归求高度 int Height(Node n) => n == null ? 0 : 1 + Math.Max(Height(n.Left), Height(n.Right));

```

练习 16.1.3（设计） 设计一个 LRU 缓存（容量固定，满了就淘汰"最久未使用"的），要求 Get 和 Put 都是 $O(1)$。

(a) 只用哈希表行不行？为什么？ (b) 只用双向链表行不行？为什么？ (c) 说出你的方案，以及每一步操作为什么是 $O(1)$。

练习 16.1.4（判断） 判断对错并说明理由：

(a) 哈希表在所有场景下都比 BST 快。 (b) 只要复杂度对，实际性能就一定有保证。 (c) 选结构时，先写对再优化，比"一上来就选最快的"更稳妥。 (d) 本书讲的数据结构可以直接用在多线程环境里。

九、练习答案

16.1.1

(d) 的关键是：哈希表做不到范围查询 —— 它根本不排序。 这正是第二节表格里"按 key 查找"和"范围查询"分成两行的原因。

16.1.2

(a) 该用 HashSet<string>。

估算：6.1 节实测"哈希表 vs 暴力查找"差约 1 万倍。

原因：List.Contains 是 $O(n)$，套在循环里变成 $O(n^2)$；HashSet 把每次查找降到 $O(1)$。

(b) 该用 Queue<Job>。

估算：5.2 节实测差 70 倍。

原因：List.RemoveAt(0) 要把后面所有元素往前搬一格，是 $O(n)$；Queue.Dequeue 是 $O(1)$。

(c) 不该依赖 Dictionary 的顺序 —— 要么改用 SortedDictionary，要么自己记录顺序。

原因：6.4 节明确说过，Dictionary 的遍历顺序不保证，而且会随扩容变化。 依赖它 = 依赖一个没写进契约的实现细节，换个 .NET 版本就可能失效。

注意这里不是"慢多少倍"的问题，而是"对不对"的问题 —— 这类错误比性能问题危险得多。

(d) 该改成迭代（或用 Thread 开大栈）。

原因：13.1 节实测，递归 DFS 在 10 万层的链上栈溢出崩溃（只压进 9,628 层栈帧就满了）， 而且 StackOverflowException 无法 try/catch（2.2 节）。

这不是"慢"的问题，是"直接死"的问题。

16.1.3

(a) 只用哈希表不行。

因为哈希表不知道"谁最久没被用过" —— 它没有顺序。 淘汰时需要找出"最久未使用"的那个，哈希表只能遍历全部来找 —— 那是 $O(n)$。

(b) 只用双向链表不行。

因为 Get(key) 需要先【找到】那个节点 —— 链表的查找是 $O(n)$。

(c) 方案：哈希表 + 双向链表。

为什么每一步都是 $O(1)$：

这个方案是"两个结构各补对方的短板"的经典例子：

• 哈希表补了链表的"查找慢"
• 双向链表补了哈希表的"没有顺序"

15.4 节的空间优化也是同一个思路（用一维数组 + 临时变量补上二维表的信息）—— 当单个结构不够用时，先问"缺的是哪条信息"，再找一个能提供它的结构。

16.1.4

(b) 是本节最该记住的一条： 复杂度决定的是"规模涨上去之后谁被甩开"，不是"现在谁快"。

实测数字才是当前场景下的答案 —— 而这正是 16.2 节的主题。

十、常见错误

十一、本节总结

1. 全书其实只回答一个问题："这件事，我该用什么装？" —— 而它的具体形式是"我最频繁的操作是什么"。
2. 按操作查的表：随机访问→数组；按 key 查→哈希表；有序/范围→BST；最值→堆；Top-K→小顶堆；两端→双端队列；任意位置增删→链表；去重计数→哈希表。
3. 每一行都有代价：哈希表无序、堆不能查任意元素、链表不能随机访问。没有全能选手。
4. 实测：同一个任务三种做法（100 万个订单 ID 找 Top-10）： A 排序+扫描 30.5 ms / B 哈希+全排序 15.4 ms / C 哈希+小顶堆 14.2 ms。 C 相对 A 快 2.2 倍，相对 B 基本持平 —— 因为这里全排序的只有 9 万个，不是 100 万个。
5. 一个重要的细节：三种实现的次数序列完全一致，但 ID 序列不一致（名次有并列）。 Top-K 在并列时结果不唯一 —— 必须事先约定平局规则。
6. "没选对结构"的代价会随规模放大：暴力版在 5 万规模慢 13.7 倍，在 20 万规模慢 48.7 倍。
7. 七个最常见的误用（List.Contains 1 万倍、RemoveAt(0) 70 倍、依赖 Dictionary 顺序、递归深链……），前两条最值得背。
8. 性能之外还有三个维度：内存（差 52.6~1994 倍）、并发（全都不是线程安全的）、可读性（n 小时它更值钱）。
9. 四步决策流程：列操作 → 找最频繁的 → 查表并检查代价 → 实测验证。

下一节衔接：本节反复说"复杂度说明趋势，实测才是当前答案"，但没有展开讲为什么。

16.2 节回答这个问题：理论复杂度和实际性能之间，到底隔着什么？

• 缓存（3.1 节埋的线：顺序访问比随机访问快 15 倍）
• 分支预测
• GC（1.1 节埋的线：GC 导致实测偏差）
• 基准测试的常见陷阱（13.1 节已经踩过：微基准的 20% 差异是噪声）

换句话说，16.2 节要把"怎么测"这件事本身讲清楚 —— 因为本节第 9 条说的"实测验证"，测得不对等于没测。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "16.1",
  "title": "选型手册：按场景选数据结构",
  "covered": [
    "「全书只回答一个问题」的收束视角",
    "按操作特征查的 15 行速查表（含每行的代价）",
    "按场景查的 15 行对照表（覆盖全书各章成果）",
    "实测：同一个 Top-10 任务的三种实现（30.5 / 15.4 / 14.2 ms）",
    "「C 相对 B 基本持平」与 11.4 节「快 23.2 倍」不矛盾的原因（排序规模不同）",
    "Top-K 并列时结果不唯一（次数序列一致、ID 序列不一致）",
    "暴力写法在两种规模上的差距放大（13.7 倍 → 48.7 倍）",
    "七个最常见的误用及其实测倍率",
    "性能之外的三个维度：内存 / 并发 / 可读性",
    "四步选型决策流程"
  ],
  "unresolved": [
    "理论复杂度与实际性能的差距来源留到 16.2",
    "并发数据结构的细节（ConcurrentDictionary、分片）超出本书范围",
    "LRU 缓存的完整实现只在练习中给出方案，未给代码"
  ],
  "canonical_terms": {
    "选型（选数据结构）": "根据最频繁的操作选择结构，并接受它相应的代价",
    "LRU 缓存": "容量固定、淘汰最久未使用项的缓存；用哈希表 + 双向链表实现 O(1) 操作"
  },
  "symbols_units": {
    "n": "元素个数",
    "m": "不同键的个数",
    "K": "Top-K 里的 K"
  },
  "assumptions": [
    "读者已读完第 1–15 章（本节的表格是对它们的汇总）",
    "读者理解 13.1 节「差距不到 2 倍且复现不了五次以上的不要下结论」",
    "本节所有倍率均引自前面各节的实测，未重新测量"
  ],
  "word_count_actual": 2764,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch16/Sec161/",
    "实验：100 万 ID（90% 集中在前 100 个）找 Top-10，三种实现 30.5/15.4/14.2 ms，为实测",
    "实验：次数序列一致 True、ID 序列一致 False（并列导致），为实测",
    "实验：暴力版在 5 万规模 13.7 倍、20 万规模 48.7 倍，为实测",
    "速查表中的倍率均摘自前面各节的实测（6.1/5.2/4.1/13.2/6.4/13.1/11.4/12.1/15.4），未杜撰"
  ],
  "known_issues": [
    "实验初版用「两个随机数相乘」造重尾分布，效果不足（最高频 ID 只出现 35 次），Top-K 失去意义 —— 改为「90% 请求打在前 100 个 ID 上」，最高频到了 9,287 次",
    "初版三种实现的结果校验用「ID 序列完全相同」，得到 False；原因是名次并列时三种实现的遍历顺序不同，挑出的 ID 不同 —— 改为同时报告「次数序列」（True）和「ID 序列」（False），并把这个现象写成教学点（呼应 7.2 节的排序稳定性）",
    "初版暴力对照只有 5 万一个规模、且不同 ID 数固定为 200，导致比值只有 5 倍 —— 改为两个规模、且不同 ID 数随规模增长（size/250），才让「差距随规模放大」这个结论显出来（13.7 → 48.7 倍）",
    "初版输出里有 Markdown 的 ** 加粗语法，在控制台会原样打印 —— 已去掉"
  ],
  "next": "16.2 从复杂度到实测：性能剖析"
}