文档章节

外排序

Avner
 Avner
发布于 2017/08/17 13:59
字数 2010
阅读 7
收藏 0

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

外排序

方法介绍

所谓外排序,顾名思义,即是在内存外面的排序,因为当要处理的数据量很大,而不能一次装入内存时,此时只能放在读写较慢的外存储器(通常是硬盘)上。

外排序通常采用的是一种“排序-归并”的策略。

  • 在排序阶段,先读入能放在内存中的数据量,将其排序输出到一个临时文件,依此进行,将待排序数据组织为多个有序的临时文件;
  • 尔后在归并阶段将这些临时文件组合为一个大的有序文件,也即排序结果。

假定现在有20个数据的文件A:{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15},但一次只能使用仅装4个数据的内容,所以,我们可以每趟对4个数据进行排序,即5路归并,具体方法如下述步骤:

  • 我们先把“大”文件A,分割为a1,a2,a3,a4,a5等5个小文件,每个小文件4个数据

    • a1文件为:5 11 0 18
    • a2文件为:4 14 9 7
    • a3文件为:6 8 12 17
    • a4文件为:16 13 19 10
    • a5文件为:2 1 3 15
  • 然后依次对5个小文件分别进行排序

    • a1文件完成排序后:0 5 11 18
    • a2文件完成排序后:4 7 9 14
    • a3文件完成排序后:6 8 12 17
    • a4文件完成排序后:10 13 16 19
    • a5文件完成排序后:1 2 3 15
  • 最终多路归并,完成整个排序

    • 整个大文件A文件完成排序后:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

问题实例

1、给10^7个数据量的磁盘文件排序

输入:给定一个文件,里面最多含有n个不重复的正整数(也就是说可能含有少于n个不重复正整数),且其中每个数都小于等于n,n=10^7。 输出:得到按从小到大升序排列的包含所有输入的整数的列表。 条件:最多有大约1MB的内存空间可用,但磁盘空间足够。且要求运行时间在5分钟以下,10秒为最佳结果。

解法一 :位图方案

你可能会想到把磁盘文件进行归并排序,但题目要求你只有1MB的内存空间可用,所以,归并排序这个方法不行。

熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述,用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合,边框用如下字符串来表示集合{1,2,3,5,8,13}:

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

上述集合中各数对应的位置则置1,没有对应的数的位置则置0。

参考编程珠玑一书上的位图方案,针对我们的10^7个数据量的磁盘文件排序问题,我们可以这么考虑,由于每个7位十进制整数表示一个小于1000万的整数。我们可以使用一个具有1000万个位的字符串来表示这个文件,其中,当且仅当整数i在文件中存在时,第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性:

  1. 输入数据限制在相对较小的范围内,
  2. 数据没有重复,
  3. 其中的每条记录都是单一的整数,没有任何其它与之关联的数据。

所以,此问题用位图的方案分为以下三步进行解决:

  • 第一步,将所有的位都置为0,从而将集合初始化为空。
  • 第二步,通过读入文件中的每个整数来建立集合,将每个对应的位都置为1。
  • 第三步,检验每一位,如果该位为1,就输出对应的整数。

经过以上三步后,产生有序的输出文件。令n为位图向量中的位数(本例中为1000 0000),程序可以用伪代码表示如下:

//磁盘文件排序位图方案的伪代码  
//copyright@ Jon Bentley  
//July、updated,2011.05.29。  

//第一步,将所有的位都初始化为0  
for i ={0,....n}      
   bit[i]=0;  
//第二步,通过读入文件中的每个整数来建立集合,将每个对应的位都置为1。  
for each i in the input file     
   bit[i]=1;  

//第三步,检验每一位,如果该位为1,就输出对应的整数。  
for i={0...n}      
  if bit[i]==1        
    write i on the output file  

上述的位图方案,共需要扫描输入数据两次,具体执行步骤如下:

第一次,只处理1—4999999之间的数据,这些数都是小于5000000的,对这些数进行位图排序,只需要约5000000/8=625000Byte,也就是0.625M,排序后输出。 第二次,扫描输入文件时,只处理4999999-10000000的数据项,也只需要0.625M(可以使用第一次处理申请的内存)。 因此,总共也只需要0.625M 位图的的方法有必要强调一下,就是位图的适用范围为针对不重复的数据进行排序,若数据有重复,位图方案就不适用了。

不过很快,我们就将意识到,用此位图方法,严格说来还是不太行,空间消耗10^7/8还是大于1M(1M=1024*1024空间,小于10^7/8)。

既然如果用位图方案的话,我们需要约1.25MB(若每条记录是8位的正整数的话,则10000000/(1024 1024 8) ~= 1.2M)的空间,而现在只有1MB的可用存储空间,那么究竟该作何处理呢?

解法二 :多路归并

