15 External Sorting¶
为什么我们不能在硬盘上完成快速排序？
这是因为在硬盘中我们访问一个数据 a[i] ，需要
- find the track
- find the sector
- find a[i] and transmit
我们并不能做到像 internal memory 那样快速地随机读取数据，我们希望读取的数据时连成一片的，这样我们就可以减少前面的寻道时间了。
这时候 Merge-sort 的方法就满足我们的条件，为简单起见，我们假设
- Store data on tapes (can only be accessed sequentially)
- Can use at least 3 tape drives
Example
Suppose that the internal memory can handle M = 3 records at a time.
图中 \(T_1\) 是一条 tape 的编号，我们可以理解为一个序列的物理地址，或更通俗的来说，可以当作一个数组，只不过它的实际数据是在硬盘中。换句话来说，这里的 tape 表示的都是硬盘中的数据。
这条 tape 中有 13 个元素，我们记其为 \(N = 13\)。而这条原始的 tape 被划分为了 5 段，每一段都有不超过 3 个元素，此时 \(M = 3\)。即有 \(\lceil \frac{N}{M} \rceil = 5\)。
在第一轮中，面对全部都是无序的数据，我们将这 \(\lceil \frac{N}{M} \rceil = 5\) 个段均分到两条 tape 上（2-way），这里经历两个步骤：
- 依次读取 \(T_1\) 中每一段数据（刚好占满内存），并对它们进行内排序；
- 将排序完的段，追加写到 \(T_2\) 或 \(T_3\) 中（具体每一个 tape 写几条，会有专门策略做调整，目前先平分着放）；
于是，\(T_1\) 中的数据便被转移到了 \(T_2\) 和 \(T_3\)。为了重复利用 tape，此时的 \(T_1\) 被看作可以用的空磁盘了。
之后的 pass 则基本遵循同样的规则，不断取每一路的第一个 run 并 merge，并且将结果写到两个（k 个）闲置的 tape 上（和前面说过的一样，这里暂且将分配策略定为平分到每一个 tape 上）。
例如，我们要取 \(T_2\) 和 \(T_3\) 的第一段，执行归并操作，得到一个新的，有 6 个数据的 run，并写到闲置的 \(T_1\) 上；接下来取 \(T_2\) 和 \(T_3\) 的第二段，归并得到新的 run，此时我们发现，\(T_1\)、\(T_2\)、\(T_3\) 都不是闲置的，所以我们需要一个新的 tape，写到 \(T_4\) 上。
pass 3 和 pass 2 的过程基本一致。现在的 tape 状态是 \(\{T_2, T_3\}\) 闲置，我们取 \(T_1\) 和 \(T_4\) 的第一段，得到一个新的 run，包含 12 个元素；取 \(T_1\) 和 \(T_4\) 的第二段，得到一个新的 run，包含 1 个元素。这两段被分配到两条空闲 tape 上，即 \(T_2\) 和 \(T_3\)。
最终得到结果
在上述例子中，我们进行了四次 pass, 那么对于一般的情况，N个数据，internal memory 最多可处理 M 个数据的时候，则需要 \(1+\lceil \log _2(N/M)\rceil\)
于是我们可以考虑的优化空间
- 一个 pass 意味着若干次 seek，所以减少 pass 可以是一个方向；
- merge 的过程中会多次读取 tape 中的数据，而对于计算机来说单次大量读取比多次小量读取更高效，如何优化数据读取也是一个方向；
- 如何更高效的在 \(k\)-way merge 过程中，归并 M 个分别来自 k 个序列的数据，即内排序的策略，也上优化的一个方向；
- 读入、内排序、输出，这三个事务目前是停机串行的，考虑将其并行化也是一个方向；
# Pass 优化¶
我们之前使用的是 2-way merge，现在考虑使用 k-way merge，也就是说每次merge的时候选择 k 个 run 一起
Note
这个 merge 的过程我们可以使用堆来处理，更新一个 k-minheap，因为我们每次都要取 k 个数中的最小值
每一次 run 的数量变为原来的 1/k ，所以 pass 的数量为
但是这种方法会带来另一个问题就是 tapes 的数量需要 2k 个（k个负责输入，k个负责输出）而这并不利于我通过增加 k 来减少 pass 的数量，因而我们考虑某种策略来优化 tape 的使用。
# Tape 优化¶
Can we use 3 tapes for a 2-way merge
我们在第二次 pass 的时候只能将所有的 run 放在同一个 tape 上
这样导致的问题就是我们要进行下一次归并的时候，需要来回取数据，而这时不允许的，那么我只能将部分数据copy到另一个盘上才能继续进行操作
而这样造成的开销是巨大的
我们可以考虑，不平均的将归并后的 run 分配到各个 tape 上，即总有一些 tape 比别的 tape 多一些 run。虽然在平分的策略中，也有可能会有多出来的 run，但是只会多一个（也就是将 \(x \text{ mod }k\) 的余数分配到其中几个 tape 上）。此时这些多出来的 run 可能就是单纯的从一个 tape 别复制到另外一个 tape 上，看起来是个非常没必要的操作，为什么不直接留下它，将当前 tape 拿到下一轮用呢？
但是由于平分策略下，这个情况的出现并不可控，而且总是会引起悬殊的 tape 间的数量差，所以我们考虑能不能主动利用这个性质。
我们按照 Fibonacci 数列的项来分配每个 tape 的 \(\# run\)，此时每一个 pass 只需要一个有一个空闲的 tape 即可。
Example
假设我们现在有两个 tape，分别有 23 个 run 和 13 个 run，则：
| \(T_1\) | \(T_2\) | \(T_3\) | 说明 |
|---|---|---|---|
| 21 | 13 | - | 初始情况 |
| 8 | - | 13 | \(T_1\) 的前 13 个与 \(T_2\) 归并，结果写入 \(T_3\) |
| - | 8 | 5 | \(T_3\) 的前 8 个与 \(T_1\) 归并，结果写入 \(T_2\) |
| 5 | 3 | - | 略 |
| 2 | - | 3 | 略 |
| - | 2 | 1 | 略 |
| 1 | 1 | - | 略 |
| 0 | - | 1 | 略 |
使用 Fibonacci 我们总可以滚动着将 \(\#run\) 的规模缩小。
k-way merge with k-order Fibonacci Sequence
对于 \(k\)-way merge，我们只需要构造 k 阶 Fibonacci 数列，然后按照这个数列来分配每个 tape 的 \(\#run\) 即可。
k-order Fibonacci Sequence
给出 k 阶 Fibonacci 数列（与 PPT 略有不同，主要体现在下标从谁开始，无伤大雅）：
这个结论看起来很自然，但是实际上是怎么操作的呢？PPT 压根没讲，因此，我在询问 ch 老师以后，写下了这个部分，旨在补充 \(k\)-way merge 使用 k 阶 Fibonacci 优化的方法。
首先，做一些强调：
- 该方法陈述过程中，k 路始终直接合并成一路（千万不要用“iterative”的思路来考虑，就算 iterative，迭代完了也还是 k 路归为 1 路）；
- 我们的目的是优化每一个 pass 中每个 tape 的 \(\#run\) 不一样带来的性能问题（例如尴尬的 \(n\) 和 \(n+1\) 归，下一个 pass 就得 \(1\) 和 \(n\) 归了）；
对于第 \(i\) 个 pass，有 \(k\) 个 tape，我们记每一个 tape 的 \(\#run\) 为 \(r_i\)，则有：
- \(\max\{r_i\} = F^k_j\);
- \(\min\{r_i\} = F^k_{j-1}\);
也就是说，每个 pass 最大和最小的 \(\#run\) 分别有 k 阶 Fibonacci 中相邻的两项。
这里分开用 i 和 j 是想表达这个匹配关系不重要，重要的是最大值最小值由 Fibonacci 相邻项所确定。
那么夹在最大和最小的中间的其他 \(\#run\) 要如何确定呢？首先我们进行一段推导：
假设 \(\{r_i\}\) 经过排序，并且刚好能凑上我们所需要的数量，有：
在这一个 pass 中，我们将所有 tape 的前 \(r_1\) 个 run 拿出来 merge，这样，除了 \(r_1\) 这个 tape，其他 tape 的 \(\#run\) 都变为 \(r_i-r_1\)。此时有不等关系：
这里唯一需要说明的就是 \(r_1 > r_k - r_1\)：
proof of the relation
如果我们将现在这个排序后的数列记为 \(\{r_i'\}\)，则有：
此时根据我们关于最大最小值的陈述，又有：
于是可以推得：\(r_2 = r_1 + F^k_{j-2} = F^k_{j-1} + F^k_{j-2}\)。关于 \(r_3, r_4\)，也是一样的办法，将 \(r_2\) 的结论迁移到 \(r_2'\)，再回过头得到 \(r_3 = r_1 + r_2'= F^k_{j-1} + F^k_{j-2} + F^k_{j-3}\)，以此类推，可以得到最终结论：
当然，刚好能凑上 Fibonacci 的情况自然是少数，对于无法凑上 Fibonacci 的情况，我们可以在后面补充上正无穷的项以达到斐波那契项的情况
并行优化¶
这里并行的目标主要是使算法支持数据的读-用-写的流水线，也就是说我们要想办法让读不阻塞用，用不阻塞写。
Example
Sort a file containing 3250 records, using a computer with an internal memory capable of sorting at most 750 records. The input file has a block length of 250 records.
这里大体上与前面的例子相近，只是每一个格子中不再是一个数，而是一个block
我们将 Internal memory 分为两部分，一部分是 input buffers, 还有一部分为 output buffer
将 T2 和 T3 的第一个block读入 input buffer
对 input buffers 中的两个 block 进行归并，直到 output buffer 满了
这时候我们就要将 output buffer 中的内容写到 T1 中去，并且在这个期间我们归并的操作需要停止
于是我们考虑增加一个 output buffer，这样我们在归并满一个buffer后，我们可以继续归并。但是这样我们还有一个问题，就是当其中一个 input buffer 消耗完的时候，我们还需要等待读取下一个buffer，所以我们还需要增加2个 input buffer（因为我们不知道哪一个先耗完，所以我们一开始都要读进来），扩展到 \(k\) 的情况，我们就需要 \(2k\) 个 input buffer 以及 2 output buffer
但是，并行优化的缺点就是占据了更多的内存空间——原先 \(k+1\) 个 buffer 平分的用于处理数据的内存，现在需要被 \(2k+2\) 个 buffer 平分，所以每一个 buffer 的大小会变小。进而导致每一次从 disk 中读取的数据变少，所以要读完数据所需要的读取次数就增加，即 seek 次数增加。
Beyond a certain k value, the I\O time would actually increase despite the decrease in the number of passes being made. The optimal value for k clearly depends on disk parameters and the amount of internal memory available for buffers. 我们需要取一个合适的k
怎样得到一个更长的run？¶
我们采取一个 replacement selection 的策略
Example
构建一个M大小的MinHeap
输出11，加入96，发现比11大，可在run1中
输出81，加入12，发现比81小，说明12不可能在run1中出现了
输出94，加入35，发现比94小，说明也不可能在run1中出现了
输出96，加入17，说明17也不可能在run1中出现了，至此堆中所有元素不可能在run1中出现，开始构建run2
我们可以利用这种方法让 length of run 的均值变成原来的两倍。当原来的输入是比较有序的时候，这个方法会得到非常长的run。
如何减小归并的时间？¶
Suppose we have 4 runs of length 2, 4, 5, and 15, respectively.
How can we arrange the merging to obtain minimum merge times?
数量比较小的情况下归并的速度更快，我们希望让较小的run先归并，这样自然而然引出 Huffman Tree
这样我们归并的总时间为 \(O(\text{the weighted external path length})\)
Quote
参考了以下学长的笔记
1.https://note.howjul.com/ADS/15.%20External%20Sorting/#1 2.https://note.isshikih.top/cour_note/D2CX_AdvancedDataStructure/Lec15/#tape-%E6%95%B0%E9%87%8F%E5%88%86%E6%9E%90%E4%B8%8E%E4%BC%98%E5%8C%96
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！