Python|外部排序的次数与时间的相关算法

前言

在上一次的文章中介绍了外部排序的定义以及基础实现过程，本文章是对外部排序的次数与时间的相关算法，算法逻辑性较强，需要细致的分析与理解。才能更好的掌握。

问题描述

列如：假设有一个100KB记录的磁盘文件，而当前使用的计算机一次只能对10KB记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并。假设“数据块”的大小为10，即每一次访问外存可以读/写10个记录。则对于100个记录，处理一遍需访问外存20次(读和写各10次)。

解决方案

3.1外部排序的次数计算，由读/写规律可得：

1）10个初始归并段需访问外存20次；

2）每进行一趟归并需访问外存20次；

3）总计访问外存 20 + 4*20 =100次。

3.2外部排序时间的计算：

公式:

外部排序总时间t = 产生初始归并段的时间m*t1+外存信息读写时间d*t2+ 内部归并所需时间s*ut3

其中：

m=待排序序列含m个初始归并段

d=外存的次数

s=归并趟[(s取大于对数的最小整数)

u=计算机一次对多少个记录进行内部排序

特别:在外部排序中t2取决于外存，远远大于t1和t3，外部排序的时间取决于读写外存的次数d。

3.3举例:

若对上述例子采用2路归并,则只需进行4趟归并。

则:外排所需总的时间t = 10*t1 + 100*t2 + 4*10*t3

结语

本文是对外部排序次数与时间相关算法的讲解，一般情况下，假设待排记录序列含 m 个初始归并段，外排时采用 k路归并，则归并趟数s=],显然，随着k的增大或m的减小，归并的趟数将减少，因此对外排而言，通常采用多路归并。k 的大小可选，但需综合考虑各种因素。

实习编辑：衡辉

稿件来源：深度学习与文旅应用实验室（DLETA）