外部排序相关

外部排序 由于数据元素太多,无法一次全部读入内存进行内部排序,这是就要通过外部排序来解决 1.外排原理 目的:通过内存的读写操作(每次读写操作都是成块的进行,比如每次1KB),将存放于磁盘中的大量数据变得有序。 (拿二路归并举例) 如图,对于在磁盘中分块存放的数据,每块存入三个元素,共16块 在内存中建立三个缓冲区输出缓冲区、输入缓冲区1以及输入缓冲区2 1.1构造初始归并段 首先,依次地读入前两块数据,分别存入内存中的 缓冲区1、缓冲区2 将输入缓冲区1以及输入缓冲区2中存放的数据经过 内存中的二路归并排序(内排)后,将生成的有序的块经 输出缓冲区 写入磁盘 得到一个有序的归并段 同样的,对剩余块进行同样的操作可以得到 1.2以归并段为单位进行归并 分别选取归并段1和2中较小的一块,依次读入至缓冲区1,2 内排之后,写入内存,注意,输入缓冲区1(或2)空缺后要立即在归并段1(或2)中读入新的块到其中进行归并排序 (以保证输出缓冲区始终输出归并段中较小的元素) 最终,完成所有归并段的第一趟归并之后,会有 之后,4块成一个归并段,两两归并 …… 最终。经过3趟归并,整体会变得有序! 2.优化思路 2.1时间开销分析 在整个排序过程中,时间开销分析如下 可以看到, 外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间 而读写外存时间是关键的时间开销,因此优化应该针对怎么减少读写外存的次数展开 而文件总块数无法优化,只能针对归并的趟数优化 为此,我们需要采用多路归并来解决 2.3结论 2.4 优化思路一:采用多路归并 对上面的例子,如果采用四路归并 只需96次读写即可!! 2.5 优化思路二:减少初始归并段数量r 败者树 归并段数增加之后,内存中缓冲区数目增加,从中对比得出最小关键字的对比次数也会随之增多…… 1.算法思想 构造 如图所示的树结构,叶节点对应(脑补)各归并段(假设共有8个归并段),分支结点记录败者来自哪个归并段,最后根节点记录冠军来自哪个归并段,并且将冠军输出,为这8个归并段中的最小值。 下轮选择冠军记录的那个归并段(归并段3)中的元素6,代替1的位置,如图,并依次向上的与各败者结点对比,胜则往上,败则留下,最终输出冠军 接下来,循环这个过程 2.效率分析 对于k路归并,第一次构造败者树需要对比关键字k-1次 有了败者树,选出最小元素,只需对比关键字次$\left \lceil \log_2k \right \rceil$...

Jun 10, 2021 · 1 min · Archai