当数据放不进内存
比较次数不足以描述大型文件的排序成本:数据还要从存储设备按块读入,再把结果写回。顺序传输往往比大量零散访问便宜;不过,要计算传输量,必须先讲清楚每次传输的大小,以及每轮之间保存什么。
定义 20.1.1
(块传输模型)
固定的有限输入文件有 条记录,恰好占 个块,每个块含 条记录。一次块传输是读或写一个完整块。工作内存容纳 个记录位置,其中 。键有全序,记录的原始次序明确。算法在此模型中的成本是其块传输次数。
每个输入归并段的小型描述符与计数器另计。我们计数的是块传输,不是实际时间、比较、磁盘寻道或描述符的传输。块是计算单位,并不表示所有存储设备的延迟相同。
定义 20.1.2
(归并段)
归并段是存储为连续完整块的一段有序记录。
以下构造使每段恰好含整数个完整块。若实际最后一块未满,可以填充并记下有效记录数;填充值绝不能当成数据。
产生归并段并逐轮合并
令 ,。由 得 、。
- 每次读取至多 个块,在内存中稳定排序后写成一个归并段,直到读完 个块。稳定的合并排序可以使用同样大小的辅助数组,所需记录位置不超过 。因此最初有 个归并段,按原始数据块的次序排列。
- 每一轮合并,把相邻归并段分组,每组至多 段。每个输入预留一个块缓冲区,另预留一个输出缓冲区。反复选出各段当前首项中的最小键并输出;某个输入缓冲区用完时才读入下一块,输出缓冲区满时就写出。键相同时先取较早的输入段;同一段内保持原有次序。每组写成一个新的归并段。按本算法,即使某组只有一段也要复制。
- 对上一轮的完整输出重复合并,直到只剩一段。若 ,不需要合并轮。每轮完成之前,须保留足够的存储空间容纳输入和输出。
缓冲区共需至多 个记录位置。保存至多 个首项的堆或败者树另需 个描述符,未计入 。若实现受严格的字节预算限制,应先预留描述符空间,再重新计算扇入数。此外,已耗尽的归并段须有独立的状态,不能用一个合法的最大键冒充结束标记。
常见错误
(把全部内存都用作输入缓冲区)
人们很容易想一次合并 个归并段。这些输入缓冲区加一个输出缓冲区共需 个位置;由下取整的定义,,所以总是超出内存。例如 、 时,四个输入缓冲区加一个输出缓冲区需要 个位置。扇入数 明确保留了一个输出块。
定理 20.1.3
(正确性与稳定性)
在上述假设及算法下,产生的每个归并段都是输入中某个连续区间的稳定有序排列,而最终归并段是整个输入的稳定有序排列。
证明
(对合并轮归纳)
初始归并段是相邻输入片段的稳定有序排列,并按原始片段的次序排列。考虑一个合并组,其输入段都是原始连续区间的稳定有序排列,并按这些区间的次序列出。每段尚未取出的元素都不小于该段当前首项,因此所有首项中最小者也是整组剩余元素中的最小者。逐个输出就得到有序排列,且每条记录恰好输出一次。至于稳定性,取两条键相等的记录。若它们来自同一段,该段的次序得以保留,而那本来就是原始次序。若来自不同段,由于各段按次序覆盖连续区间,较早段的记录原本在另一条之前;平局规则正是先输出较早的段。相邻归并段对应相邻的原始位置区间,合并后仍然如此;由归纳法,每轮及最终结果都具有上述性质。
归纳携带的不只是有序性,而平局规则需要的正是这部分额外信息。
证明透视
局部的相等键规则为何保持整体次序
有序性本身在合并下封闭,稳定性却不然:它需要知道每条记录来自何处。因此证明携带一个更强的不变量:每段都是原始位置某个连续区间的稳定有序副本,并且各段按区间次序排列。关键一步只用这个不变量一次:同组不同段中键相等时,较早段的所有记录原本都在较后段之前,所以纯粹局部的规则“先取较早的输入段”就保持了整体的原始次序。最小首项的论证只用到每段有序;稳定性的论证则用到每组由按次序排列的相邻段组成。若把不相邻的段分在同一组,仍然保持有序,却可能破坏稳定性。
定理 20.1.4
(轮数与传输量)
令 ,包括 时的 。产生初始归并段及所有合并轮共需恰好
次块传输。临时空间可以在轮与轮之间重用;这个数字包括写出最终归并段。
证明
(先数段,再数块)
若某轮开始时有 段,完成后有 段。反复向上取整后,第 轮之后的段数是 :两者都是使 的最小整数 。所以首次只剩一段所需的轮数正是 。产生初始归并段时,每个输入块读一次、写一次。每个合并轮也恰好读一次每个输入块并写一次每个输出块;各组都由整块组成,没有舍弃记录,故输出仍有 块。把初始的 次和之后 轮各 次相加,即得公式。这是指定算法的精确计数,并不是所有排序算法都必须达到的下界。
概念视角组合
把各轮看成归并树的层
把每个初始归并段画成一片叶子,把每个合并组画成一个节点,其子节点就是它所消耗的归并段。第 轮就是一棵有根树的第 层:每个节点至多有 个子节点,第 层有 个节点,根位于高度 。由于只含一个归并段的组也要复制,每片叶子的深度都恰为 。每一层把全部 个块重写一次,所以各合并轮共需 次传输:轮数正是这棵树的高度。
常见错误
(漏计产生归并段的一轮)
计数是 ,而不是 :任何合并开始之前,产生归并段已把每个块读写一次。对下面的六块例子,,而算法实际进行 次传输。当 时合并项为零,但排序仍需 次传输。
例题 20.1.5
(三个归并段,一轮合并)
取 、,十二个输入键依次为
此时 、、、。稳定排序三段得到 、 和 。一次三路合并产生 。第一个 5 来自较早的第一段,因此排在第三段的 5 之前。初始轮读六块、写六块,合并轮同样如此,共 24 次传输。若最终的有序数据直接以流的形式交给下游而不写出,输出约定及计数就不同。
轮数只随段数按对数增长,但每轮都要完整读写一次。
例题 20.1.6
(十个归并段,三轮合并)
取 、、。同样 、,故 ,即九段各两块、一段一块。第一轮合并把归并段分成 四组,产生四段;按算法,单段组也要复制。下一轮分成 两组,产生两段,第三轮产生一段。段数依次为 ,所以 ,因为 。算法共传输 次。
另一个极端是完全不需要合并。
例题 20.1.7
(一段即可容纳的文件)
取 、、。此时 ,整个文件作为同一个片段读入、稳定排序后写出:、。产生归并段读两块、写两块,共 次传输。公式仍计入写出最终归并段,这是输出约定的一部分。
反例模式
每段已排序不代表整个文件已排序
断言:只要每段都已排序,把各段依次写出就得到有序文件。把 与 直接连接,所得次序中 8 在 2 之前,故并未排序。相等键时随意选一段也不一定稳定:若较早段含 、较后段含 ,先输出 就颠倒了原始次序。正确性需要最小首项合并,稳定性需要先取较早段的平局规则,两者须分别论证。
如何解读界限
用二叉堆选取首项,每输出一条记录需 的选取工作,全部合并的比较工作为 ;内存中稳定的初始排序则需 次比较。不同设备上的块传输时间可以相差很大,所以传输量本身不是运行时间的实测。压缩、变长记录、并行磁盘、异步预取、操作系统缓存及故障都不在模型之内。增加扇入数可能减少轮数,却增加缓冲区与描述符的压力。失败后重试还需要独立的原子输出与恢复约定;不能把未完成的输出当成已完成的归并段。
练习与解答
快速检查
(两个有序段的键为 和 ,第一段在原文件中较早。写出稳定合并的结果。)
每当当前首项相等时,应用平局规则。
解答 · 答案
键为 ;第一段的两个 4 要按原次序排在第二段的 4 之前。
快速检查
(设 、、。求 、、、 及块传输次数。)
由定义计算 和 ,再反复向上取整相除。
解答 · 答案
,,故 。由于 ,;段数依次为 。算法共传输 次。
快速检查
(设 、。使至多一轮合并就足够的最小整数 是多少?)
恰在 时一轮就足够。
解答 · 答案
需要 ,其中 、。 时 、、。 时 、、。 时 、、。 时 、、,故 。答案是 ,共 次传输。