诚然,在面对本题时,还可以通过计算分析出可以用如2的位图法解决,但实际上,很多的时候,我们都面临着这样一个问题,文件太大,无法一次性放入内存中计算处理,那这个时候咋办呢?分而治之,大而化小,也就是把整个大文件分为若干大小的几块,然后分别对每一块进行排序,最后完成整个过程的排序。k趟算法可以在kn的时间开销内和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。

比如可分为2块(k=2,1趟反正占用的内存只有1.25/2M),1~4999999,和5000000~9999999。先遍历一趟,首先排序处理1~4999999之间的整数(用5000000/8=625000个字的存储空间来排序0~4999999之间的整数),然后再第二趟,对5000001~1000000之间的整数进行排序处理。

解法总结

1、关于本章中位图和多路归并两种方案的时间复杂度及空间复杂度的比较,如下:

        时间复杂度        空间复杂度

位图          O(N)          0.625M

多位归并   O(Nlogn)             1M

(多路归并,时间复杂度为O(k n/k logn/k ),严格来说,还要加上读写磁盘的时间,而此算法绝大部分时间也是浪费在这上面)

2、bit-map

适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下

基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码

扩展:bloom filter可以看做是对bit-map的扩展

举一反三

、已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。 8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。

本文转载自:http://taop.marchtea.com/06.04.html

上一篇: Hive Tips
下一篇: 文字-1
Avner
粉丝 9
博文 66
码字总数 56634
作品 0
杭州
程序员
私信 提问
加载中

评论(0)

数据结构(四十三)排序的基本概念与分类

  一、排序的基本概念   假设含有n个记录的序列为{r1,r2,...,rn},其相应的关键字分别为{k1,k2,...,kn},需确定1,2,...,n的一种排列p1,p2,...,pn,使其相应的关键字满足kp1≤kp2≤...≤k...

osc_5ncz8ucr
2018/07/11
4
0
外排序 败者树 多路归并

一、外排序 排序按数据存在的位置不同分为内排序和外排序 内排序:数据都在内存中,选择合适的排序方法对数据进行排序,比如选择排序、快速排序等 衡量内排序的效率是数据的比较次数 外排序:...

程红玲OOO
2017/02/12
0
0
java中Comparatable接口和Comparator接口的区别

1、不同类型的排序规则 .自然排序是什么? 自然排序是一种升序排序。对于不同的数据类型,升序规则不一样: BigDecimal BigInteger Byte Double Float Integer Long Short 类型,是按照数值的...

osc_ejw330h5
2018/09/21
2
0
设想有一个20GB的文件,每一行一个字符串。说明如何将这个文件进行排序。

设想有一个20GB的文件,每一行一个字符串。说明如何将这个文件进行排序。 思路1:外部排序,将部分数据载入内存。 将整个文件划分成许多块,每个块xMB,其中x是可用的内存大小。每个块各自进...

一贱书生
2016/11/24
42
0
多线程外排序解决大数据排序问题2(最小堆并行k路归并)

转自:AIfred 事实证明外排序的效率主要依赖于磁盘,归并阶段采用K路归并可以显著减少IO量,最小堆并行k路归并,效率倍增。 二路归并的思路会导致非常多冗余的磁盘访问,两组两组合并确定的是...

osc_sfkqtwox
2018/09/05
2
0

没有更多内容

加载失败,请刷新页面

加载更多

QT 执行shell命令

(1)首先包含头文件: #include <QProcess> (2)执行shell命令: QProcess::execute("ls");

悲催的古灵武士
28分钟前
22
0
osgEarth使用笔记3——加载倾斜摄影数据

目录 1. 概述 2. 详论 2.1. 位置 2.2. 着色 2.3. 其他 3. 结果 4. 参考 1. 概述 我在《OSG加载倾斜摄影数据》这篇博文中论述了如何通过OSG生成一个整体的索引文件,通过这个索引文件来正确显...

osc_7oc4d1en
29分钟前
19
0
cesium加载gltf模型点击以及列表点击定位弹窗

前言 cesium 官网的api文档介绍地址cesium官网api,里面详细的介绍 cesium 各个类的介绍,还有就是在线例子:cesium 官网在线例子,这个也是学习 cesium 的好素材。 之前有部分订阅者咨询我,...

osc_cx8uhydz
30分钟前
14
0
思维导图软件如何插入图片?具体步骤?

学习思维导图制作的过程中,会遇到很多没有学过的知识,需要我们不断地去改进和学习,这样增强自己的学习能力,才能更好地掌握制图软件。以后帮助我们快速方便地完成制图,今天我们就要来看看...

深蓝月上
30分钟前
25
0
Notepad++ 列块模式编辑,替换换行符

一、列块模式编辑: 1、数据准备 2、按住 “Alt + 鼠标左键” 选择需要列块模式编辑的区域,可以看到多了一条竖线 3、之后批量可以添加,修改内容 二、替换换行符 上面说了列块模式的编辑,后...

osc_itgved4p
31分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部