外排序 External sorting
2024-04-06 18:46:58
2019-04-17 18:11:34
外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。尔后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。
外排序的一个例子是外归并排序（External merge sort），它读入一些能放在内存内的数据量，在内存中排序后输出为一个顺串（即是内部数据有序的临时文件），处理完所有的数据后再进行归并。
比如，要对900 MB的数据进行排序，但机器上只有100 MB的可用内存时，外归并排序按如下方法操作：
- 读入100 MB的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。
- 将排序完成的数据写入磁盘。
- 重复步骤1和2直到所有的数据都存入了不同的100 MB的块（临时文件）中。在这个例子中，有900 MB数据，单个临时文件大小为100 MB，所以会产生9个临时文件。
- 读入每个临时文件（顺串）的前10 MB（ = 100 MB / (9块 + 1)）的数据放入内存中的输入缓冲区，最后的10 MB作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得更好的效果。）
- 执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写出至目标文件，清空缓冲区。一旦9个输入缓冲区中的一个变空，就从这个缓冲区关联的文件，读入下一个10M数据，除非这个文件已读完。
这是“外归并排序”能在主存外完成排序的关键步骤 -- 因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并)，每个大块不用完全载入主存。
最新文章
- 关于HIVE的数据模型介绍
- 柯里化/偏函数/Curring用法
- 使用GITHUB的体会
- keepalived的安装和使用
- aix5下安装python和cx_Oracle
- winform 加密 解密 分类： WinForm 2014-05-16 15:05 400人阅读 评论(0) 收藏
- RMAN传输表空间迁移数据
- 使用代码辅助生成工具CodeSmith -- 生成NHibernate的映射文件
- sqlplus连接oracle问题
- Delphi系列书籍pdf 118本 网友吐血整理
- x的x次幂的值为10，求x的近似值
- Python爬虫基础之Urllib
- python机器学习-sklearn挖掘乳腺癌细胞（四）
- [转]vs2010用 boost.python 编译c++类库 供python调用
- jqGrid API （转）
- listener does not currently know of 。。。。
- django-simple_tag、filter
- access database in a helper function ?
- python 面向对象 isinstance
- PHP秒杀系统全方位设计分析（二）