article20201129
大数据 | 大数据基础--算法之外存模型算法：外存排序
亲爱的读者朋友大家晚上好，上次我们简单介绍了外存模型以及一些基本问题，这次我们来介绍外存模型下的排序算法。
外存模型
到目前为止，按照存储模型，我们学过的算法模型应该分为两种：一种是\(RAM\)模型，也就是我们常用的算法的设计模型，另一种是\(I/O\)模型，内存比数据量小，外存是无限的。
外存访问与内存访问有一些差异：
- 与外存相比，内存的速度更快
- 外存的连续访问比随机访问代价小，也就是说：以块\((block)\)为单位访问，而不是\(elemen\ wise\)
在\(I/O\)模型中，内存的大小为\(M\)，页面大小为\(B\)，外存大小无限，页面大小为\(B\)。
外存排序问题
考虑外存排序算法的时候要与外存模型紧密地结合起来。
算法
- 给定\(N\)个数据，将其分成大小为\(O(M)\)的组
- 每一组数据可以在内存排序
- 将每一组数据从外存读进来需要\(O(M/B)\)次\(I/O\)
- 对所有分组进行以上操作，于是每个分组内部都是已经排好序的数据
- 对这些排好序的分组进行多路归并排序
- 每次可以归并\(O(M/B)\)个分组
过程解释
首先需要明白的一点是从外存向内存转移数据的时候，一次只能转移\(B\)的数据量。于是，要想一次把内存读慢，相应的\(I/O\)次数就是\(O(M/B)\)。另外进行多路归并排序时，至多可以归并多少分组。从每个分组读出来一个页面，然后进行排序，所以这里跟每个分组的大小没有关系，只跟内存的大小有关，所以是\(O(M/B)\)。
图示
评价
我们来对上述算法的\(I/O\)代价进行简单的分析：首先时间复杂度分为两个部分，一个是分组内排序，另一个是分组间归并排序。对于分组内排序，只需要将每个分组的数据读入内存即可，这部分对应的时间复杂度为\(O(N/B)\)。对于归并排序，相应的时间代价应该是每一趟归并的开销之和，而每一趟归并都需要把所有数据都导入到内存中一次，这个时间代价为\(O(N/B)\)，因此我们只需要计算处进行归并的趟数即可。如图所示，归并的趟数可以表示为\(O(log_{M/B}\frac{N}{B})\)。综上所述：总的时间开销为：\(O(N/B \cdot log_{M/B}\frac{N}{B})\)。
总结
以上就是关于外村模型下对数据进行排序问题的解决方案。下次我们会对\(list\ ranking\)算法进行分析，敬请期待~