精华内容
下载资源
问答
  • 大数据排序

    千次阅读 2018-02-28 10:09:14
     在大数据研究的路上,我们总要对一些很大的数据进行各种各样的操作。比如说对数据排序,比如说对数据统计,比如说对数据计算。而在大量的数据面前,我们总是束手无策,因为我们无法在限定时间的情况下,在效率上...

    转自http://blog.csdn.net/lemon_tree12138/article/details/48783535

    前言:

      在大数据研究的路上,我们总要对一些很大的数据进行各种各样的操作。比如说对数据排序,比如说对数据统计,比如说对数据计算。而在大量的数据面前,我们总是束手无策,因为我们无法在限定时间的情况下,在效率上做到让人满意,也无法在限定空间的情况下,能够快速解决问题。可能我们在一些日常的开发过程中,没有遇到过这些问题。不过,现在是时候来考虑一下这样的问题了。因为,现在正值大数据的时代。

      在本文中我会用三种方法,从两个方面来说明如何解决对5亿数据进行排序工作。

                                                                  

    思路分析:

      拿到这样的一个问题,你的第一感觉是什么?冒泡排序?选择排序?插入排序?堆排?还是快排?可能你的想法是我的内存不够。的确,这么大的一个数据量,我们的内存的确不够。因为单是5亿的整数数据就有3.7个G(别说你是壕,内存大着呢)。既然内存不够,那么我们要怎么来解决呢?

      要知道我们一步做不了的事,两步总能做到。那么我们就来尝试第一步做一些,剩下的一些就等会再来搞定吧。基于这样的思路,就有下面的一个解题方法——分治!

    1.分治——根据数据存在文件中的位置分裂文件到批量小文件中

      相对于朴素的排序,这是一种比较稳妥的解决方法。因为数据量太大了!我们不得不将大事化小,小事化了。

      这里我们的做法是每次读取待排序文件的10000个数据,把这10000个数据进行快速排序,再写到一个小文件bigdata.part.i.sorted中。这样我们就得到了50000个已排序好的小文件了。

      在有已排序小文件的基础上,我只要每次拿到这些文件中当前位置的最小值就OK了。再把这些值依次写入bigdata.sorted中。

    2.分治——根据数据自身大小分裂文件到批量小文件中

      按照数据位置进行分裂大文件也可以。不过这样就导致了一个问题,在把小文件合并成大文件的时候并不那么高效。那么,这里我们就有了另一种思路:我们先把文件中的数据按照大小把到不同的文件中。再对这些不同的文件进行排序。这样我们可以直接按文件的字典序输出即可。

    3.字典树

      关于字典树的基本使用,大家可以参见本人的另一篇博客:《数据结构:字典树的基本使用

      基于《数据结构:字典树的基本使用》这篇博客中对字典序的讲解,我们知道我们要做就是对字典树进行广度优先搜索。


    结构设计图:

      


    代码分析:

    0.分治

    (0)分割大文件

      此步对大文件的分割是按序进行的,这样我们就可以确保数据的离散化,不会让一个小文件中的数据很多,一个小文件的数据很少。

    [java]  view plain  copy
    1. public static void splitBigFile2PartBySerial(String filePath, String partPath) throws IOException {  
    2.         File file = new File(filePath);  
    3.         FileInputStream inputStream = new FileInputStream(file);  
    4.         BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));  
    5.           
    6.         StringBuffer buffer = new StringBuffer();  
    7.           
    8.         String readerLine = "";  
    9.         int line = 0;  
    10.         while ((readerLine = reader.readLine()) != null) {  
    11.             buffer.append(readerLine + " ");  
    12.             if (++line % Config.PART_NUMBER_COUNT == 0) {  
    13.                 sortStringBuffer(buffer);  
    14.                 int splitLine = line / Config.PART_NUMBER_COUNT;  
    15.                 write(partPath.replace("xxx""" + splitLine), buffer.toString());  
    16.                 buffer.setLength(0);  
    17.                 System.out.println("SPLIT: " + splitLine);  
    18.             }  
    19.         }  
    20.           
    21.         reader.close();  
    22.     }  

    (1)排序

      即使是已经切割成小份的了,不过每个小文件中的数据集仍然有50000个。因为50000个数据也不是一个小数据,在排序的过程中,也会有一些讲究,所有这里我们使用的是快排。如下:

    [java]  view plain  copy
    1. public static void sortStringBuffer(StringBuffer buffer) {  
    2.         String[] numberTexts = buffer.toString().split(" ");  
    3.         buffer.setLength(0);  
    4.         int[] numbers = new int[numberTexts.length];  
    5.         for (int i = 0; i < numberTexts.length; i++) {  
    6.             numbers[i] = Integer.parseInt(numberTexts[i]);  
    7.         }  
    8.           
    9.         int[] sorted = QKSort.quickSort(numbers);  
    10.         for (int i = 0; i < sorted.length; i++) {  
    11.             buffer.append(sorted[i] + "\n");  
    12.         }  
    13.     }  

    (2)合并

      在合并的时候,我们要明确一个问题。虽然我们的单个小文件已经有序,不过我们还并不知道整体的顺序。比如:

      文件1:1 2 4 6 9 34 288

      文件2:4 5 6 87 99 104 135

      上面的两个文件虽然每个文件内部已经有序,不过整体来说,是无序的。对于在单个文件有序的基础上,我们可以做一些事情。我们可以把每个文件中的数据看成是一个队列,我们总是从队列的首部开始进行出队(因为队列的头部总是最小的数)。这样,我们就把问题转化成从N个小文件中依次比较,得到最小的结果并记入文件(当然,我们不可以生成一个数就写一次文件,这样太低效了,我们可以使用一个变量缓存这此"最小值",在累计到一定数量之后再一次性写入。再清空变量,循环反复,直到文件全部写入完毕)。

    [java]  view plain  copy
    1. public static void mergeSorted(String dirPath) throws NumberFormatException, IOException {  
    2.         long t = System.currentTimeMillis();  
    3.           
    4.         File dirFile = new File(dirPath);  
    5.         File[] partFiles = dirFile.listFiles();  
    6.           
    7.         FileInputStream[] inputStreams = new FileInputStream[partFiles.length];  
    8.         BufferedReader[] readers = new BufferedReader[partFiles.length];  
    9.           
    10.         int[] minNumbers = new int[partFiles.length];  
    11.         for (int i = 0; i < partFiles.length; i++) {  
    12.             inputStreams[i] = new FileInputStream(partFiles[i]);  
    13.             readers[i] = new BufferedReader(new InputStreamReader(inputStreams[i]));  
    14.             minNumbers[i] = Integer.parseInt(readers[i].readLine());  
    15.         }  
    16.           
    17.         int numberCount = Config.TOTAL_NUMBER_COUNT;  
    18.         while (true) {  
    19.             int index = Tools.minNumberIndex(minNumbers);  
    20.             System.out.println(minNumbers[index]);  
    21.             write(Config.BIGDATA_NUMBER_FILEPATH_SORTED, minNumbers[index] + "\n");  
    22.             minNumbers[index] = Integer.parseInt(readers[index].readLine());  
    23.               
    24.             if (numberCount-- <= 0) {  
    25.                 break;  
    26.             }  
    27.         }  
    28.           
    29.         System.err.println("TIME: " + (System.currentTimeMillis() - t));  
    30.           
    31.         for (int i = 0; i < partFiles.length; i++) {  
    32.             inputStreams[i].close();  
    33.             readers[i].close();  
    34.         }  
    35.     }  
    注:这里关于分治的算法,我就只提供一种实现过程了。可能从上面的说明中,大家也意识到了一个问题,如果我们把大文件中的数据按照数值大小化分到不同的小文件中。这样会有一个很致命的问题,那就是可能我们的小文件会出现两极分化的局面,即有一部分文件中的数据很少,有一部分小文件中的数据很多。所以,这里我就不再提供实现过程,在上面有所说明,只是想说我们在解决问题的时候,可能会有很多不同的想法,这些想法都很好,只是有时我们需要一个最优的来提升逼格(^_^)。


    1.字典树

      因为我们知道字典树是可以压缩数据量的一种数据结构,尤其是针对那么使用的字符串个数有限(比如:'0','1','2','3','4','5','6','7','8','9'),并整体数量很多的情况。因为我们可以可以让同一个字符重复使用多次。比如:"123456789"和"123456780"其实只使用了'0'-'9'这10个字符而已。关于字典树的实现,我想是很简单的一种方法。如果你还是感觉有些朦胧和模糊的话,就请参见本人的另一篇博客数据结构:字典树的基本使用》,在那一篇博客中,我有很详细地介绍对字典树的各种基本操作及说明。

      这里我还是贴出一部分关键的代码,和大家一起学习吧。代码如下:

    (0)将数据记入文件

    [java]  view plain  copy
    1. public static void sortTrie(String filePath) throws IOException {  
    2.         File file = new File(filePath);  
    3.         FileInputStream inputStream = new FileInputStream(file);  
    4.         BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));  
    5.           
    6.         TrieTree tree = new TrieTree("sorting");  
    7.         String readerLine = "";  
    8.         int line = 0;  
    9.         while ((readerLine = reader.readLine()) != null) {  
    10.             tree.insert(readerLine);  
    11.             if (++line % Config.PART_NUMBER_COUNT == 0) {  
    12.                 System.out.println("LINE: " + line);  
    13.             }  
    14.         }  
    15.           
    16.         System.out.println("文件读取完毕");  
    17.           
    18.         writeTrieTree2File(Config.BIGDATA_NUMBER_FILEPATH_SORTED, tree);  
    19.           
    20.         reader.close();  
    21.     }  

    (1)对字典树进行广度优先搜索

    [java]  view plain  copy
    1. public static void sortNumberOrder(String filePath, Node node) throws IOException {  
    2.         Queue<Node> queuing = new LinkedList<Node>();  
    3.         queuing.offer(node);  
    4.           
    5.         while (!queuing.isEmpty()) {  
    6.             Node currentNode = queuing.poll();  
    7.             if (currentNode.isEnd()) {  
    8.                 buffer.append(getNodePath(currentNode) + "\n");  
    9.                 if (++index % 50000 == 0) {  
    10.                     write(filePath, buffer.toString());  
    11.                 }  
    12.             }  
    13.             Node[] children = currentNode.getChildren();  
    14.             for (Node sonNode : children) {  
    15.                 if (sonNode != null) {  
    16.                     queuing.offer(sonNode);  
    17.                 }  
    18.             }  
    19.         }  
    20.     }  
    21.       
    22.     /** 
    23.      * 获得某一节点的上层节点,即前缀字符串 
    24.      * @param node 
    25.      * @return 
    26.      */  
    27.     public static String getNodePath(Node node) {  
    28.         StringBuffer path = new StringBuffer();  
    29.         Node currentNode = node;  
    30.         while (currentNode.getParent() != null) {  
    31.             path.append(currentNode.getName());  
    32.             currentNode = currentNode.getParent();  
    33.         }  
    34.           
    35.         return path.reverse().toString();  
    36.     }  

    小结:

      在大数据的探索还远不止于此。还有很多东西等着我们去了解,去发现,以及创造。

      而对于大量数据的问题,我们可以利用分治来化解它的大,从而可以更方便地去观察全局。也可以使用我们已经学习过的一些数据结构及算法来求解问题。不过随着我们不断地学习,不断地探索,我们可能会感觉到自己学习的一些固有的数据结构和算法并不能完全地解决我们遇到的问题,那么就需要我们的创造力了。

    展开全文
  • 大数据排序算法

    2019-04-16 16:01:49
    一、快速排序(用的比较多) (1) 递归对所有数据分成[a,b)b(b,d]两个区间,(b,d]区间内的数都是大于[a,b)区间内的数 (2) 对(b,d]重复(1)操作,直到最右边的区间个数小于1000个。注意[a,b)区间不用划分 (3) 返回上一...

    一、快速排序(用的比较多)
    (1) 递归对所有数据分成[a,b)b(b,d]两个区间,(b,d]区间内的数都是大于[a,b)区间内的数 
    (2) 对(b,d]重复(1)操作,直到最右边的区间个数小于1000个。注意[a,b)区间不用划分 
    (3) 返回上一个区间,并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分,分为[a2,b2)b2(b2,d2]两个区间,取(b2,d2]区间。如果个数不够,继续(3)操作,如果个数超过1000的就重复1操作,直到最后右边只有1000个数为止。 

    二、分块查找 

    先把100w个数分成100份,每份1w个数。先分别找出每1w个数里面的最大的数,然后比较。找出100个最大的数中的最大的数和最小的数,取最大数的这组的第二大的数,与最小的数比较。。。。

    三、堆排序(针对大数据使用较多)

    先取出前1000个数,维护一个1000个数的最小堆,遍历一遍剩余的元素,在此过程中维护堆就可以了。具体步骤如下: 

    • step1:取前m个元素(例如m=100),建立一个小顶堆。保持一个小顶堆得性质的步骤,运行时间为O(lgm);建立一个小顶堆运行时间为m*O(lgm)=O(m lgm);       
    • step2:顺序读取后续元素,直到结束。每次读取一个元素,如果该元素比堆顶元素小,直接丢弃,如果大于堆顶元素,则用该元素替换堆顶元素,然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素,因此需要维护堆的代价为(N-m)*O(lgm); 
    • 最后这个堆中的元素就是最大的1000个。时间复杂度为O(N lgm)。 

    补充:这个方法的说法也可以更简化一些:
    假设数组arr保存1000个数字,首先取前1000个数字放入数组arr,对于第1001个数字k,如果k大于arr中的最小数,则用k替换最小数,对剩下的数字都进行这种处理。

    排序一般都是拿空间换时间的。


    题目:如何在10亿数中找出前1000大的数?

    小史:我可以用分治法,这有点类似快排中partition的操作。随机选一个数t,然后对整个数组进行partition,会得到两部分,前一部分的数都大于t,后一部分的数都小于t。

    小史:如果说前一部分总数大于1000个,那就继续在前一部分进行partition寻找。如果前一部分的数小于1000个,那就在后一部分再进行partition,寻找剩下的数。

    小史:首先,partition的过程,时间是o(n)。我们在进行第一次partition的时候需要花费n,第二次partition的时候,数据量减半了,所以只要花费n/2,同理第三次的时候只要花费n/4,以此类推。而n+n/2+n/4+...显然是小于2n的,所以这个方法的渐进时间只有o(n)

    (注:这里的时间复杂度计算只是简化计算版,真正严谨的数学证明可以参考算法导论相关分析。)

    半分钟过去了。

    小史一时慌了神。

    他回忆起了之前吕老师给他讲解bitmap时的一些细节。突然有了一个想法。

    小史在纸上画了画。

     

    推排序定义:

    在描述算法复杂度时,经常用到O(1), O(n), O(logn), O(nlogn)来表示对应复杂度程度, 不过目前大家默认也通过这几个方式表示空间复杂度 。那么,O(1), O(n), O(logn), O(nlogn)就可以看作既可表示算法复杂度,也可以表示空间复杂度。

    大O加上()的形式,里面其实包裹的是一个函数f(),O(f()),指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。


    推排序

    堆排序是利用这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。

    堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

    堆排序从1亿个数中找到最小的100个数

    package com.test;
    
    import java.util.Date;
    import java.util.Arrays;
    import java.util.Random;
    
    public class SortClass {
    
    	public static void main(String[] args) {
    		find();
    	}
    
    	public static void find() {//
    		int number = 100000000;// 一亿个数
    		int maxnum = 1000000000;// 随机数最大值
    		int i = 0;
    		int topnum = 100;// 取最大的多少个
    
    		Date startTime = new Date();
    
    		Random random = new Random();
    		int[] top = new int[topnum];
    		for (i = 0; i < topnum; i++) {
    			top[i] = Math.abs(random.nextInt(maxnum));// 设置为随机数
    //				top[i] = getNum(i);
    		}
    
    		buildHeap(top, 0, top.length);// 构建最小堆, top[0]为最小元素
    		for (i = topnum; i < number; i++) {
    
    			int currentNumber2 = Math.abs(random.nextInt(maxnum));// 设置为随机数
    //				int currentNumber2 = getNum(i);
    			// 大于 top[0]则交换currentNumber2 重构最小堆
    			if (top[0] < currentNumber2) {
    				top[0] = currentNumber2;
    				shift(top, 0, top.length, 0); // 构建最小堆 top[0]为最小元素
    			}
    		}
    //		System.out.println(Arrays.toString(top));
    		sort(top);
    		System.out.println("\n"+Arrays.toString(top)+"\n");
    
    		Date endTime = new Date();
    		System.out.println("用了" + (endTime.getTime() - startTime.getTime()) + "毫秒");
    
    	}
    
    	public static int getNum(int i) {
    		return i;
    	}
    
    	// 构造排序数组
    	public static void buildHeap(int[] array, int from, int len) {
    		int pos = (len - 1) / 2;
    		for (int i = pos; i >= 0; i--) {
    			shift(array, from, len, i);
    		}
    	}
    
    	/**
    	 * @param array top数组
    	 * @param from  开始
    	 * @param len   数组长度
    	 * @param pos   当前节点index
    	 */
    	public static void shift(int[] array, int from, int len, int pos) {
    		// 保存该节点的值
    		int tmp = array[from + pos];
    
    		int index = pos * 2 + 1;// 得到当前pos节点的左节点
    		while (index < len)// 存在左节点
    		{
    			if (index + 1 < len && array[from + index] > array[from + index + 1])// 如果存在右节点
    			{
    				// 如果右边节点比左边节点小,就和右边的比较
    				index += 1;
    			}
    
    			if (tmp > array[from + index]) {
    				array[from + pos] = array[from + index];
    				pos = index;
    				index = pos * 2 + 1;
    			} else {
    				break;
    			}
    		}
    		// 最终全部置换完毕后 ,把临时变量赋给最后的节点
    		array[from + pos] = tmp;
    	}
    
    	public static void sort(int[] array) {
    		for (int i = 0; i < array.length - 1; i++) {
    			// 当前值当作最小值
    			int min = array[i];
    			for (int j = i + 1; j < array.length; j++) {
    				if (min > array[j]) {
    					// 如果后面有比min值还小的就交换
    					min = array[j];
    					array[j] = array[i];
    					array[i] = min;
    				}
    			}
    		}
    	}
    }
    

     

    展开全文
  • 大数据排序的几种方法

    千次阅读 2019-01-22 23:32:53
    使用场景举例:对2G的数据量进行排序,这是基本要求。  数据:1、每个数据不大于8亿;2、数据类型位int;3、每个数据最多重复一次。  内存:最多用200M的内存进行操作。  首先对占用的内存进行判断,每个数据不...

    位图法
    位图法是我在编程珠玑上看到的一种比较新颖的方法,思路比较巧妙效率也很高。 
    使用场景举例:对2G的数据量进行排序,这是基本要求。 
    数据:1、每个数据不大于8亿;2、数据类型位int;3、每个数据最多重复一次。 
    内存:最多用200M的内存进行操作。 
    首先对占用的内存进行判断,每个数据不大于8亿,那么8亿是一个什么概念呢。 
    **1 byte = 8 bit(位) 
    1024 byte = 8*1024 bit = 1k 
    1024 k = 8*1024*1024 bit = 1M = 8388608 bit** 
    也就是1M=8388608位 
    而位图法的基本思想就是利用一位代表一个数字,例如3位上为1,则说明3在数据中出现过,若为0,则说明3在数据中没有出现过。所以当题目中出现每个数据最多重复一次这个条件时,我们可以考虑使用位图法来进行大数据排序。 
    那么假如使用位图法来进行这题的排序,内存占用多少呢。由题目知道每个数据不大于8亿,那么我们就需要8亿位,占用800000000/8388608=95M的空间,满足最多使用200M内存进行操作的条件,这也是这题能够使用位图法来解决的一个基础。

    堆排序法
    堆排序是4种平均时间复杂度为nlogn的排序方法之一,其优点在于当求M个数中的前n个最大数,和最小数的时候性能极好。所以当从海量数据中要找出前m个最大值或最小值,而对其他值没有要求时,使用堆排序法效果很好。 
    使用场景:从1亿个整数里找出100个最大的数 
    步骤: 
    1.读取前100个数字,建立最大值堆。(这里采用堆排序将空间复杂度讲得很低,要排序1亿个数,但一次性只需读取100个数字,或者设置其他基数,不需要1次性读完所有数据,降低对内存要求) 
    2、依次读取余下的数,与最大值堆作比较,维持最大值堆。可以每次读取的数量为一个磁盘页面,将每个页面的数据依次进堆比较,这样节省IO时间。 
    3.将堆进行排序,即可得到100个有序最大值。 

    较为通用的分治策略
    分治策略师对常见复杂问题的一种万能的解决方法,虽然很多情况下,分治策略的解法都不是最优解,但是其通用性很强。 
    分治法的核心就是将一个复杂的问题通过分解抽象成若干个简单的问题。 
    应用场景:10G的数据,在2G内存的单台机器上排序的算法 
    我的想法,这个场景既没有介绍数据是否有重复,也没有给出数据的范围,也不是求最大的个数。而通过分治虽然可能需要的io次数很多,但是对解决这个问题还是具有一定的可行性的。 
    步骤: 
    1、从大数据中抽取样本,将需要排序的数据切分为多个样本数大致相等的区间,例如:1-100,101-300… 
    2、将大数据文件切分为多个小数据文件,这里要考虑IO次数和硬件资源问题,例如可将小数据文件数设定为1G(要预留内存给执行时的程序使用) 
    3、使用最优的算法对小数据文件的数据进行排序,将排序结果按照步骤1划分的区间进行存储 
    4、对各个数据区间内的排序结果文件进行处理,最终每个区间得到一个排序结果的文件 
    5、将各个区间的排序结果合并. 
    通过分治将大数据变成小数据进行处理,再合并。
     

    展开全文
  • 大数据排序(10亿量级以上)C语言实现 我们平常对数据进行排序一般用内部方法,即八大排序方法: 直接插入排序 冒泡排序 希尔排序 堆排序 归并排序 堆排序 快速排序 基数排序 这些排序方法默认你们已经掌握了,...

    大数据排序(10亿量级以上)C语言实现

    我们平常对数据进行排序一般用内部方法,即八大排序方法:

    1. 直接插入排序
    2. 冒泡排序
    3. 希尔排序
    4. 堆排序
    5. 归并排序
    6. 堆排序
    7. 快速排序
    8. 基数排序

    这些排序方法默认你们已经掌握了,如果不了解可以在网上搜一下
    首先给出设计的大纲,一共分三步:

    1. 先生成10亿随机数数据
    2. 将10亿数据分成n个小文件并进行排序
    3. 最后将n个小文件进行归并

    这里可能大家就会有疑问了,为什么要分好几个小文件呢?

    这是由于我们的堆栈无法一次性地存入10亿个数据,因此我们要进行外部排序,即分成n个小文件,然后在进行归并合到目标文件中,这样达到排序目的

    主函数代码如下:

    #include <iostream>
    #include<time.h>
    #include"random.h"
    #include"divid.h"
    #include"result.h"
    using namespace std;
    int main()
    {
    	unsigned int begin, end,begin1,begin2,begin3,end1,end2,end3;
    	begin = (unsigned int)time(NULL);
    	begin1 = (unsigned int)time(NULL);
    	random();
    	begin2 = (unsigned int)time(NULL);
    	end1 = (unsigned int)time(NULL);
    	std::cout << "创建文件用时" << (end1 - begin1)<<"s"<<endl;
    	divid();
    	begin3 = (unsigned int)time(NULL);
    	end2 = (unsigned int)time(NULL);
    	std::cout << "第一次排序用时" << (end2 - begin2) << "s"<<endl;
    	result();
    	end3 = (unsigned int)time(NULL);
    	end = (unsigned int)time(NULL);
    	std::cout << "第二次排序加写入文件用时" << (end3 - begin3) << "s"<<endl;
    	std::cout << "总用时为" << (end - begin)<<"s"<<endl;
    }
    
    

    接下来我们要生成随机数,我才用的是scrand函数将当前时间作为种子来随机生成无符号整型数,代码如下(random.h):

    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    
    int random()
    {
    	FILE* fp;
    	fopen_s(&fp, "D:\\算法\\10亿数排序\\main\\data2.txt", "w");
    	if (fp == NULL)
    	{
    		return 0;
    	}
    	long int length = 1000000000;
    	unsigned long int a;
    	srand((unsigned long int)time(NULL));
    	for (int i = 0; i < length; i++)
    	{
    		a = rand();
    		fprintf(fp, "%d ", a);
    		if (i%30==0&&i!=0)
    		{
    			fprintf(fp, "\n");
    		}
    	}
    	fclose(fp);
    	return 0;
    }
    
    

    接下来就到我们的重点了,如何将数据分成n个小文件进行排序,这里我采用的是快速排序,将数据分成500个有序的数据文件这个就不赘述了很简单理解,代码如下(divid.h):

    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include"QuickSort.h"
    #define MAX 1000000000/500
    #define MAX2 500
    
    
    
    int divid()
    {
    	char name[80];
    	double begin,begin1;
    	double end,end1;
    	FILE* fp;
    	int *a;
    	a = new int[MAX+1];
    	int i;
    	int j;
    	fopen_s(&fp, "D:\\算法\\10亿数排序\\main\\data2.txt", "r");
    	if (fp == NULL)
    	{
    		return 0;
    	}
    	
    	std::cout.precision(3);
    	begin1 = (double)time(NULL);
    	for (j = 1; j <= MAX2; j++)
    	{
    
    		sprintf_s(name, "D:\\算法\\10亿数排序\\main\\divideandsort\\%02d.txt", j);
    
    		//读取文件
    		begin = (double)time(NULL);
    		for (i = 1; i < MAX + 1; i++)
    		{
    			fscanf_s(fp, "%d", &a[i]);
    		}
    		end = (double)time(NULL);
    		//std::cout << "读入数据花费的时间:" << (end - begin) << "\n";
    
    		//快速排序
    		begin = (double)time(NULL);
    		QuickSort(a,MAX);
    		end = (double)time(NULL);
    		//std::cout << "快速排序所花费的时间:" << (end - begin) << "\n";
    
    		//写入文件
    		FILE* fp1;
    		fopen_s(&fp1, name, "w");
    		begin = (double)time(NULL);
    		if (fp1 == NULL)
    		{
    			return 0;
    		}
    		for (i = 1; i < MAX; i++)
    		{
    			fprintf_s(fp1, "%d ", a[i]);
    			if (i % 30 == 0 && i != 0)
    			{
    				fprintf(fp1, "\n");
    			}
    		}
    		fprintf_s(fp1, "%d", a[i]);
    		end = (double)time(NULL);
    		fclose(fp1);
    		//std::cout << "写入数据花费的时间:" << (end - begin) << "\n";
    	}
    	end1 = (double)time(NULL);
    	//std::cout << "将十亿数分成十六个文件并排序所花费的时间:" << (end1 - begin1);
    	fclose(fp);
    	delete[] a;
    	return 0;
    }
    

    下面是我自己写的快速排序模板,如果你想用库函数也行。

    #pragma once
    template <class T>
    int Partition(T L[], int low, int high)//一次快排 
    {
    	int pivotkey;
    	L[0] = L[low];
    	pivotkey = L[low];
    	while (low < high)
    	{
    		while (low < high && L[high] >= pivotkey)
    		{
    			--high;
    		}
    		L[low] = L[high];
    		while (low < high && L[low] <= pivotkey)
    		{
    			++low;
    		}
    		L[high] = L[low];
    	}
    	L[low] = L[0];
    	return low;
    
    }
    template <class T>
    void QSort(T L[], int low, int high)//比较函数 
    {
    	int pivotloc;
    	if (low < high)
    	{
    		pivotloc = Partition(L, low, high);
    		QSort(L, low, pivotloc - 1);
    		QSort(L, pivotloc + 1, high);
    	}
    }
    
    template<class T>
    void QuickSort(T L[],int max)//快速排序 
    {
    	QSort(L, 1, max);
    }
    

    我们这样就完成了外部排序,接下来要做的是如何归并,我们首先得开个500大小的数组存每个文件的第一个数据,然后在开一个500的文件流数组便于读数据。

    这里可能会有疑问为什么只能开500个文件流?

    因为文件流最大只能同时开508个,因此我们所用的文件流最大只能开到500,因为正好整除,这也是第二次只分500个文件的原因。

    接下来就是如何保证每次输入到目标文件里是最小的,我这里有三种方法(result.h):
    第一种方案:我们可以每次遍历数组找到最小的然后写到文件里,再上对应文件中读入下一个数据,再遍历,一次类推,代码如下:

    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include <iostream>
    using namespace std;
    #define MAX3 500
    
    //最小值所在数组的下标
    template <class Type> int Min(Type* a, int N)
    {
    	int m = -1;//作为所以文件都读取完毕的标志
    	for (int i = 0; i < N; ++i)
    	{
    		if (a[i] == -1)//此文件已读取完毕,所以-1不作为一个数参与比较
    			continue;
    		if (m == -1 || a[m] > a[i])
    			m = i;
    	}
    	return m;
    }
    
    int result()
    {
    	//合并文件
    	time_t begin, end;
    	FILE* fp = NULL;
    	FILE* FileList[MAX3];
    	errno_t err;
    	if ((err = fopen_s(&fp, "D:\\算法\\10亿数排序\\main\\result.txt", "w")) != 0)//创建数据输出的文件
    	{
    		cout << "File open error!\n";
    		return 0;
    	}
    	for (int i = 0; i < MAX3; i++)
    	{
    		char name[200];
    		sprintf_s(name, "D:\\算法\\10亿数排序\\main\\divideandsort\\%02d.txt", i + 1);
    		fopen_s(&FileList[i], name, "r");
    	}
    	int number[MAX3];//每个文件中最小的元素即第一个元素
    	for (int i = 0; i < MAX3; i++)
    		fscanf_s(FileList[i], "%d", &number[i]);
    	//开始归并
    	while (1)
    	{
    		int min = Min(number, MAX3);
    		cout << number[min] << ends;
    		if (min == -1)
    			break;  //所有文件读取完毕
    		fprintf(fp, "%d ", number[min]);
    		fscanf_s(FileList[min], "%d", &number[min]);
    		if (feof(FileList[min]))
    		{
    			number[min] = -1;  //本文件读取完毕
    		}
    	}
    	for (int i = 0; i < MAX3; i++)
    		fclose(FileList[i]);
    	fclose(fp);
    }
    

    运行结果如下:
    在这里插入图片描述

    我们发现其实并不快,那么是为什么影响其速度呢,那就是每次都得做n次比较,因此比较浪费空间,因此想到了第二种方法。

    第二种方案:既然比较浪费了这么多时间做比较,我们可以第一遍将数组排成有序的每次将数组中的第一个元素写到目标文件中,然后新加的元素做二分插入排序,以此类推,这样最坏是n次比较,最好1次比较,代码如下:

    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include <iostream>
    using namespace std;
    #define MAX1 500+1
    
    struct arr
    {
    	int a;
    	int flag;
    };
    
    void Exchange(arr L[], int i, int j)
    {
    	int temp;
    	temp = L[i].a;
    	L[i].a = L[j].a;
    	L[j].a = temp;
    	temp = L[i].flag;
    	L[i].flag = L[j].flag;
    	L[j].flag = temp;
    }
    
    int partition(arr l[], int low, int high)//一次快排 
    {
    	int pivotkey;
    	Exchange(l, 0, low);
    	pivotkey = l[low].a;
    	while (low < high)
    	{
    		while (low < high && l[high].a >= pivotkey)
    		{
    			--high;
    		}
    		l[low] = l[high];
    		while (low < high && l[low].a <= pivotkey)
    		{
    			++low;
    		}
    		Exchange(l, high, low);
    	}
    	Exchange(l, low, 0);
    	return low;
    
    }
    void qsort(arr l[], int low, int high)//比较函数 
    {
    	int pivotloc;
    	if (low < high)
    	{
    		pivotloc = partition(l, low, high);
    		qsort(l, low, pivotloc - 1);
    		qsort(l, pivotloc + 1, high);
    	}
    }
    
    void quicksort(arr l[], int max)//快速排序 
    {
    	qsort(l, 1, max);
    }
    
    void InsertSort(arr L[],int max)//二分查找法插入排序 
    {
    	int i;
    	for (i=1;i<max-1;i++)
    	{
    		if (L[i].a<=L[i+1].a)
    		{
    			break;
    		}
    		Exchange(L, i, i + 1);
    	}
    }
    
    int result()
    {
    	arr b[MAX1];
    	int i;
    	int flag1;
    	int j;
    	int k=0;
    	int tmp;
    	char name[80];
    	FILE* fp[MAX1];
    	FILE* fp1;
    	fopen_s(&fp1, "D:\\算法\\10亿数排序\\main\\result.txt", "w");
    	if (fp1 == NULL)
    	{
    		return 0;
    	}
    	for (i = 1; i < MAX1; i++)
    	{
    		sprintf_s(name,"D:\\算法\\10亿数排序\\main\\divideandsort\\%02d.txt", i);
    		fopen_s(&fp[i], name, "r");
    		if (fp[i] == NULL)
    		{
    			return 0;
    		}
    		
    		fscanf_s(fp[i], "%d", &b[i].a);
    		b[i].flag = i;
    	}
    	quicksort(b,MAX1);
    	flag1 = 1;
    	j = 1;
    	while (flag1)
    	{
    		flag1 = 0;
    		fprintf_s(fp1, "%d ", b[1].a);
    		//cout << b[1].a<<ends;
    		if (j == 30)
    		{
    			fprintf_s(fp1, "\n");
    			j = 1;
    		}
    		else
    		{
    			j++;
    		}
    		tmp = b[1].flag;
    		if (tmp > 0)
    		{
    			if (!feof(fp[tmp]))
    			{
    				fscanf_s(fp[tmp], "%d", &b[1].a);
    				flag1 = 1;
    			}
    			else
    			{
    				for (i = 1; i < MAX1; i++)
    				{
    					if (fp[i] != NULL)
    					{
    						fscanf_s(fp[i], "%d", &b[1].a);
    						b[1].flag = i;
    						break;
    						flag1 = 1;
    					}
    				}
    				if (!flag1)
    				{
    					break;
    				}
    			}
    			InsertSort(b,MAX1);
    		}
    	}
    	for (i = 2; i < MAX1; i++)
    	{
    		fprintf_s(fp1, "%d ", b[i].a);
    		//cout << b[1].a<<ends;
    	}
    	fclose(fp1);
    	for  ( i = 1;  i < MAX1;  i++)
    	{
    		fclose(fp[i]);
    	}
    	return 0;
    }
    

    运行结果为:
    在这里插入图片描述
    从运行结果发现性能提高了,但是并未提高太多(这是最好的一次运行结果),那么是为什么导致的呢,这是由于虽然比较少了,但是数据交换次数比较多,这样会占很多的时间和空间,因此笔者做了很多构想,最后想出第三种方案。

    第三种方案:那么我们如何将前两种方法综合起来呢,既不做如此多的比较,又使用较少的交换次数,其实这个是最关键的思想,最终我想到了用堆排序的方法,这样500大小的数组最多比较27次,做1次交换,性能大大提高,当我们其中的一个文件读完之后,我们可以将数组头和尾交换,然后数组长度减一,直到数组有效长度为0,代码如下:

    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include <iostream>
    using namespace std;
    #define MAX1 (500+1)
    
    struct arr
    {
    	int a;
    	int flag;
    };
    
    //inline void Exchange(arr L[], int i, int j)
    //{
    //	int temp;
    //	temp = L[i].a;
    //	L[i].a = L[j].a;
    //	L[j].a = temp;
    //	temp = L[i].flag;
    //	L[i].flag = L[j].flag;
    //	L[j].flag = temp;
    //}
    
    inline void HeepAdjust(arr L[], int s, int m)//堆排序的调整 
    {
    	arr rc;
    	int j;
    	rc.a = L[s].a;
    	rc.flag = L[s].flag;
    	for (j = 2 * s; j < m ; j *= 2)
    	{
    		if (j + 1 < m && L[j].a > L[j + 1].a)
    		{
    			++j;
    		}
    		if (!(rc.a > L[j].a))
    		{
    			break;
    		}
    		//Exchange(L, s, j);
    		int temp;
    		temp = L[s].a;
    		L[s].a = L[j].a;
    		L[j].a = temp;
    		temp = L[s].flag;
    		L[s].flag = L[j].flag;
    		L[j].flag = temp;
    		s = j;
    	}
    	L[s].a = rc.a;
    	L[s].flag = rc.flag;
    }
    
    int result()
    {
    	arr b[MAX1];
    	int i;
    	int j;
    	int l;
    	int tmp;
    	char name[80];
    	FILE* fp[MAX1];
    	FILE* fp1;
    	fopen_s(&fp1, "D:\\算法\\10亿数排序\\main\\result.txt", "w");
    	if (fp1 == NULL)
    	{
    		return 0;
    	}
    	for (i = 1; i < MAX1; i++)
    	{
    		sprintf_s(name, "D:\\算法\\10亿数排序\\main\\divideandsort\\%02d.txt", i);
    		fopen_s(&fp[i], name, "r");
    		if (fp[i] == NULL)
    		{
    			return 0;
    		}
    
    		fscanf_s(fp[i], "%d", &b[i].a);
    		b[i].flag = i;
    	}
    	for (i = MAX1/2;i > 0 ; --i)
    	{
    		HeepAdjust(b, i,MAX1);
    	}
    	j = 1;
    	l = MAX1;
    	while (1)
    	{
    		fprintf_s(fp1, "%d ", b[1].a);
    		//cout << b[1].a << ends;
    		if (j == 30)
    		{
    			fprintf_s(fp1, "\n");
    			j = 1;
    		}
    		else
    		{
    			j++;
    		}
    		tmp = b[1].flag;
    		if (tmp > 0)
    		{
    			if (!feof(fp[tmp]))
    			{
    				fscanf_s(fp[tmp], "%d", &b[1].a);
    			}
    			else
    			{
    				//Exchange(b, 1, l);
    				int temp;
    				temp = b[1].a;
    				b[1].a = b[l-1].a;
    				b[l-1].a = temp;
    				temp = b[1].flag;
    				b[1].flag = b[l-1].flag;
    				b[l-1].flag = temp;
    				l--;
    			}
    			if (l<=1)
    			{
    				break;
    			}
    			HeepAdjust(b, 1, l);
    		}
    	}
    	fclose(fp1);
    	for (i = 1; i < MAX1; i++)
    	{
    		fclose(fp[i]);
    	}
    	return 0;
    }
    

    运行结果为:
    在这里插入图片描述

    从运行结果可以看出此方法的性能是最好的,综合了前两种方法的特点,既没有比较太多的次数,也没有做太多次的数据交换,所以整体性能最好

    至此我们就将10亿随机数排成有序的了。

    源代码已上传github:源代码

    展开全文
  • 大数据排序算法总结

    千次阅读 2016-06-29 10:51:25
    5、大数据排序的实现代码, 理论上支持几百亿没问题吧 6、大文件内数据排序问题:采用文件映射内存技术 7、堆排序 海量数据求前N大的值 8、大数据排序相关 9、【参考】给大数据量的磁盘文件排序 10、
  • 大数据排序方案---外排序介绍

    千次阅读 2017-04-25 01:19:09
    我们一般提到排序都是指内排序,比如快排,堆排序,归并排序等,所谓内排序就是能把所有待排序的数据外进内存之中,比如,一个数组之中。但是如果文件太大,文件中的所有数据不能一次性的放入内存之中,快排,堆排序...
  • !...查询语句如下: select ORG_ID , rn from ( ... 数据量小的时候rn和id的排序是一致的,都是ASC,但是当数据量变到足够大的时候 rn变成乱序的了,这到底是什么原因?还有就是分页查询应该order by rn ?
  • 大数据排序问题

    2019-10-04 15:50:49
    一个文件中有9亿条不重复的9位整数,对这个文件中数字进行排序 直接想法 9亿条(9e8)数据,每个数据能用int存储 因此所需要内存 9e8x4B = 3.6e9B = 3.6GB,这是装载所需要的 排序复杂度一般都是nlogn 因此需要的内存...
  • SQL Server 中虽然有 ORDER BY NewID() 方法,但对于数据量比较大的结果集来说,排序那慢的可不是一星半点。 微软官方给了一种方案,https://msdn.microsoft.com/en-us/library/cc441928.aspx 示例如下: SELECT ...
  • bitmap实现大数据排序和去重

    千次阅读 2018-02-28 21:49:26
    void sort(vector<int> &a) // 将元素存入bitmap数组中,元素其实自动排序,只要bit == 1,即说明有此元素。 { unsigned int bitmap[SIZE]; cleanAll(bitmap); for (int i = 0; i (); i++) { set(bitmap, a...
  • 1、对于很大的数据量,考虑多级索引和桶排序; 2、建立一个足够大的bit数组当作hash表,以bit数组的下标来表示一个整数,以bit位中的0或1来表示这个整数是否在这个数组中存在,适用于无重复原始数据的搜索,原来...
  • Hadoop MapReduce做大数据排序

    千次阅读 2014-10-31 17:48:57
    1. 我们知道mapreduce天生适合作排序,由于他有一个shuffer的过程,当数据量很少的时候我们可以把reduce的num设置成1来进行排序,但是如果数据量很大,在一个reduce上处理不过来或者处理时间太长,那么我们就需要...
  • 1、问题 问题提出: M(如10亿)个int整数,只有其中N个数重复出现过,读取到内存中并将重复的整数删除。 2、解决方案 问题分析: ...我们考虑大数据的情况:例如在java语言下,对10亿个int类型数据...
  • 之前写过一篇八种排序算法的博客,不过都是基于小数据量进行的排序,没有像这篇这样做大数据排序。文末会放出链接。 桶排序(Bucket sort) 首先,我们来看桶排序。桶排序,顾名思义,会用到“桶”,核心思想是将要...
  • 1. 概述 排序算法是计算机技术中最基本的算法,许多复杂算法都会用到排序。... 上海尚学堂大数据培训组原创,陆续有大数据相关技术文章奉上,请多关注! 2. 几个概念 (1)排序稳定:如果两个数相同,对他...
  • 大数据排序或取重或去重相关问题

    千次阅读 2016-08-11 12:57:29
    方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。  方案3:采用局部淘汰法。选取前100个元素,并...
  • 中间件高效快速大数据排序A piece of middleware is a function that hooks into the routing process, performing an arbitrary operation at some point in the chain (depending on what we want it to do). ...
  • 大数据排序处理

    千次阅读 2014-04-27 10:55:01
    1. Top K算法:使用堆排序算法+大顶堆+10个元素的数组。 2. IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理;可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%
  • 对Oracle的数据进行排序,在数据量比较大的情况下,往往性能会非常低,由于排序需要耗费大量存储空间,一旦涉及磁盘排序,就会有导致效率低下,为了提供其排序效率,经常需要对数据库的相关参数进行调整,但是也无法...
  • 现有8G的数据,其中都是无符号的int型,现有1G内存,如何对这些数据排序。 答: 首先建立一个struct将数据包起来,结构体包含数据的值及它出现的次数。需要建立一个大根堆,每个大根堆的一个数据项是这个结构体,...
  • 大数据怎么排序

    2017-02-15 14:40:00
    http://www.importnew.com/23450.html 转载于:https://www.cnblogs.com/zjf6666/p/6401369.html
  • 阿里中间件笔试题---大数据排序

    千次阅读 2019-04-04 18:05:53
    需要,写一个程序,将所有数字排序,分为10个文件输出,如0号文件包含前1000万个数字,1号文件文件包含第1千万-2千万之间的数字,依次类推。 限制:如果使用java,-Xmx需要设置为32MB;其它语言也需限制内存为32MB...
  • 大数据排序合并

    2014-08-17 18:03:48
    * 大数据排序合并 * * @param args */ public static void main(String[] args) throws IOException { // 写入文件的路径 String filePath = "d:\\file_dir"; // 切分文件的路径 String ...
  • 我有10亿的用户数据放在节点中;key,value格式:姓名、金额 数据场景:这10亿为交易支付数据,可能存在重复支付的数据 计算设备:一台物理机、配置不限、需要运用nosql中间件来处理这10亿数据。...
  • 要求对28G的数据排序,数据的格式如下: id time 要求按时间升序排序 已有的资源为64G内存,32核的服务器一台,需要在一个晚上(8小时)内跑出排序结果。 一个直观的解法就是把数据全部加载进内存,然而实际操作并不...
  • mapreduce的排序机制之total排序 (1)设置一个reduce task ,全局有序,但是并发度太低,单节点负载太大 (2)设置分区段partitioner,设置相应数量的reduce task,可以实现全局有序,但难以避免数据分布不...
  • 转载大数据排序 很好的思想

    万次阅读 2009-09-09 14:43:00
    http://www.cnblogs.com/songsu/articles/1457666.html 算法的力量:位运算在排序与...一般解题思路: 1、将数据导入到内存中 2、将数据进行排序 (比如插入排序、快速排序) 3、将排序好的数据存入文件难题: 一个整

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,006
精华内容 40,002
关键字:

大数据排序