精华内容
下载资源
问答
  • 外部排序
    2021-08-03 16:34:03

    外部排序

    外部排序:由于计算机内存有限,当数据量过大时,数据不能一次性加载到内存中,数据保存在外存中(硬盘,文件里面)上,(寄存器>Cache>内存>固态硬盘>机械硬盘),限制外部排序效率的是IO(读写)的效率。如果要提高外部排序的效率,就要减少IO次数。

    一般来说外排序分为两个步骤:预处理和合并排序。首先,根据可用内存的大小,将外存上含有n个纪录的文件分成若干长度为t的子文件(或段);其次,利用内部排序的方法,对每个子文件的t个纪录进行内部排序。这些经过排序的子文件(段)通常称为顺串(run),顺串生成后即将其写入外存。这样在外存上就得到了m个顺串(m=[n/t])。最后,对这些顺串进行归并,使顺串的长度逐渐增大,直到所有的待排序的记录成为一个顺串为止。

    思路:
    

    在这里插入图片描述
    上面的是4路归并

    (1) 二路合并排序
    二路合并是最简单的合并方法,合并的实现与内排序中的二路归并算法并无本质区别,下面通过具体例子,分析二路合并外部排序的过程。

    有一个含有9000个纪录的文件需要排序(基于关键字)。假定系统仅能提供容纳1800个纪录的内存。文件在外存(如磁盘)上分块存储,每块600个纪录。外部排序的过程分为生成初始顺串和对顺串进行归并排序两个阶段。在生成初始顺串阶段,每次读入1800个纪录(即3段)待内存,采用内排序依次生成顺串依次写入外存储器中。

    顺串生成后,就开一开始对顺串进行归并。首先将内存等分成3个缓冲区,每个缓冲区可容纳600个纪录,其中两个为输入缓冲区,一个为输出缓冲区,每次从外存读入待归并的块到输入缓冲取,进行内部归并,归并后的结果送入输出缓冲区,输出缓冲区的记录写满时再将其写入外存。若输入缓冲区中的纪录为空,则将待归并顺串中的后续块读入输入缓冲区中进行归并,直到待归并的两个顺串都已归并为止。重复上述的归并方法,由含有5块(每块上限1800个记录)的顺串经二路归并的一遍归并后生成含有3块(每块上限3600个记录)的顺串,再经过第二遍……第s遍(s=[],m为初始顺串的个数),生成含有所有记录的顺串,从而完成了二路归并外部排序。

    对文件进行外部排序的过程中,因为对外存的读写操作所用的操作的时间远远超过在内存中产生顺串和合并所需的时间,所以常用对外存的读写操作所用的时间作为外部排序的主要时间开销。分析一下上述二路归并排序的对外存的读写时间。初始时生成5个顺串的读写次数为30次(每块的读写次数为2次)。
    类似地,可得到二路、三路……多路合并方法。

    (2) 多路替代选择合并排序

    采用多路合并技术,可以减少合并遍数,从而减少块读写次数,加快排序速度。但路数的多少依赖于内存容量的限制。此外,多路合并排序的快慢还依赖于内部归并算法的快慢。

    设文件有n个纪录,m个初始顺串,采用k路合并方法,那么合并阶段将进行遍合并。k路合并的基本操作是从k个顺换的第一个纪录中选出最小纪录(即关键字最小的纪录),把它从输入缓冲区移入输出缓冲区。若采用直接选择方式选择最小元,需要k-1次比较,遍合并共需n(k-1)=次比较。由于随k的增长而增长,则内部归并时间亦随k的增大而增大,这将抵消由于增大k而减少外存信息读写时间所得的效果。若在k个纪录中采用树形选择方式选择最小元,则选择输出一个最小元之后,只需从某叶到根的路径上重新调整选择树,即可选择下一个最小元。重新构造选择书仅用O()次比较,于是内部合并时间O(n)=O(),它与k无关,不再随k的增大而增大。

    m路归并
    外部排序读写的次数与归并的趟数成正比
    每归并一趟,把所有的数据加载进来,并且写回来
    总共进行多少趟归并 log(m) n/k   logm r
    n总的数据个数
    k每个内存块中数据存储的个数
    n/k ==  数据块  初始归并段的数量  r
    

    提高外部排序的效率:
    1.多路归并 增加归并路数
    多路归并时,为了减少比较次数
    败者树 选取最小值只需要logm次比较
    2.减少初始归并段
    增加每个归并段的数据量(内存变大)
    置换选择排序 来初始化归并段

    最佳归并树
    	用置换-选择排序 初始化的每个归并段中数据的个数不一样
    	用这些归并段来构造一个m叉树,要使得读写次数最少
    	需要构造一棵最优m叉树,最佳归并树和哈夫曼树差不多
    9个归并段:
    	9,30,12,18,3,17,2,6,24
    	(9+30+12+18+3+17+2+6+24)*2 = 484
    
    9,12,18,3,17,2,6,24  
    为了构造m叉最佳归并树,可能需要增加虚段(0)
    9,12,18,3,17,2,6,24  构成三叉最优归并树
    9,12,18,3,17,2,6,24 ,0
    
    假设对m个归并段,进行k路归并,使读写次数最少 得构造最优归并树
    需要补充多少个虚段?
    
    9个归并段  3路归并  
    8个归并段  3路归并   1个虚段
    7个归并段  3路归并   
    10个归并段 4路归并 
    11个归并段 4路归并 
    (m-1)%(k-1) == 0  不需要补充虚段
    
    m叶子结点个数  除了叶子结点以外,所有n结点需要k个子结点
    	n个度为k的结点  m个度为0的结点
    	结点个数=总度数+1
    nk+1=n+m
    (k-1)n = m-1  n肯定是整数
    n = (m-1)/(k-1)  (m-1)%(k-1)为0
    
    需要补:
    	k-(m-1)%(k-1)-1个虚段
    	k-1 - (m-1)%(k-1)		
    	x/y != 0
    	x%y 余数
    	(x-x%y+y)%y == 0
    	(x+(y-x%y))%y == 0
    
    外部排序的二路归并思路
    影响外部排序效率的因素
    提高外部排序的效率 减少归并的趟数(增加归并路数 减少初始归并段的数量)
    增加归并路数:
    

    败者树 (减少比较次数)

    在这里插入图片描述

    败者树是计算机科学学科里的一种数据结构,可用于外部排序中提高效率。败者树实际上是一棵完全二叉树,可以看做是胜者树的一种变体。败者树简化了重构。败者树的重构只是与该结点的父结点的记录有关,而胜者树的重构还与该结点的兄弟结点有关。败者树中每个叶节点存放各归并段在归并过程中当前参加比较的记录,每个非叶结点记忆其两个子女结点中记录排序码小的结点(即败者)。
    败者树
    败者树

    注意,败者树的重构跟胜者树是不一样的,败者树的重构只需要与其父结点比较。对照右图来看,b3与结点ls[4]的原值比较,ls[4]中存放的原值是结点4,即b3与b4比较,b3负b4胜,则修改ls[4]的值为结点3。同理,以此类推,沿着根结点不断比赛,直至结束。
    败者树重构过程如下:
    将新进入选择树的结点与其父结点进行比赛:将败者存放在父结点中;而胜者再与上一级的父结点比较。
    比赛沿着到根结点的路径不断进行,直到ls[1]处。把败者存放在结点ls[1]中,胜者存放在ls[0]中。

    转换选择排序:
    	得到初始归并段(每个归并段是有序的)
    最佳归并树:
    	根据初始归并段构造最佳归并树,减少读写磁盘次数
    
    更多相关内容
  • 有文件大小为1G的一个文件,文件每行存储的为URL及其访问次数,例如/api/auth/login 2 ,计算出访问次数最多的前5个URL和其访问次数,每行的URL可能重复,计算内存限制10M。 === 内含解题思路、测试结果截图、可运行...
  • 外部排序

    2021-06-05 16:08:08
    外部排序的基本概念 前面介绍过的排序方法都是在内存中进行的(称为内部排序)。而在许多实际应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进 行排序。因此,需要...

    外部排序基本概念

    在许多实际应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进行排序。因此,需要将待排序的记录存储在外存上,排序时再把数据一部分 一部分地调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换,对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序方法就称为外部排序。

    外存、内存之间的数据交换

    在实际应用中,由于外存设备的不同,通常又可分为磁盘文件排序和磁带文件排序两大类。磁带文件排序和磁盘文件排序的基本步骤类似,主要不同之处是初始归并段在外存介质中的分布方式,磁盘是直接存取设备,磁带是顺序存取设备。
    在这里插入图片描述
    文件通常是按块存储在磁盘上的,操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读/写的机械动作所需的时间远远超过内存运算的时间(相比而言可以忽略不计),因此在外部排序过程中的时间代价主要考虑访问磁盘的次数,即I/O次数。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    外部排序原理

    外部排序通常采用归并排序方法。它包括两个相对独立的阶段:首先,根据内存缓冲区的大小,将外存上含n个记录的文件分成若干长度为h的子文件,依次读入内存并利用有效的内部排序方法对它们进行排序,并将排序后得到的有序子文件重新写回外存,通常称这些有序子文件为归并段或顺串,然后,对这些归并段进行逐趟归并,使归并段(有序的子文件)逐渐由小到大,直至得到整个有序文件为止。
    在这里插入图片描述

    构造初始归并段

    一个含有 2000个记录的文件, 每个磁盘块可容纳250个记录,则该文件包含8个磁盘块。然后对该文件做2路归并排序,每次向内存读入两个磁盘块,排序后再写回磁盘。若把内存工作区等分为3个缓冲区,其中的两个为输入缓冲区,二个为输出缓冲区,则可以在内存中利用简单2路归并Merge()函数实现2路归并。
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    第一趟归并

    在这里插入图片描述
    首先,从参加归并排序的两个输入归并段R1和R2中分别读入一个块,放在输入缓冲区1和输入缓冲区2中。
    在这里插入图片描述
    然后,在内存中进行2路归并,归并出来的对象顺序存放在输出缓冲区中。
    在这里插入图片描述
    若输出缓冲区中对象存满,则将其内的对象顺序写到输出归并段(R1’)中,再将该输出缓冲区清空,继续存放归并后的对象。
    在这里插入图片描述
    若某个输入缓冲区中的对象取空,则从对应的输入归并段中再读取下一块(这种情况在第一趟归并时不会出现),继续参加归并。
    在这里插入图片描述
    在这里插入图片描述
    如此继续,直到两个输入归并段中的对象全部读入内存并都归并完成为止。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    当R1和R2归并完后,再归并R3和R4、R5和R6、最后归并R7和R8,这是一趟归并。
    在这里插入图片描述

    第二趟归并

    再把上趟的结果R1’、R2’、R3’和R4’两两归并,这又是一趟归并。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    第三趟归并

    最后把R1"和R2"两个归并段归并,结果得到最终的有序文件,一共进行了3趟归并。
    在这里插入图片描述
    在这里插入图片描述
    在外部排序中实现两两归并时,不仅要调用Merge()过程,而且要进行外存的读/写,由于不可能将两个有序段及归并结果段同时存放在内存中,因此需要不停地将数据读出、写入磁盘,而这会耗费大量的时间。

    时间开销分析

    外部排序的总时间=内部排序所需的时间+外存信息读写的时间+内部归并所需的时间
    在这里插入图片描述
    tES=rtIS+dtIO+S(n-1)tmg

    式中,r是初始归并段的个数,tIS是对每个初始归并段进行内部排序的时间,d是访问外存块的次数,t0是每个块的存取时间,s是归并趟数,n是每趟参加2路归并的记录个数,tmg是每做一次内部归并时,取得一个关键字最小记录的时间。显然, 磁盘存取的时间远大于内部排序和内部归并的时间,因此要提高外部排序的速度,应着力减少d,即I/O次数。

    如何优化

    在这里插入图片描述
    由于外存上信息的读/写是以“物理块”为单位的,且每个物理块可容纳250个记录,可知每一趟归并需进行8次“读”和8次“写”,3趟归并加上内部排序时所需进行的读/写,使得在外部排序中共需进行164=64次读写。故上述2路平衡归并排序的总时间为
    8
    tIS+64tIO+32000tmg

    优化:多路归并

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    若采用4路归并排序,则只需要2趟归并,外部排序时的总读/写次数便减至2*16 + 16=48。因此,增大归并路数,可减少归井越数,进而减少总的磁盘I/O次数。
    在这里插入图片描述

    优化:减少初始归并段数量

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    树的高度=⌈logmr⌉= 归并趟数S。可见,只要增大归并路数m,或减少初始归并段个数r,都能减少归并趟数S,进而减少读写磁盘的次数d,达到提高外部排序速度的目的。

    纠正:什么是多路平衡归并

    一般地,对r个初始归并段,做m路平衡归并,归并树可用严格m叉树(即只有度为m与度为0的结点的m叉树)来表示。第一趟可将r个初始归并段归并为⌈r/m⌉个归并段,以后每趟归并将l个归并段归并成⌈l/m⌉个归并段,直到最后形成一个大的归并段为止。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。
  • 文件_处理通过改进的快速排序进行外部排序您将为二进制数据实现外部排序算法。 输入数据文件将由许多 4 字节记录组成,每个记录由 1 到 30,000 范围内的两个 2 字节(短)整数值组成。 第一个 2 字节字段是键值...
  • 完整java实现外部排序

    2021-02-12 20:53:03
    外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。选自百度百科。第一步: 首先我们先来创建...

    外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。选自百度百科。

    第一步:      首先我们先来创建一个大号的文件。

    public class Sort {

    public static void main(String[] args) throws IOException{

    File file=new File("E:/排序/source.txt");

    int numCount=10000000;

    Random r=new Random();

    if(file.exists())file.delete();

    FileWriter fw=new FileWriter(file);

    for(int i=0;i

    fw.write(r.nextInt()+"\n");

    }

    fw.close();

    }

    文件不是很大,也就107M左右,当然我们可以修改numCount来让这个文件变得更大。

    第二步,外部排序,以下是完整代码

    package sort;

    import java.io.BufferedReader;

    import java.io.BufferedWriter;

    import java.io.File;

    import java.io.FileReader;

    import java.io.FileWriter;

    import java.io.IOException;

    import java.util.ArrayList;

    import java.util.List;

    import java.util.Random;

    public class Sort {

    public static void main(String[] args) throws IOException{

    File file=new File("E:/排序/source.txt");

    BufferedReader  fr=new BufferedReader(new FileReader(file));//源数据文件读取。

    final int SIZE=10000;//这里是定义我们将源文件中以10000条记录作为单位进行分割。

    int[] nums=new int[SIZE];//临时存放分割时的记录

    List fileNames=new ArrayList();//保存所有分割文件的名称

    int index=0;

    while(true){

    String num=fr.readLine();//从原文件中读取一条记录

    if(num==null){//如果读取完毕后,进行一次排序并保存

    fileNames.add(sortAndSave(nums,index));

    break;

    }

    nums[index]=Integer.valueOf(num);

    index++;

    if(index==SIZE){//当nums里面读的数字到达长度边界时,排序,存储

    fileNames.add(sortAndSave(nums,index));//sortAndSave是将nums中前index条记录先快速排序,然后存入文件,最好将文件名返回。

    index=0;//重置index

    }

    }

    fr.close();

    mergeSort(fileNames);//将所有fileNames的文件进行合并

    }

    //sortAndSave是将nums中前index条记录先快速排序,然后存入文件,最好将文件名返回

    public static String sortAndSave(int[] nums,int size) throws IOException{

    quicksort.sort(nums,0, size-1);

    String fileName="E:/排序/sort"+System.nanoTime()+".txt";

    File rf=new File(fileName);

    BufferedWriter bw=new BufferedWriter(new FileWriter(rf));

    for(int i=0;i

    bw.close();

    return fileName;

    }

    public static void mergeSort(List fileNames) throws IOException{

    List tempFileNames=new ArrayList();

    for(int i=0;i

    String resultFileName="E:/排序/sort"+System.nanoTime()+".txt";

    File resultFile=new File(resultFileName);

    tempFileNames.add(resultFileName);

    BufferedWriter bw=new BufferedWriter(new FileWriter(resultFile));

    File file1=new File(fileNames.get(i++));

    BufferedReader br1=new BufferedReader(new FileReader(file1));

    if(i

    File file2=new File(fileNames.get(i));

    BufferedReader br2=new BufferedReader(new FileReader(file2));

    int num1=0;

    int num2=0;

    boolean isFirst=true;

    boolean firstNext=true;

    String numVal1=null,numVal2=null;

    for(;;){

    if(isFirst){

    numVal1=br1.readLine();

    numVal2=br2.readLine();

    num1=Integer.valueOf(numVal1);

    num2=Integer.valueOf(numVal2);

    isFirst=false;

    }

    else if(firstNext)

    numVal1=br1.readLine();

    else

    numVal2=br2.readLine();

    if(numVal1!=null && numVal2!=null){

    if(firstNext){

    num1=Integer.valueOf(numVal1);

    }else{

    num2=Integer.valueOf(numVal2);

    }

    if(num1

    bw.write(num1+"\n");

    firstNext=true;

    }else{

    bw.write(num2+"\n");

    firstNext=false;

    }

    }else{

    if(numVal1!=null)bw.write(numVal1+"\n");

    if(numVal2!=null)bw.write(numVal2+"\n");

    break;

    }

    }

    while(true){

    numVal2=br2.readLine();;

    if(numVal2!=null)bw.write(numVal2+"\n");

    else break;

    }

    br2.close();

    file2.delete();

    }

    while(true){

    String numVal1=br1.readLine();

    if(numVal1!=null){

    bw.write(numVal1+"\n");

    }

    else break;

    }

    br1.close();

    file1.delete();

    bw.close();

    }

    int size=tempFileNames.size();

    if(size>1){

    mergeSort(tempFileNames);

    }else if(size==1){

    File file=new File(tempFileNames.get(0));

    file.renameTo(new File("E:/排序/result.txt"));

    }

    }}

    //快速排序

    class quicksort {

    public static void sort(int data[],int low,int hight){

    quicksort qs=new quicksort();

    qs.data=data;

    qs.sort(low, hight);

    }

    public int data[];

    private int partition(int sortArray[], int low, int hight) {

    int key = sortArray[low];

    while (low < hight) {

    while (low < hight && sortArray[hight] >= key)hight--;

    sortArray[low] = sortArray[hight];

    while (low < hight && sortArray[low] <= key)low++;

    sortArray[hight] = sortArray[low];

    }

    sortArray[low] = key;

    return low;

    }

    public void sort(int low, int hight) {

    if (low < hight) {

    int result = partition(data, low, hight);

    sort(low, result - 1);

    sort(result + 1, hight);

    }

    }

    public void display() {

    for (int i = 0; i < data.length; i++) {

    System.out.print(data[i]);

    System.out.print(" ");

    }

    }

    }

    分享到:

    18e900b8666ce6f233d25ec02f95ee59.png

    72dd548719f0ace4d5f9bca64e1d7715.png

    2012-02-16 17:58

    浏览 4359

    分类:互联网

    评论

    1 楼

    abao1

    2018-05-03

    发现一个小问题 sortAndSave方法中的for循环 第二个参数应该用size吧

    5fc1b339112ca891d78bf0475ef98611.gif

    展开全文
  • 外部排序 C++源码

    2014-08-11 23:59:40
    原创,外部排序的C++源码,利用败者树16路归并,主要源于字典排序的需要,所以针对的是字符串,可以自定义字符串的最大最小长度,可以自定义归并路数,根据词组的大小,自定义设定内部排序的大小
  • 外部排序算法详解

    2014-10-29 12:24:29
    本PPT详细讲解了外部排序算法,讲解言简意赅,深入浅出,想了解外部排序算法的朋友可以下载阅读。
  • 外部排序专题

    2020-12-03 13:14:21
    1.外部排序基本概念:前面介绍的排序都是内部排序,是直接在内存里面进行排序的,但是大多数情况下文件比较大,这时候我们就得把文件分割成一个个小块进行输入内存再排序。在排序过程中需要进行多次的内存与外存之间...

    1.外部排序基本概念:前面介绍的排序都是内部排序,是直接在内存里面进行排序的,但是大多数情况下文件比较大,这时候我们就得把文件分割成一个个小块进行输入内存再排序。在排序过程中需要进行多次的内存与外存之间的交互,所以称之为外部排序。

    外部排序操作:以例题作为讲解

    例题1:假设文件有4500个记录,每块磁盘可以放75个记录,计算机中用于排序的内存区可以存放 450 个记录,试问:
    1)可以建立多少个初始归并段?每个归并段有多少个记录?存放于多少个块中?
    2)应采用几路归并,请写出每趟需要读写磁盘的块数

    解答:
    1) 文件中有4500个记录,内部排序区可容纳450个记录(其实排序过程是 依次 输入1-450,451-900… 进行排序,然后输出构成有序的初始归并段 ),则可建立的初始归并段为4500/450 = 10,每个初始归并段有450个记录,存放于 450/75 =6 个块中。
    2)内存区可以容纳6个块,所以可以建立5个输入缓冲区。1个输出缓冲区,因此采用5路归并。
    归并次数为 log(5)10 = 2,每次归并需要读写磁盘次数都为4500/75=60 次 ,每次归并需要读写磁盘总次数为为60 * 2 =120 次,做了两趟归并,读写总次数 2 * 120=240。
    另外再来看看
    2.外部排序总时间= 内部排序所需时间+外村信息读写时间+内部归并需要时间

    内部排序所需时间 :就是第一次进行生成初始归并序列的时间,这其中就有一次读写时间,排序时间可以忽略。如上题内部排序所需时间为 120 相当于一次归并的时间
    外存信息读写时间 :其实就是归并次数乘以每次读写时间,上题为 两次归并,每次归并读写磁盘次数为120 ,所以总时间为2 * 120 = 240次。
    内部归并需要时间:就是在内存中进行序列段合并为一个序列段所需时间,这一时间其实主要在于数据进行比较的时间,例如上题,进行的是5路归并,那么在5个元素中选取最小数比较次数是4次,总共有4500个记录,最后一个不需要比较,因此每趟归并需要的比较次数为 (4500-1)*4=17996次,进行两次归并,17996 *2=35992次比较。但是比较时间相比于读写时间比较短所以可以忽略。

    归并次数 S=log(k) r 。r为初始归并段,k为归并路数,证明很简单,略。若是不采用其他方法进行比较次数优化则S趟总共需要比较次数为 S( n-1 )( k-1) = [ log(k) r ] ( n-1 )( k-1)=[log2 r] (n-1)(k-1)/[log2k] ,式子中 (k-1)/log2k 随着路数k的增大而增大,这将抵消由于k增大而减少外存访问次数所得到的效益,那么能不能使用其他方法来减少比较次数呢?下面介绍败者树方法。
    败者树:树中k个叶节点分别存放k个归并段在归并过程中当前参加比较的记录,内部节点用来记录左右子树的 “败者” 而胜利者继续向上比较直到到达根节点,如图所示。
    在这里插入图片描述

    因为 k 路归并的败者树深度为log2k , 因此k 个记录中选择最小关键字,最多需要 log2k次比较,所以排序总的比较次数为S(n-1)[log2k]=[log(k)r] (n-1) log2k=(n-1) log2r 。 可见使用败者树后内部归并的比较次数就与k无关了,因此只要内存空间允许,可以通过增大路数k达到减少 I/O 次数,提高外部排序速度。
    值得说明的是,归并路数k并不是越大越好,归并路数k增大,相应的得增加输入缓冲区的块数,若是可使用的空间一定,势必要减少每个输入缓冲区的容量,这样也会使得内存、外存交换数据次数增加,因此仍然会导致时间增大。

    还有什么办法可以减少排序时间呢?

    3.置换选择排序(生成初始归并段)
    只要增大初始归并段长度就可以减少初始归并段个数,达到减少归并时间的效果。

    在这里插入图片描述
    上述算法中WA选择最小数使用败者树实现。

    综上所述:每一次归并所读取 I/O 的次数是一定的,总记录/每块磁盘容量,因此可以通过减少归并次数,达到减少读取次数减少排序时间问题,那么减少归并次数的方法有:增大归并路数 或者 增大初始序列 。
    实现代码:

    
    void Select_MiniMax(LoserTree ls,WorkArea wa,int q){
        int p, s, t;
    // ls[t]为q的双亲节点,p作为中介
       
        for(t = (w+q)/2,p = ls[t]; t > 0;t = t/2,p = ls[t]){
            // 段号小者 或者 段号相等且关键字更小的为胜者
            if(wa[p].rnum < wa[q].rnum || (wa[p].rnum == wa[q].rnum && wa[p].key < wa[q].key)){
                s=q;
                q=ls[t]; //q指示新的胜利者
                ls[t]=s;
            }
        }
        ls[0] = q; // 最后的冠军
    }
    //输入w个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录,并由s指示其在wa中的位置。
    void Construct_Loser(LoserTree ls, WorkArea wa, FILE *fi){
        int i;
        for(i = 0; i < w; ++i){
            wa[i].rnum = wa[i].key = ls[i] = 0;
        }
        for(i = w - 1; i >= 0; --i){
            fread(&wa[i].rec, sizeof(RedType), 1, fi);// 输入一个记录
            wa[i].key = wa[i].rec.key; // 提取关键字
            wa[i].rnum = 1; // 其段号为"1"
            Select_MiniMax(ls,wa,i); // 调整败者树
        }
    }
    
    

    4.最佳归并树

    文件经过置换选择排序后,得到的是长度不等的初始归并段,下面讨论如何组织长度不等的初始归并段的归并顺序使得IO次数最少。其实也就是m叉哈夫曼树类似,很简单,不展开叙述。其中有一点不同是,可能初始归并段个数并不能构成严格的k叉树,这时就要补充虚段了。

    如何确定添加虚段的数目?
    设度为0的节点有 N0 个,度为 k的节点个数有Nk个,则对于严格k叉树 N0=(k-1) Nk+1,由此可得Nk=(N0-1)/(k-1) 。

    1. 若是(N0-1)%(k-1) =0 , 则说明这N0个叶节点正好可以构成严格k叉树。
    2. 若是不等于0,则设需要添加 m个 长度为0 的虚段使得(N0+m-1)%(k-1)=0,即可。

    以上就是外部排序的全部内容

    展开全文
  • 什么是外部排序

    千次阅读 2021-08-18 14:36:59
    外部排序外部排序的基本概念外部排序的方法后续 外部排序的基本概念 在内存中进行的排序是内部排序,而在许多应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进行...
  • 数据结构---归并排序和外部排序

    千次阅读 2019-04-23 19:11:39
    若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。 就地排序 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),称为就地排序。 稳定排序 ...
  • 排序(二) - 外部排序

    2020-07-14 09:16:54
    外部排序,指待排序文件较大,内存依次放不下,需存放在外存的文件的排序。 在许多应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进行排序。因此,需要将待排序...
  • 八大内部排序+外部排序

    千次阅读 2019-07-12 21:42:21
    排序划分 内部排序 1.直接插入排序 基本思想 通常人们整理桥牌的方法是一张一张的来,将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中,为了要给插入的元素腾出空间,我们需要将其余所有元素...
  • Python实现外部排序

    2021-07-06 00:30:11
    本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。引言外部排序法:外部排序分为独立的两部分组成:1.按可用内存大小,利用内部排序方法,构造若干个记...
  • 多线程外部排序&wordcount 版权所有 (c) 2014,龙 (Ryan) 南宫。 保留所有权利。 邮箱: 创建时间:2014 年 10 月 9 日共享内存多线程外部排序和词频统计。 a) 使用 Makefile 编译源代码。 b) 通过修改源代码顶部的...
  • 2021考研408数据结构基础知识点:外部排序一、外部排序的基本概念在许多应用中,经常需要对大文件进行排序,因为文件中的记录很多、信息量庞大,无法将整个文件复制进内存中进行排序。因此,需要将待...
  • 排序算法之归并排序和外部排序

    千次阅读 2018-06-11 09:29:12
    一、归并排序   归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的...
  • 数据结构课程是计算机类专业的专业基础课程,在IT...系列课程包含11个部分,本课为第10部分外部排序外部排序针对数据量很大时,排序过程必须要在内、外存之间交换数据时的应用,介绍磁盘排序和磁带排序的相关算法。
  • 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们通常所说的排序算法往往指的是内部排序算法,即数据...
  • 外部排序 外部排序指的是大文件排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。 一般来说外排序分为两个步骤:...
  • 本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。前言在上一次的文章中介绍了外部排序的定义以及基础实现过程,本文章是对外部排序的次数与时间的相关算...
  • 利用python,JavaScript,java,go,PHP等实现: 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序排序 计数排序排序 基数排序
  • 第7章 文件与外部排序数据结构与算法计算机科学与技术学院(2021春)数据结构与算法第六部分 排序第7章 文件与外部排序数据结构与算法计算机科学与技术学院(20

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 252,961
精华内容 101,184
关键字:

外部排序

友情链接: MLP.zip