外部排序 · 终极无死角自学笔记
定位:假设你以后彻底忘了这一章,或者正准备上 408 考场,只看这一篇就能把底层直觉、算法运转、公式推导、考场暗坑全部捡回来。全程大白话推演,零省略、零错漏。
第 0 章:外部排序为什么存在?(底层逻辑与成本账本)
0.1 物理矛盾:桌子太小,牌太多
假设你要给 \(100\text{ GB}\) 的扑克牌(数据记录)从小到大排序,但你的桌子(内存)最多只能摊开 \(8\text{ GB}\) 的牌。剩下的牌全部锁在仓库(磁盘)里,每次只能用小推车搬一小摞到桌子上。 - 内存(RAM):极快,但容量小,断电丢数据。 - 外存(磁盘/SSD):容量极大,但读写速度比内存慢 \(10^5 \sim 10^6\) 倍。
因为物理上根本不可能把 \(100\text{ GB}\) 数据一次性塞进内存,所以平时学的快速排序、堆排序、内部归并排序(这些统称内部排序,要求所有数据随时能在内存里随机访问)全部失效。为此专门设计的“内存 \(+\) 磁盘协同排序方案”,就叫外部排序(External Sorting)。
0.2 决定全章走向的铁律:瓶颈不在“算”,而在“搬”
- CPU 在内存里比较两个数:纳秒级(\(10^{-9}\text{ s}\))
- 磁盘读写一次数据块:毫秒级(\(10^{-3}\text{ s}\))
两者相差近百万倍!这意味着:哪怕你在内存里多做几万次比较,也比不上少读一次磁盘划算。 因此,外部排序的设计哲学只有一个核心目标——千方百计减少磁盘读写(I/O)次数。后面学的所有高大上名词(多路归并、败者树、置换-选择、最佳归并树),全都是在为“少跑几趟仓库”服务。
0.3 I/O 是怎么算账的:按“块”搬运,绝不按“条”搬运
操作系统在内存和磁盘之间搬运数据,绝对不是一条记录一条记录地搬,而是一块(Block / Page)一块地搬。
- 一个磁盘块通常有几 \(\text{KB}\)(比如 \(4\text{ KB}\)),里面紧凑地装着几十甚至上百条记录。
- 内存里会开辟专门的缓冲区(Buffer),大小刚好等于一个磁盘块(或整数倍)。
- 读入:一次 Read I/O,直接把磁盘上一整块数据装满内存的输入缓冲区,然后 CPU 在缓冲区里一条条慢悠悠地处理。
- 写出:CPU 把排好序的记录一条条塞进输出缓冲区,塞满一整块后,触发一次 Write I/O,整块写回磁盘。
核心推论:一趟处理下来,读写的 I/O 次数严格等于“文件占用的总磁盘块数 \(b\)”,跟里面装的数字是 \(1\) 还是 \(99999\)、记录长什么样毫无关系!
第 1 章:基本方法——分两步走(生成初始段 \(+\) 多路归并)
既然桌子一次放不下所有牌,最符合人类直觉的做法就是“分批理顺,再分组合并”。
第 1 步:生成初始归并段(第 0 趟:分批内部排序)
假设文件总共有 \(b\) 个磁盘块,而内存工作区最多只能同时容纳 \(m\) 条记录(对应若干个块): 1. 从磁盘顺序读入一批能塞满内存的数据; 2. 在内存里用传统的内部排序(如快排、堆排,或者第 4 章要讲的置换-选择排序)把这批牌从小到大排好; 3. 把排好序的这批牌写回磁盘,单独放成一摞。 4. 重复上述过程,直到把整个文件切分完毕。
结果:磁盘上现在躺着 \(r\) 摞牌。每一摞内部是严格有序的,但摞与摞之间是乱序的。 - 核心术语:这每一摞排好序的子文件,叫做一个初始归并段(Initial Run,简称顺串)。 - I/O 账单:这一步把整个文件完整读了一遍(\(b\) 次读)、排好序又完整写回磁盘一遍(\(b\) 次写)。所以生成初始归并段固定消耗 \(2b\) 次 I/O!千万别漏算!
第 2 步:\(k\) 路平衡归并(把 \(r\) 摞合成 \(1\) 摞)
现在磁盘上有 \(r\) 摞有序的牌,怎么把它们合成最终的 \(1\) 大摞? 我们在内存桌面上同时摆开 \(k\) 个输入缓冲区(对应 \(k\) 摞牌)和 \(1\) 个输出缓冲区: 1. 选定 \(k\) 摞牌,把每一摞的第 1 块读入各自对应的输入缓冲区; 2. 每摞牌只看最上面露头的那一张(因为每摞内部有序,露头的这张必定是该摞目前的最小值); 3. 选最小:在这 \(k\) 张露头的牌里找出最小的一张,拿走放进输出缓冲区; 4. 补牌与触发 I/O: - 哪一摞被拿走了一张,就由该输入缓冲区的下一张记录顶上; - 如果某摞的输入缓冲区被拿空了,立刻从磁盘读取该摞的下一块填满缓冲区; - 如果该摞在磁盘上的所有块都读完了,这摞就彻底退出竞争; - 如果输出缓冲区被塞满了,立刻把它整块写回磁盘,清空后继续装。 5. 当这 \(k\) 摞全部耗尽时,它们就在磁盘上合并成了新的、长度翻了 \(k\) 倍的 \(1\) 大摞有序牌。
把 \(k\) 个有序段合并成 \(1\) 个有序段的过程,就叫 \(k\) 路归并(\(k\)-way Merge)。
1.3 考点深挖:内存里到底需要几个缓冲区?
这是一个非常经典的 408 选择题考点,取决于你追求“能跑就行”还是“CPU 与磁盘并行不卡顿”:
| 模式 | 输入缓冲区数量 | 输出缓冲区数量 | 总缓冲区数 | 运作特点与缺陷 |
|---|---|---|---|---|
| 基础串行模式 | \(k\) 个 | \(1\) 个 | \(k + 1\) 个 | 任何一个输入缓冲空了,或输出缓冲满了,CPU 必须停下来干等磁盘 I/O 完成,串行等待,效率低。 |
| 双缓冲并行模式 | \(2k\) 个 | \(2\) 个 | \(2k + 2\) 个 | 每路配“使用缓冲 \(+\) 预读缓冲”,输出配“装填缓冲 \(+\) 写出缓冲”。CPU 在内存做归并的同时,磁盘在后台并行读写另一半缓冲区,无缝衔接! |
第 2 章:全章计分板——趟数与总 I/O 公式
2.1 归并趟数公式 \(S\)
什么叫“一趟(Pass)”? 因为内存有限,一次最多只能同时合 \(k\) 摞(通常 \(k \ll r\))。我们把磁盘上的 \(r\) 摞牌,按每 \(k\) 摞一组,分批轮流合并。当所有的 \(r\) 摞都被处理完一遍,全部数据在磁盘上被完整读一遍 \(+\) 完整写一遍,摞数从 \(r\) 缩小为 \(\lceil r / k \rceil\),这就叫一趟归并。
每过一趟,摞数就除以 \(k\)。一直除到只剩最终的 \(1\) 摞为止,一共需要归并多少趟? $\(S = \lceil \log_k r \rceil\)$ - \(r\):初始归并段的个数(初始有几摞) - \(k\):归并路数(一次合几摞) - \(\lceil \cdot \rceil\):向上取整(只要还剩超过 \(1\) 摞,哪怕不够 \(k\) 摞,也必须再跑最后一趟合起来)
举例:初始有 \(r = 1000\) 摞,采用 \(k = 13\) 路归并: * 第 1 趟后:\(\lceil 1000 / 13 \rceil = 77\) 摞 * 第 2 趟后:\(\lceil 77 / 13 \rceil = 6\) 摞 * 第 3 趟后:\(\lceil 6 / 13 \rceil = 1\) 摞(排序完成!) 共经历了 \(S = \lceil \log_{13} 1000 \rceil = 3\) 趟归并。
2.2 为什么不能把 \(k\) 开到无限大,“一趟全合完”?
初学者最爱问:既然 \(k\) 越大趟数越少,我有 \(1000\) 摞,直接搞个 \(1000\) 路归并,一趟合成 \(1\) 摞不就完了吗? 物理限制原因有二: 1. 内存空间限制(主因):\(k\) 路归并至少要在内存里开辟 \(k+1\) 个缓冲区。如果 \(k\) 开得太大,内存被切成几千个极其细碎的微型缓冲区,每个缓冲区小到装不下几个字节,就丧失了“按大块顺序读写”的优势,导致磁头频繁寻道,I/O 反而爆炸。所以 \(k \le \text{可用内存容量} \div \text{单个缓冲块大小}\)。 2. CPU 内部比较开销暴涨(次因):每次输出一条记录,都要在 \(k\) 个排头里选最小。如果不用特殊数据结构(见第 3 章败者树),每次选最小要比较 \(k-1\) 次,\(k\) 太大时 CPU 计算时间会反过来拖垮总时间。
2.3 外部排序的总时间与总 I/O 账单(408 必背公式)
外部排序的总时间由三部分组成: $\(\text{外部排序总时间} = \text{生成初始归并段的时间} + \text{外部信息读写(I/O)时间} + \text{内部归并比较时间}\)$
如果只算 磁盘 I/O 次数(设文件共有 \(b\) 个磁盘块,采用均匀的 \(k\) 路平衡归并): 1. 生成初始归并段(第 0 趟):读 \(b\) 块 \(+\) 写 \(b\) 块 \(= 2b\) 次 I/O。 2. 每跑 1 趟归并:读 \(b\) 块 \(+\) 写 \(b\) 块 \(= 2b\) 次 I/O。 3. 跑 \(S = \lceil \log_k r \rceil\) 趟归并:共 \(2b \times S\) 次 I/O。
因此,外部排序的总 I/O 次数公式为: $\(\text{总 I/O 次数} = 2b + 2b \times \lceil \log_k r \rceil = 2b \times (\lceil \log_k r \rceil + 1)\)$
考场保命警告:做题时一定要拿荧光笔圈出题干问的是什么! * 如果问“归并过程中的 I/O 次数”:答案是 \(2b \times S\)(或最佳归并树下的 \(2 \times \text{WPL}\))。 * 如果问“外部排序的总 I/O 次数 / 总读写次数”:必须加上生成初始归并段的那 \(2b\)!漏加直接痛失 \(2\) 分!
2.4 几何图像:归并过程就是一棵倒长的 \(k\) 叉树
我们可以把多趟归并的过程画成一棵 \(k\) 叉树(归并树):
[ 最终 1 个完整有序文件 ] <-- 树根
/ | \
[中间段] [中间段] [中间段] <-- 第 2 趟归并结果
/ | \ / | \ / | \
[1] [2] [3] [4] [5] [6] [7] [8] [9] <-- 叶子:初始归并段(共 r 个)
- 树的叶节点 \(=\) 初始归并段(共 \(r\) 个)
- 树的非叶节点 \(=\) 一次合并操作(生成的新归并段)
- 树的高度(不含根的层数 / 叶子的深度) \(=\) 归并趟数 \(S = \lceil \log_k r \rceil\)
- 叶子的深度 \(d\) \(=\) 该初始段被完整读写的趟数(深度为 \(d\),就经历 \(d\) 次读 \(+\) \(d\) 次写)。
2.5 全章主线导览图:三大神技各管哪一环?
看着公式 \(S = \lceil \log_k r \rceil\) 和上面的 \(k\) 叉树,要想减少 I/O,全章只有三条路可走,对应三大核心考点:
| 优化方向 | 数学目标 | 遇到的阻碍 | 解决它的核心算法(考点) |
|---|---|---|---|
| 路线 1:把分母 \(k\) 变大 | 增大归并路数 \(k\),压低树高 \(S\) | \(k\) 变大后,每选一个最小元素要比较 \(k-1\) 次,CPU 算不过来 | 第 3 章:败者树(Loser Tree) 把选最小的比较次数从 \(k-1\) 压到 \(\lceil \log_2 k \rceil\) |
| 路线 2:把分子 \(r\) 变小 | 减少初始归并段个数 \(r\),压低树高 \(S\) | 内存只有 \(m\) 大,普通内排切出的每段长度死死卡在 \(m\) | 第 4 章:置换-选择排序 边输出边读入,让平均段长突破到 \(2m\),\(r\) 直接减半 |
| 路线 3:优化树的形状 | 段长短不一时,让大段少搬、小段多搬 | 均匀归并会让很长的段也被搬很多趟,浪费 I/O | 第 5 章:最佳归并树(\(k\) 叉哈夫曼树) 长段放浅层、短段放深层,不够分支时补虚段 |
第 3 章:败者树(Loser Tree)——让归并路数 \(k\) 放心开大
3.1 为什么需要它?(算笔明白账)
假设总共有 \(N\) 条记录做 \(k\) 路归并: - 如果用最笨的线性扫描在 \(k\) 个排头里找最小:每输出 \(1\) 条记录要比较 \(k-1\) 次,输出全部 \(N\) 条记录一趟要比较 \(N(k-1)\) 次。总共 \(S = \lceil \log_k r \rceil\) 趟,总比较次数为: \(C_{\text{线性}} = \lceil \log_k r \rceil \times N(k - 1) = \frac{\ln r}{\ln k} \times N(k - 1)\) 你会发现,当 \(k\) 增大时,\(\frac{k-1}{\ln k}\) 是单调递增的!也就是说,\(k\) 开得越大,CPU 内部比较的时间反而呈爆炸式增长,把省下来的磁盘 I/O 时间全给抵消了! - 如果引入败者树:每次找最小并调整只需 \(\lceil \log_2 k \rceil\) 次比较。总比较次数变为: \(C_{\text{败者树}} = \lceil \log_k r \rceil \times N \lceil \log_2 k \rceil \approx \frac{\log_2 r}{\log_2 k} \times N \log_2 k = N \log_2 r\) 奇迹发生了:式子里的 \(\log_2 k\) 被完美约掉了!总比较次数彻底与归并路数 \(k\) 无关! 这意味着只要内存缓冲区够用,你可以把 \(k\) 尽情开大,CPU 比较开销丝毫不会增加!
3.2 败者树长什么样?(结构解剖)
败者树本质上是一棵用来打“淘汰赛”的完全二叉树,用来记录锦标赛的过程。
对于 \(k\) 路归并,败者树由两部分数组构成:
1. \(k\) 个叶节点(外节点)b[0 ... k-1]:存放 \(k\) 摞牌各自当前露头的那一张记录(每摞只派 1 名代表参赛)。
2. \(k\) 个非叶节点(内节点)ls[0 ... k-1]:存放的是段号(即数组 b 的下标索引,代表几号选手),绝不存记录本身!
- 其中 ls[1 ... k-1] 共 \(k-1\) 个节点,构成标准完全二叉树的内部分支节点(即“比赛场地”),每个格子记录这场比赛输掉的人(败者,即关键字更大的那个)的段号。
- ls[0] 单独悬在树根头顶上,记录全场总冠军(最终胜者,即全场最小值)的段号。
[ ls[0]: 最终总冠军段号 ]
|
( ls[1]: 总决赛败者段号 ) <-- 树根
/ \
( ls[2]: 半决赛A败者 ) ( ls[3]: 半决赛B败者 )
/ \ / \
[b[0]] [b[1]] [b[2]] [b[3]] <-- 叶子:4 个归并段的当前排头
3.3 完整运作流程(以 \(k = 4\) 为例手把手推演)
比赛规则:选小的赢(小者为胜者,大者为败者)。败者留在原地当守门员,胜者晋级往上走!
假设 4 个归并段当前的排头分别是:b[0] = 10,b[1] = 5,b[2] = 12,b[3] = 8。
第一阶段:初始建树(两两捉对厮杀)
- 半决赛 A(
ls[2]):b[0](10)vsb[1](5)\(\to\)5小所以赢,10输。 - 动作:败者
b[0]的段号0留守写进ls[2];胜者b[1](5)晋级去打总决赛。 - 半决赛 B(
ls[3]):b[2](12)vsb[3](8)\(\to\)8小所以赢,12输。 - 动作:败者
b[2]的段号2留守写进ls[3];胜者b[3](8)晋级去打总决赛。 - 总决赛(
ls[1]):晋级的b[1](5)vsb[3](8)\(\to\)5赢,8输。 - 动作:败者
b[3]的段号3留守写进ls[1];最终总冠军b[1]的段号1登上王座写进ls[0]!
此时树的状态:
- 叶子:b[0]=10, b[1]=5, b[2]=12, b[3]=8
- 内部节点:ls[2]=0(值为10), ls[3]=2(值为12), ls[1]=3(值为8)
- 冠军王座:ls[0] = 1(对应最小值 5)
第二阶段:输出冠军,补新牌并调整(核心考点!)
- 输出与补牌:根据
ls[0] = 1,直接把b[1]的5送入输出缓冲区。紧接着从第 1 段抽下一张牌(假设是15)补进b[1]。 - 沿路径向上挑战守门员:新来的
b[1](15)不需要重打整个锦标赛,它只需要顺着老冠军当年晋级的那条路(b[1]\(\to\)ls[2]\(\to\)ls[1]\(\to\)ls[0])一路往上走,路过哪个场地,就跟那个场地的守门员(败者)单挑一场: - 第 1 站(半决赛 A
ls[2]):新挑战者b[1](15)vs 原守门员ls[2]里记的b[0](10)。- 结果:
10 < 15,所以原守门员b[0](10)赢了!新来的b[1](15)输了! - 动作:败者留下,胜者往上!
ls[2]改记新败者1(即15),而赢家b[0](10)替补继续往上走去打总决赛!
- 结果:
- 第 2 站(总决赛
ls[1]):刚上来的胜者b[0](10)vs 总决赛守门员ls[1]里记的b[3](8)。- 结果:
8 < 10,所以总决赛守门员b[3](8)赢了!b[0](10)输了! - 动作:
ls[1]改记新败者0(即10),而赢家b[3](8)继续往上走!
- 结果:
- 终点站(冠军位
ls[0]):上面再也没人拦着了,赢家b[3]直接登基,ls[0]改记3(对应新全场最小值8)!
你看,只经过了 \(2\) 次比较(等于树高 \(\log_2 4 = 2\)),新的全场最小值 8 就选出来了!如果某个归并段彻底空了怎么办?只需往它的叶子塞一个虚拟的 $+\infty$,它就会逢战必输、永远垫底,直到所有段都变成 \(+\infty\),排序结束。
3.4 灵魂追问:为什么非要记“败者(输家)”,记“胜者(赢家)”不行吗?
这是面试和考研最喜欢深挖的机理题!如果内部节点记录每一场的赢家,那叫胜者树(Winner Tree)。为什么外部排序抛弃胜者树,独宠败者树?
想明白一个逻辑:
当总冠军 5 被拿走、新牌 15 补上来时,另一半赛区(半决赛 B)根本没受任何影响。
新牌 15 想要证明自己是新的全场最小,它需要打败谁?它只需要打败“当年被老冠军 5 亲手淘汰掉的那批手下败将”!
- 在败者树里,父节点存的正好就是当年那场比赛输给老冠军的人(守门员)。所以新牌往上走时,直接跟父节点比就行了!不需要看兄弟节点是谁! 每上一层,严格只做 \(1\) 次比较。
- 如果用胜者树(父节点存赢家):因为老冠军一路赢到底,从叶子到根整条路径上存的全是老冠军自己!新牌补上来后,抬头看父节点——父节点是空的(老冠军走了),它不知道当年这一场是谁输了,必须扭头去访问兄弟节点才能找到对手。这不仅增加了寻址开销,在代码实现和树结构维护上也比败者树繁琐得多。
3.5 败者树 vs 胜者树 vs 堆(考场满分对比表)
| 对比维度 | 败者树(Loser Tree) | 胜者树(Winner Tree) | 二叉堆(Min-Heap) |
|---|---|---|---|
| 树形态与节点数 | \(k\) 个叶子 \(+\) \(k-1\) 个内节点 \(+\) \(1\) 个冠军位 | \(k\) 个叶子 \(+\) \(k-1\) 个内节点 | 共 \(k\) 个节点(无内外节点之分) |
| 内部节点存什么 | 败者的段号(索引),数据不动 | 胜者的段号(索引),数据不动 | 记录本身(调整时需在数组内搬移记录) |
| 调整时跟谁比 | 直接和父节点比(无需看兄弟) | 必须找兄弟节点比,胜者写回父节点 | 父节点需先比左右孩子(\(1\) 次),再和自己比(\(1\) 次) |
| 调整一次比较次数 | 严格 \(\lceil \log_2 k \rceil\) 次(每层 1 次) | \(\lceil \log_2 k \rceil\) 次(但需额外读取兄弟节点) | 最坏 \(2 \lfloor \log_2 k \rfloor\) 次(每层 2 次) |
| 初始化建树比较次数 | \(k\) 次调整,共约 \(k \lceil \log_2 k \rceil\) 次 | \(k - 1\) 次 | \(O(k)\) |
第 4 章:置换-选择排序(Replacement-Selection)——把每摞变长,减小 \(r\)
4.1 痛点与动机
在普通方法里,如果内存工作区只能装 \(m\) 条记录,那么每次读入 \(m\) 条排好写出去,切出来的每个初始归并段长度死死固定为 \(m\)。如果有 \(n\) 条记录,就会切出 \(r = \lceil n / m \rceil\) 个初始段。 思考:能不能在生成初始归并段时,采用“边输出、边读入”的流水线方式,让切出来的每一摞长度突破内存容量 \(m\) 的限制?每摞越长,总摞数 \(r\) 就越少,归并趟数 \(S = \lceil \log_k r \rceil\) 就越少!这就是置换-选择排序。
4.2 算法规则:两种理解视角(直觉打标版 vs 408 败者树标准版)
视角一:直觉“打标记”版(做手算模拟题最快)
假设内存工作区容量为 \(m\),我们要生成升序(从小到大)的初始归并段:
1. 先从输入文件读入 \(m\) 条记录塞满工作区;
2. 挑出工作区里最小的记录输出到当前归并段,并记住这个刚输出的值为 MINIMAX(当前段的守门线);
3. 立刻从输入文件补进 \(1\) 条新记录顶替空位;
4. 核心判决:
- 如果 新记录 \(\ge\) MINIMAX:太好了!它比刚输出的那张牌大,接在当前这一摞后面完全合法(不会破坏递增序),让它正常参与当前段的后续选拔;
- 如果 新记录 \(<\) MINIMAX:糟了!刚输出了 50,现在来个 14,要是把 14 放进当前摞,递增序就毁了!所以给这张 14 贴上封条(打标记 *,视作 \(+\infty\))——它不能参与当前段的选拔,但继续留在内存工作区里占着坑位,留给下一段用!
5. 如此循环,直到工作区里的 \(m\) 个位置全部被贴上了封条,说明当前这一摞实在接不下去了,当前归并段正式结束!
6. 撕掉工作区里所有封条,开启下一个新归并段,继续上述过程,直到输入文件读空、工作区也排空为止。
视角二:408 教材标准实现版(容量为 \(m\) 的败者树 \(+\) 段号双关键字)
在严蔚敏教材与 408 统考真题中,置换-选择排序的底层数据结构正是第 3 章讲的败者树(叶节点容量为 \(m\))!
计算机里怎么优雅地实现“打封条”和“撕封条”而不用每次遍历数组呢?
- 绝妙设计:给进入工作区 wa[0 ... m-1] 的每一条记录配两个属性:key(关键字大小)和 rc(Run Number,所属归并段号,初始为 \(1\))。
- 补牌定段号:当输出 MINIMAX 并补进一条新记录时:
- 若 \(\text{新记录.key} \ge \text{MINIMAX}\),则它的段号不变:\(\text{新记录.rc} = \text{当前段号 } rc\);
- 若 \(\text{新记录.key} < \text{MINIMAX}\),直接把它的段号加一:\(\text{新记录.rc} = rc + 1\)(代表分入下一段)!
- 败者树双关键字比较规则:在败者树向上调整PK时,先比段号 rc(段号小的直接赢!);只有段号相同时,才比关键字 key(关键字小的赢!)。
- 这样一来,段号为 \(rc+1\) 的记录遇到段号为 \(rc\) 的记录时必定输掉,天然达到了“被雪藏”的效果!当某天登顶 ls[0] 的总冠军段号变成了 \(rc+1\),就说明第 \(rc\) 段自动结束了,无缝切换到第 \(rc+1\) 段!连清空标记的步骤都省了!
4.3 完整真题手工模拟(\(m = 4\),共 \(19\) 条记录)
输入序列:51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
内存工作区容量 \(m = 4\)。带 * 号表示该元素小于刚输出的 MINIMAX,已被打入下一段(本段内冻结):
第一段(Run 1)生成过程:
| 步骤 | 动作前工作区状态(容量 \(m=4\)) | 选出最小输出(MINIMAX) |
从文件补入新数 | 判决(新数 vs MINIMAX) |
动作后工作区状态 |
|---|---|---|---|---|---|
| 初始 | 读入前 4 个数 | — | 51, 94, 37, 92 |
全部属于第 1 段 | [51, 94, 37, 92] |
| 1 | [51, 94, 37, 92] |
37 | 14 |
\(14 < 37 \to\) 冻结标 * |
[51, 94, 14*, 92] |
| 2 | [51, 94, 14*, 92] |
51 | 63 |
\(63 \ge 51 \to\) 正常可用 | [63, 94, 14*, 92] |
| 3 | [63, 94, 14*, 92] |
63 | 15 |
\(15 < 63 \to\) 冻结标 * |
[15*, 94, 14*, 92] |
| 4 | [15*, 94, 14*, 92] |
92 | 99 |
\(99 \ge 92 \to\) 正常可用 | [15*, 94, 14*, 99] |
| 5 | [15*, 94, 14*, 99] |
94 | 48 |
\(48 < 94 \to\) 冻结标 * |
[15*, 48*, 14*, 99] |
| 6 | [15*, 48*, 14*, 99] |
99 | 56 |
\(56 < 99 \to\) 冻结标 * |
[15*, 48*, 14*, 56*] |
此时工作区 [15*, 48*, 14*, 56*] 全军覆没(全部带 *),第 1 段宣告结束!
- 第 1 个初始归并段:37, 51, 63, 92, 94, 99(长度 \(= 6\),成功突破了工作区容量 \(m=4\)!)
第二段(Run 2)与第三段(Run 3)生成过程:
撕掉所有 * 号,工作区恢复为 [15, 48, 14, 56],继续按同样规则往后走:
- 依次输出 14(补 23 可用)\(\to\) 输出 15(补 60 可用)\(\to\) 输出 23(补 31 可用)\(\to\) 输出 31(补 17* 冻结)\(\to\) 输出 48(补 43* 冻结)\(\to\) 输出 56(补 8* 冻结)\(\to\) 输出 60(补 90 可用)\(\to\) 输出 90(补 166 可用)\(\to\) 输出 166(补 100* 冻结)。
- 注:请严格按步骤核对,实际在输出 14 补 23、输出 15 补 60、输出 23 补 31、输出 31 补 17*、输出 48 补 43*、输出 56 补 8*、输出 60 补 90、输出 90 补 166、输出 166 补 100* 后,工作区变为 [17*, 43*, 8*, 100*],第 2 段结束(共 \(9\) 个元素:14, 15, 23, 31, 48, 56, 60, 90, 166);最后文件已读空,工作区剩下的 \(4\) 个数直接排好输出为第 3 段:8, 17, 43, 100。
- 对比成效:\(19\) 条记录、内存只能放 \(4\) 条,普通内排必须切成 \(\lceil 19/4 \rceil = 5\) 段,而置换-选择排序只切出了 \(3\) 段!
4.4 置换-选择排序的段长规律(高频客观题结论)
设文件共有 \(n\) 条记录,内存工作区容量为 \(m\)(且 \(n \gg m\)): 1. 最大值 \(= n\)(只生成 \(1\) 个段):当输入文件本身就是正序(递增)或每个新读入的数都恰好 \(\ge\) 刚输出的数时,永远不会触发冻结标记,一路畅通无阻把整个文件合成 \(1\) 段,段长为 \(n\)。 2. 前段最小值 \(= m\)(最坏情况:输入完全逆序/递减):当输入文件完全逆序(递减)时,每补进来一个数必定比刚输出的小,立刻被冻结。把初始工作区里的 \(m\) 个数输出完后,新补进来的 \(m\) 个数恰好全部被冻结,段被迫结束。因此除了最后一段外,前面的每一个归并段长度至少为 \(m\)。 - 408 满分细节排雷:千万别无脑背“所有段最小长度都是 \(m\)”!最后一个归并段的长度完全可能小于 \(m\)!因为当输入文件被读空时,工作区里残留着几个带标记的数,它们凑成最后一段,个数可能只有 \(1 \sim m\) 个(例如 \(n=10, m=4\) 且全逆序,切出的三段长度分别为 \(4, 4, 2\),最后一段长度为 \(2 < 4\))。 3. 随机数据的期望平均值 \(= 2m\):数学家 Knuth 用漂亮的“扫雪机模型(Snowplow Analogy)”证明了:若输入数据随机分布,置换-选择排序生成的初始归并段平均长度为工作区大小 \(m\) 的 \(2\) 倍(即 \(2m\))!这意味着初始段数 \(r\) 直接减半!
第 5 章:最佳归并树(Optimal Merge Tree)——长短不一时的最优合并策略
5.1 新麻烦:置换-选择切出的段“长短不一”
用完第 4 章的置换-选择排序后,磁盘上的初始归并段个数 \(r\) 确实变少了,但出现了一个副作用:每一摞的长度不再相等了!
假设切出了 \(4\) 个初始归并段,占用的磁盘块数分别为 2, 3, 6, 9(总块数 \(b = 20\)),现在做 \(2\) 路归并。
回忆第 2.4 节:一个初始段在归并树里的深度是 \(d\),它就要被完整地读 \(d\) 次、写 \(d\) 次!
我们对比两种合并顺序:
- 笨方案(先合大的):先把 6 和 9 合成 15,同时把 2 和 3 合成 5;最后把 5 和 15 合成 20。
- 此时四个段深度全都是 \(2\),总处理块数 \(= (2+3+6+9) \times 2 = 40\) 块,归并 I/O \(= 40 \times 2 = 80\) 次。
- 聪明方案(短段早合,长段晚合):
1. 第 1 步:选最短的 2 和 3 合并成 5;
2. 第 2 步:选次短的 5 和 6 合并成 11;
3. 第 3 步:最后把 11 和大胖子 9 合并成 20!
- 看看现在的深度:2 和 3 深度为 \(3\)(搬了 \(3\) 趟),6 深度为 \(2\)(搬了 \(2\) 趟),而最庞大的 9 深度只有 \(1\)(只参加了最后一趟归并,搬了 \(1\) 趟)!
- 总处理块数 \(= 2 \times 3 + 3 \times 3 + 6 \times 2 + 9 \times 1 = 6 + 9 + 12 + 9 = \mathbf{36}\) 块!归并 I/O \(= 36 \times 2 = \mathbf{72}\) 次!白白省下了 \(8\) 次磁盘读写!
5.2 本质揭秘:最佳归并树就是 \(k\) 叉哈夫曼树!
把每个初始归并段的长度(块数 \(l_i\))看作叶节点的权值,把该段参与归并的趟数看作叶节点到根的路径长度(深度 \(d_i\)),那么归并过程中被读写的总块数就是这棵树的带权路径长度(WPL): $\(\text{WPL} = \sum_{i=1}^{r} (l_i \times d_i)\)$ 因为每处理一块数据需要 读 1 次 \(+\) 写 1 次 \(= 2\) 次 I/O,所以: $\(\text{归并过程的总 I/O 次数} = 2 \times \text{WPL}\)$ $\((\text{若求整个外部排序的总 I/O 次数} = 2b + 2 \times \text{WPL})\)$
要想让 I/O 最少,就是要让 \(\text{WPL}\) 最小!这完完全全就是数据结构树那一章学的哈夫曼树(最优 \(k\) 叉树)!构造方法只有一句话:每次从当前剩下的段里,挑出长度最小的 \(k\) 个段合并成一个新段,直到只剩 1 个段为止。
5.3 核心必考杀手锏:虚段(Dummy Runs,长度为 \(0\) 的假段)
为什么要补“虚段”?(不补会出什么惨剧?)
在 \(2\) 叉哈夫曼树里,每次 \(2\) 个合 \(1\) 个,永远不会出现“不够合”的情况。但在 \(k\) 叉哈夫曼树(\(k \ge 3\)) 里,大概率会出现最后凑不满 \(k\) 个的尴尬局面!
举个血淋淋的例子:假设有 \(r = 8\) 个初始段,长度分别为 2, 3, 5, 7, 11, 13, 17, 19,做 \(k = 3\) 路归并。
- 如果直接硬合(不补虚段):
- 第 1 次合最小的 3 个:2 + 3 + 5 = 10(剩 6 个段:7, 10, 11, 13, 17, 19)
- 第 2 次合最小的 3 个:7 + 10 + 11 = 28(剩 4 个段:13, 17, 19, 28)
- 第 3 次合最小的 3 个:13 + 17 + 19 = 49(剩 2 个段:28, 49)
- 惨剧发生:第 4 次在树根处,只剩 28 和 49 两个段了!明明你有同时归并 \(3\) 路的能力,在最顶层(搬运数据量最大的地方!)却空置了 \(1\) 路,退化成了 \(2\) 路归并!这意味着原本可以在树根少走一层的重型节点,被迫往下沉了一层!
- 正确做法(在最底层补“长度为 0 的虚段”):
我们要保证树根处必须严丝合缝地凑满 \(k\) 个分支!既然总共差 \(1\) 个才够凑整,我们应该把这个“空缺名额”放到最底层(权值最小的地方)去消化——即在开始构建哈夫曼树之前,人为补上 \(1\) 个长度为 \(0\) 的虚段!
- 加上虚段 0 后,共有 \(9\) 个段:0, 2, 3, 5, 7, 11, 13, 17, 19。
- 第 1 次合最小的 3 个:0 + 2 + 3 = 5(虚段 0 不占任何磁盘块,读它写它消耗 \(0\) 次 I/O,相当于只把 2 和 3 二路合并了,把“不满 3 路”的损失限制在了最轻量级的 2 和 3 身上!)。
- 后续每次合并都完美凑满 3 路,树根也是满打满算的 3 路!
虚段个数的严格数学推导与秒杀公式(背熟!)
怎么一眼算出到底要不要补虚段、该补几个? 底层数学逻辑: - 在一棵所有内部节点都严格分满 \(k\) 个叉的正则 \(k\) 叉树中: - 每做一次 \(k\) 路合并,就把 \(k\) 个段合成 \(1\) 个新段,总段数净减少 \(k - 1\) 个。 - 假设一共经历了 \(m\) 次合并,最终变成了 \(1\) 个根,那么初始段数(含虚段)\(r'\) 必然满足: \(r' - m(k - 1) = 1 \implies r' - 1 = m(k - 1)\) 也就是说,(总叶子数 \(- 1\))必须能被 \((k - 1)\) 整除!
考场秒杀公式: 给定实际初始归并段个数 \(r\),归并路数 \(k\),先计算余数 \(u\): $\(u = (r - 1) \bmod (k - 1)\)$ 1. 若 \(u = 0\):说明 \((r - 1)\) 刚好是 \((k - 1)\) 的整数倍,棵棵分支全满,不需要补虚段(补 \(0\) 个)! 2. 若 \(u \ne 0\):说明最后一次合并时只剩了 \(u + 1\) 个段,还差几个才满 \(k\) 个?需要补充的长度为 \(0\) 的虚段个数为: \(\text{需补虚段数} = (k - 1) - u\)
验算练习: * 刚才的例子:\(r = 8, k = 3\)。 计算 \(u = (8 - 1) \bmod (3 - 1) = 7 \bmod 2 = 1 \ne 0\)。 需补虚段数 \(= (3 - 1) - 1 = \mathbf{1}\) 个! * 若 \(r = 10, k = 4\): 计算 \(u = (10 - 1) \bmod (4 - 1) = 9 \bmod 3 = 0\)。 需补虚段数 \(= \mathbf{0}\) 个! * 若 \(r = 11, k = 4\): 计算 \(u = (11 - 1) \bmod (4 - 1) = 10 \bmod 3 = 1 \ne 0\)。 需补虚段数 \(= (4 - 1) - 1 = \mathbf{2}\) 个!
5.4 最佳归并树完整真题演练(手把手带你拿满分)
题目:设外存上有 \(8\) 个初始归并段,其记录长(磁盘块数)依次为:5, 12, 16, 20, 23, 28, 30, 45。现采用 \(3\) 路平衡归并,请画出最佳归并树,并计算归并过程中的总读写(I/O)次数。
满分作答步骤:
1. 第 1 步:算虚段
已知 \(r = 8, k = 3\)。
\(u = (8 - 1) \bmod (3 - 1) = 7 \bmod 2 = 1 \ne 0\)
需添加虚段个数 \(= (3 - 1) - 1 = 1\) 个(权值为 \(0\))。
当前待合并集合(共 \(9\) 个):{0, 5, 12, 16, 20, 23, 28, 30, 45}。
2. 第 2 步:每次选最小的 \(3\) 个合并(建 3 叉哈夫曼树)
- 第 1 次合并:挑最小的 0, 5, 12 \(\to\) 合成新节点 17。
剩余集合:{16, 17, 20, 23, 28, 30, 45}。
- 第 2 次合并:挑最小的 16, 17, 20 \(\to\) 合成新节点 53。
剩余集合:{23, 28, 30, 45, 53}。
- 第 3 次合并:挑最小的 23, 28, 30 \(\to\) 合成新节点 81。
剩余集合:{45, 53, 81}。
- 第 4 次合并(树根):把最后剩下的 45, 53, 81 \(\to\) 合成最终根节点 179!
3. 第 3 步:画树看深度,算 WPL
[ 179 ] <-- 深度 0(根)
/ | \
(81) (53) [45] <-- 深度 1([45]在此层)
/ | \ / | \
[23][28][30] [16](17)[20] <-- 深度 2([23,28,30,16,20]在此层)
/ | \
[0][5][12] <-- 深度 3([0,5,12]在此层)
- 方法 A(按叶节点 \(\sum l_i \times d_i\) 算):
- 深度为 \(1\) 的叶子:
45 - 深度为 \(2\) 的叶子:
23, 28, 30, 16, 20 - 深度为 \(3\) 的叶子:
0, 5, 12\(\text{WPL} = 45 \times 1 + (23 + 28 + 30 + 16 + 20) \times 2 + (0 + 5 + 12) \times 3 = 45 + 234 + 51 = 330\)
- 深度为 \(1\) 的叶子:
- 方法 B(考场验算神技:所有非叶内部节点的权值之和!):
每次合并生成的中间节点分别是
17、53、81、179,把它们直接加起来: \(\text{WPL} = 17 + 53 + 81 + 179 = 330\) (两种算法结果分毫不差,考场上强烈建议用方法 A 加上方法 B 双重验算,绝对不会算错!) - 第 4 步:算总 I/O 次数 \(\text{归并过程总 I/O 次数} = 2 \times \text{WPL} = 2 \times 330 = \mathbf{660}\text{ 次}\)
第 6 章:深度排雷与灵魂答疑(防掉坑指南)
6.1 经典拷问:“如果某一摞全是极小的数字,被瞬间拿空,会不会导致频繁等 I/O?”
这个问题必须分两个层次回答,才能看出你是真正学通了还是只背了皮毛:
- 第一层(算总 I/O 次数账):总 I/O 次数绝对不变!
因为磁盘读写是按“块”通过缓冲区进行的。就算第 1 摞全是全场最小的数字(比如
1, 2, 3...),CPU 也是先把第 1 摞的第 1 块读进输入缓冲区,在内存里飞快地拿完这一整块、塞满输出缓冲区写出一块后,再去读第 1 摞的第 2 块。整趟下来,每一块依然是严格读 1 次、写 1 次,总 I/O 次数依然死死等于 \(2b\),不会多出哪怕 1 次磁盘读写。 - 第二层(算双缓冲并行效率账):会导致“并行退化为串行”,CPU 频繁被迫停工等待! 在高级的双缓冲并行归并(\(2k\) 个输入缓冲区)中,我们的理想状态是:CPU 在消耗这 \(k\) 路的当前缓冲块时,磁盘正在后台慢悠悠地把下一批要用的块预读进备用缓冲区。
- 如果数据分布均匀,每路消耗速度差不多,磁盘轮流预读即可;
- 但如果第 1 摞全是极小的数,第 1 摞的当前缓冲块和备用缓冲块会被瞬间连续抽干,而其他 \(k-1\) 路的缓冲区一张牌都没动!
- 此时如果系统傻乎乎地去预读第 2 摞的数据,第 1 摞就会断粮,导致 CPU 必须停下来干等第 1 摞的磁盘 I/O!
- 教材解决方案:为了实现真正的读写并行,外部排序会观察每一块最后一条记录的关键字大小,谁的末尾记录最小,说明哪一摞的缓冲块会最先耗尽,磁盘就优先去预读哪一摞的下一块!
6.2 审题生与死:408 考场最阴险的 3 个文字游戏
- 给的是“记录数”还是“磁盘块数”?
- 题干常写:“文件有 \(10000\) 条记录,每个磁盘块可存 \(100\) 条记录……”。
- 铁律:算 I/O 次数时,第一步必须先把记录数折算成总磁盘块数 \(b = \lceil 10000 / 100 \rceil = 100\) 块!拿记录数直接乘趟数算 I/O 的,统统零分!
- 问的是“归并 I/O”还是“外部排序总 I/O”?
- 只要问“外部排序的总读写次数”,必须加上生成初始归并段(第 0 趟)的 \(2b\)!
- 只有明确问“归并过程中的读写次数”或“建好初始归并段后的读写次数”,才不加那 \(2b\)。
- 败者树调整 vs 建树?
- \(k\) 路归并败者树,每输出一个元素后的单次调整比较次数为 \(\lceil \log_2 k \rceil\),与树中有多少条记录无关,只与归并路数 \(k\) 有关。
第 7 章:考场速查背诵卡(上考场前 5 分钟看这张表)
| 核心考点 | 终极公式 / 核心结论 | 必防暗坑 |
|---|---|---|
| 1. 初始归并段与趟数 | 初始段数 \(r\),归并路数 \(k\),归并趟数 \(S = \lceil \log_k r \rceil\) | \(k\) 的上限由内存可划分的缓冲区个数决定,不由 \(r\) 决定 |
| 2. 磁盘 I/O 总账 | \(\text{归并 I/O} = 2b \times S\) \(\text{外排总 I/O} = 2b \text{(初始段)} + 2b \times S = 2b(S + 1)\) |
\(b\) 是总磁盘块数(\(\text{总记录数} \div \text{每块记录数}\));看清含不含初始段 |
| 3. 缓冲区配置 | 基础串行需 \(k + 1\) 个(\(k\) 入 \(1\) 出) 读写并行需 \(2k + 2\) 个(\(2k\) 入 \(2\) 出) |
并行归并时需预测哪个输入缓冲最先空(比每块末尾关键字) |
| 4. 败者树 | \(k\) 个叶子 b[0..k-1] 存排头记录;\(k-1\) 个内节点 ls[1..k-1] 存败者段号;ls[0] 存总冠军段号。单次调整比较次数 \(= \lceil \log_2 k \rceil\) |
败者留守父节点,胜者向上挑战;调整时只和父节点比(每层 1 次),不看兄弟节点;使内部归并总比较次数 \(O(N \log_2 r)\) 与 \(k\) 无关 |
| 5. 置换-选择排序 | 工作区容量 \(m\),底层用容量为 \(m\) 的败者树实现。 段长范围:最大 \(n\)(正序),前段最小 \(m\)(逆序),随机期望 \(2m\) |
新数 \(<\) 刚输出数则段号 \(+1\)(打标记冻结); 最后一个归并段的长度可能 \(< m\) |
| 6. 最佳归并树与虚段 | 本质是 \(k\) 叉哈夫曼树。先算 \(u = (r - 1) \bmod (k - 1)\): • 若 \(u = 0\),补 \(0\) 个虚段; • 若 \(u \ne 0\),补 \((k - 1) - u\) 个权值为 \(0\) 的虚段。 每次挑最小的 \(k\) 个段合并,\(\text{归并总 I/O} = 2 \times \text{WPL}\) |
模的是 \(k - 1\) 绝不是 \(k\)! 虚段必须放在最开始和权值最小的实段一起合并; \(\text{WPL}\) 等于所有叶子的 \(\sum(l_i \times d_i)\),也等于所有非叶内部节点权值之和 |