精华内容
下载资源
问答
  • 外部排序

    千次阅读 2015-04-05 21:02:37
    外部排序

       外部排序

        我们一般提到排序都是指内排序,比如快速排序,堆排序,归并排序等,所谓内排序就是可以在内存中完成的排序。但对于大数据集来说,内存是远远不够的,这时候就涉及到外排序的知识了。外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装人内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序。

        一、实现过程
        外部排序过程可以分成两个相对独立的阶段:
        (1)按可用内存的大小,把外存上含有n个记录的文件分成若干个长度为L的子文件,把这些子文件依次读入内存,并利用有效的内部排序方法对它们进行排序,再将排序后得到的有序子文件重新写入外存;
        (2)对这些有序子文件逐趟归并,使其逐渐由小到大,直至得到整个有序文件为止。
        其中,第一个阶段即为内部排序的操作,而第二个阶段涉及到了外部排序中的归并。在前面提到,内存归并排序在开始时是把数组中的每个元素均看作是长度为1的有序表,在归并过程中,有序表的长度从1开始,依次为2、4、8、……,直至有序表的长度len大于等于待排序的记录数n为止。而在对外存文件的归并排序中,初始有序表的长度通常是从一个确定的长度开始而不是从1开始,这是为了能够有效地减少归并的趟数和访问外存的次数,以提高外部排序的效率。所以,在第一阶段要按照初始有序表确定的长度在原文件上依次建立好每个有序表,在第二个阶段再调用对文件的归并排序算法完成排序。

        二、抛砖引玉

        回顾上篇博客《内部排序总结》的第三个例子,即:有10个文件,放在10台机器上,每个文件中有1百万个数。要求选出这1000万个数中最大的50个数。

       这道题目,需要外部排序算法来搞定。外部排序的基本过程由两个相对独立的阶段组成(上面已经提到):
        1、按照内存大小,将外存上含n个记录的文件分成若干长度为L的子文件或段,依次读入内存并用内部排序算法对其分别排序。并将排序后的结果写回外存。将这些有序文件称为:归并段。
        2、对这些归并段进行逐趟排序,得到归并后的有序文件。
        解决上面的这道题,并不需要我们进行完整的外部排序过程。我们省略内外存数据交换过程,重点讲一种外部排序中用来实现高效归并的高级数据结构:
    败者树

        三、胜者树和败者树

        胜者树和败者树都是完全二叉树,是树形选择排序的一种变型。每个叶子结点相当于一个选手,每个中间结点相当于一场比赛,每一层相当于一轮比赛。不同的是,胜者树的中间结点记录的是胜者的标号;而败者树的中间结点记录的败者的标号。胜者树与败者树可以在logn的时间内找到最值。任何一个叶子结点的值改变后,利用中间结点的信息,还是能够快速地找到最值。在k路归并排序中经常用到。

       胜者树

        胜者树的一个优点是,如果一个选手的值改变了,可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树,而不必改变其他比赛的结果。

        

        图1

        图1是一个胜者树的示例(规定数值小者胜)。
        1. b3 PK b4,b3胜b4负,内部结点ls[4]的值为3;
        2. b3 PK b0,b3胜b0负,内部结点ls[2]的值为3;
        3. b1 PK b2,b1胜b2负,内部结点ls[3]的值为1;
        4. b3 PK b1,b3胜b1负,内部结点ls[1]的值为3。

        

    图2

        当图1中叶子结点b3的值变为11时,重构的胜者树如图2所示。
        1. b3 PK b4,b3胜b4负,内部结点ls[4]的值为3;
        2. b3 PK b0,b0胜b3负,内部结点ls[2]的值为0;
        3. b1 PK b2,b1胜b2负,内部结点ls[3]的值为1;
        4. b0 PK b1,b1胜b0负,内部结点ls[1]的值为1。

       败者树

        败者树是胜者树的一种变体。在败者树中,用父结点记录其左右子结点进行比赛的败者,而让胜者参加下一轮的比赛。败者树的根结点记录的是败者,需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。

        

        图3

        图3是一棵败者树(规定数大者败)。
        1. b3 PK b4,b3胜b4负,内部结点ls[4]的值为4;
        2. b3 PK b0,b3胜b0负,内部结点ls[2]的值为0;
        3. b1 PK b2,b1胜b2负,内部结点ls[3]的值为2;
        4. b3 PK b1,b3胜b1负,内部结点ls[1]的值为1;
        5. 在根结点ls[1]上又加了一个结点ls[0]=3,记录的最后的胜者。
        败者树
    重构过程如下:
        1、将新进入选择树的结点与其父结点进行比赛:将败者存放在父结点中;而胜者再与上一级的父结点比较。
        2、比赛沿着到根结点的路径不断进行,直到ls[1]处。把败者存放在结点ls[1]中,胜者存放在ls[0]中。

        

    图4

        图4是当b3变为13时,败者树的重构图。
       
    注意,败者树的重构跟胜者树是不一样的,败者树的重构只需要与其父结点比较。对照图3来看,b3与结点ls[4]的原值比较,ls[4]中存放的原值是结点4,即b3与b4比较,b3负b4胜,则修改ls[4]的值为结点3。同理,以此类推,沿着根结点不断比赛,直至结束。
        由上可知,败者树简化了重构。
    败者树的重构只是与该结点的父结点的记录有关,而胜者树的重构还与该结点的兄弟结点有关。

        

        四、败者树 多路平衡归并外部排序
        1、外部排序的基本思路
        假设有一个72KB的文件,其中存储了18K个整数,磁盘中物理块的大小为4KB,将文件分成18组,每组刚好4KB。
        首先通过18次内部排序,把18组数据排好序,得到初始的18个归并段R1-R18,每个归并段有1024个整数。
        然后对这18个归并段使用5路平衡归并排序:
        第1次归并:产生5个归并段
        R11   R12    R13    R14    R15
        其中
        R11是由{R1,R2,R3,R4}中的数据合并而来
        R12是由{R5,R6,R7,R8}中的数据合并而来
        R13是由{R9,R10,R11,R12}中的数据合并而来
        R14是由{R13,R14,R15,R16}中的数据合并而来
        R15是由{R17,R18}中的数据合并而来
        把这5个归并段的数据写入5个文件:
        foo_1.dat    foo_2.dat    foo_3.dat     foo_4.dat     foo_5.dat
     
        第2次归并:从第1次归并产生的5个文件中读取数据,合并,产生2个归并段
        R21  R22
        其中R21是由{R11,R12,R13,R14}中的数据合并而来
        其中R22是由{R15}中的数据合并而来
        把这2个归并段写入2个文件
        bar_1.dat   bar_2.dat
     
        第3次归并:从第2次归并产生的2个文件中读取数据,合并,产生1个归并段

        R31

        R31是由{R21,R22}中的数据合并而来

        把这个文件写入1个文件
        foo_1.dat
        此即为最终排序好的文件。
     
        2、使用败者树加快合并排序
        外部排序最耗时间的操作时磁盘读写,对于有m个初始归并段,k路平衡的归并排序,磁盘读写次数为|logkm|,可见增大k的值可以减少磁盘读写的次数,但增大k的值也会带来负面效应,即进行k路合并的时候会增加算法复杂度,来看一个例子。
        把n个整数分成k组,每组整数都已排序好,现在要把k组数据合并成1组排好序的整数,求算法复杂度
        u1: xxxxxxxx
        u2: xxxxxxxx
        u3: xxxxxxxx
        .......
        uk: xxxxxxxx
        算法的步骤是:每次从k个组中的首元素中选一个最小的数,加入到新组,这样每次都要比较k-1次,故算法复杂度为O((n-1)*(k-1)),而如果使用败者树,可以在O(logk)的复杂度下得到最小的数,算法复杂度将为O((n-1)*logk), 对于外部排序这种数据量超大的排序来说,这是一个不小的提高。
     
        关于败者树的创建和调整,可以参考清华大学《数据结构-C语言版》。

    #include <iostream>
    using namespace std;
    
    #define LEN 10			//最大归并段长
    #define MINKEY -1     //默认全为正数
    #define MAXKEY 100    //最大值,当一个段全部输出后的赋值
    
    struct Array
    {
    	int arr[LEN];
    	int num;
    	int pos;
    }*A;
    
    	int k,count;
    	int *LoserTree,*External;
    
    void Adjust(int s)
    {
    	int t=(s+k)/2;
    	int temp;
    	while(t>0)
    	{
    		if(External[s] > External[LoserTree[t]])
    		{
    			temp = s;
    			s = LoserTree[t];
    			LoserTree[t]=temp;
    		}
    		t=t/2;
    	}
    	LoserTree[0]=s;
    }
    
    void CreateLoserTree()
    {
    	External[k]=MINKEY;
    	int i;
    	for(i=0;i<k;i++)LoserTree[i]=k;
    	for(i=k-1;i>=0;i--)Adjust(i);
    }
    
    void K_Merge()
    {
    	int i,p;
    	for(i=0;i<k;i++)
    	{
    		p = A[i].pos;
    		External[i]=A[i].arr[p];
    		//cout<<External[i]<<",";
    		A[i].pos++;
    	}
    	CreateLoserTree();
    	int NO = 0;
    	while(NO<count)
    	{
    		p=LoserTree[0];
    		cout<<External[p]<<",";
    		NO++;
    		if(A[p].pos>=A[p].num)External[p]=MAXKEY;
    		else 
    		{
    			External[p]=A[p].arr[A[p].pos];
    			A[p].pos++;
    		}
    		Adjust(p);
    	}
    	cout<<endl;
    }
    
    int main()
    {
    	freopen("in.txt","r",stdin);
    
    	int i,j;
    	count=0;
    	cin>>k;
    	A=(Array *)malloc(sizeof(Array)*k);
    	for(i=0;i<k;i++)
    	{
    		cin>>A[i].num;
    		count=count+A[i].num;
    		for(j=0;j<A[i].num;j++)
    		{
    			cin>>A[i].arr[j];
    		}
    		A[i].pos=0;
    	}
    	LoserTree=(int *)malloc(sizeof(int)*k);
    	External=(int *)malloc(sizeof(int)*(k+1));
    
    	K_Merge();
    
    	return 0;
    }
        

    也可参考:

    http://mp.weixin.qq.com/s?__biz=MzA5NjQ4NDA4Mw==&mid=210783856&idx=1&sn=28035af2e7b5565337b7a4debbbc39ee&scene=5

        

        

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,699
精华内容 2,279
关键字:

外部排序