大数据算法：对5亿数据进行排序
0.前言：
在大数据研究的路上，咱们总要对一些很大的数据进行各类各样的操做。好比说对数据排序，好比说对数据统计，好比说对数据计算。而在大量的数据面前，咱们老是一筹莫展，由于咱们没法在限定时间的状况下，在效率上作到让人满意，也没法在限定空间的状况下，可以快速解决问题。可能咱们在一些平常的开发过程当中，没有遇到过这些问题。不过，如今是时候来考虑一下这样的问题了。由于，如今正值大数据的时代。java
在本文中我会用三种方法，从两个方面来讲明如何解决对5亿数据进行排序工做。node
1.版本说明
商业转载请联系做者得到受权，非商业转载请注明出处。
本文做者：Q-WHai
发表日期： 2015年10月24日
本文连接：https://blog.csdn.net/lemon_tree12138/article/details/48783535
来源：CSDN
更多内容：分类 >> 算法与数学算法
2.思路分析：
拿到这样的一个问题，你的第一感受是什么？冒泡排序？选择排序？插入排序？堆排？仍是快排？可能你的想法是个人内存不够。的确，这么大的一个数据量，咱们的内存的确不够。由于单是5亿的整数数据就有3.7个G(别说你是壕，内存大着呢)。既然内存不够，那么咱们要怎么来解决呢？缓存
要知道咱们一步作不了的事，两步总能作到。那么咱们就来尝试第一步作一些，剩下的一些就等会再来搞定吧。基于这样的思路，就有下面的一个解题方法——分治！数据结构
1.分治——根据数据存在文件中的位置分裂文件到批量小文件中app
相对于朴素的排序，这是一种比较稳妥的解决方法。由于数据量太大了！咱们不得不将大事化小，小事化了。数据结构和算法
这里咱们的作法是每次读取待排序文件的10000个数据，把这10000个数据进行快速排序，再写到一个小文件bigdata.part.i.sorted中。这样咱们就获得了50000个已排序好的小文件了。学习
在有已排序小文件的基础上，我只要每次拿到这些文件中当前位置的最小值就OK了。再把这些值依次写入bigdata.sorted中。大数据
2.分治——根据数据自身大小分裂文件到批量小文件中ui
按照数据位置进行分裂大文件也能够。不过这样就致使了一个问题，在把小文件合并成大文件的时候并不那么高效。那么，这里咱们就有了另外一种思路：咱们先把文件中的数据按照大小把到不一样的文件中。再对这些不一样的文件进行排序。这样咱们能够直接按文件的字典序输出便可。
3.字典树
关于字典树的基本使用，你们能够参见本人的另外一篇博客：《数据结构：字典树的基本使用》
基于《数据结构：字典树的基本使用》这篇博客中对字典序的讲解，咱们知道咱们要作就是对字典树进行广度优先搜索。
3.结构设计图：
4.代码分析：
0.分治
(0)分割大文件
此步对大文件的分割是按序进行的，这样咱们就能够确保数据的离散化，不会让一个小文件中的数据不少，一个小文件的数据不多。
public static void splitBigFile2PartBySerial(String filePath, String partPath) throws IOException {
File file = new File(filePath);
FileInputStream inputStream = new FileInputStream(file);
BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));
StringBuffer buffer = new StringBuffer();
String readerLine = "";
int line = 0;
while ((readerLine = reader.readLine()) != null) {
buffer.append(readerLine + " ");
if (++line % Config.PART_NUMBER_COUNT == 0) {
sortStringBuffer(buffer);
int splitLine = line / Config.PART_NUMBER_COUNT;
write(partPath.replace("xxx", "" + splitLine), buffer.toString());
buffer.setLength(0);
System.out.println("SPLIT: " + splitLine);
}
}
reader.close();
}
(1)排序
即便是已经切割成小份的了，不过每一个小文件中的数据集仍然有50000个。由于50000个数据也不是一个小数据，在排序的过程当中，也会有一些讲究，全部这里咱们使用的是快排。以下：
public static void sortStringBuffer(StringBuffer buffer) {
String[] numberTexts = buffer.toString().split(" ");
buffer.setLength(0);
int[] numbers = new int[numberTexts.length];
for (int i = 0; i < numberTexts.length; i++) {
numbers[i] = Integer.parseInt(numberTexts[i]);
}
int[] sorted = QKSort.quickSort(numbers);
for (int i = 0; i < sorted.length; i++) {
buffer.append(sorted[i] + "\n");
}
}
(2)合并
在合并的时候，咱们要明确一个问题。虽然咱们的单个小文件已经有序，不过咱们还并不知道总体的顺序。好比：
文件1:1 2 4 6 9 34 288
文件2:4 5 6 87 99 104 135
上面的两个文件虽然每一个文件内部已经有序，不过总体来讲，是无序的。对于在单个文件有序的基础上，咱们能够作一些事情。咱们能够把每一个文件中的数据当作是一个队列，咱们老是从队列的首部开始进行出队(由于队列的头部老是最小的数)。这样，咱们就把问题转化成从N个小文件中依次比较，获得最小的结果并记入文件(固然，咱们不能够生成一个数就写一次文件，这样过低效了，咱们可使用一个变量缓存这此"最小值"，在累计到必定数量以后再一次性写入。再清空变量，循环反复，直到文件所有写入完毕)。
public static void mergeSorted(String dirPath) throws NumberFormatException, IOException {
long t = System.currentTimeMillis();
File dirFile = new File(dirPath);
File[] partFiles = dirFile.listFiles();
FileInputStream[] inputStreams = new FileInputStream[partFiles.length];
BufferedReader[] readers = new BufferedReader[partFiles.length];
int[] minNumbers = new int[partFiles.length];
for (int i = 0; i < partFiles.length; i++) {
inputStreams[i] = new FileInputStream(partFiles[i]);
readers[i] = new BufferedReader(new InputStreamReader(inputStreams[i]));
minNumbers[i] = Integer.parseInt(readers[i].readLine());
}
int numberCount = Config.TOTAL_NUMBER_COUNT;
while (true) {
int index = Tools.minNumberIndex(minNumbers);
System.out.println(minNumbers[index]);
write(Config.BIGDATA_NUMBER_FILEPATH_SORTED, minNumbers[index] + "\n");
minNumbers[index] = Integer.parseInt(readers[index].readLine());
if (numberCount-- <= 0) {
break;
}
}
System.err.println("TIME: " + (System.currentTimeMillis() - t));
for (int i = 0; i < partFiles.length; i++) {
inputStreams[i].close();
readers[i].close();
}
}
注：这里关于分治的算法，我就只提供一种实现过程了。可能从上面的说明中，你们也意识到了一个问题，若是咱们把大文件中的数据按照数值大小化分到不一样的小文件中。这样会有一个很致命的问题，那就是可能咱们的小文件会出现两极分化的局面，即有一部分文件中的数据不多，有一部分小文件中的数据不少。因此，这里我就再也不提供实现过程，在上面有所说明，只是想说咱们在解决问题的时候，可能会有不少不一样的想法，这些想法都很好，只是有时咱们须要一个最优的来提高逼格(^_^)。
1.字典树
由于咱们知道字典树是能够压缩数据量的一种数据结构，尤为是针对那么使用的字符串个数有限(好比：'0','1','2','3','4','5','6','7','8','9')，并总体数量不少的状况。由于咱们能够可让同一个字符重复使用屡次。好比："123456789"和"123456780"其实只使用了'0'-'9'这10个字符而已。关于字典树的实现，我想是很简单的一种方法。若是你仍是感受有些朦胧和模糊的话，就请参见本人的另外一篇博客《数据结构：字典树的基本使用》，在那一篇博客中，我有很详细地介绍对字典树的各类基本操做及说明。
这里我仍是贴出一部分关键的代码，和你们一块儿学习吧。代码以下：
(0)将数据记入文件
public static void sortTrie(String filePath) throws IOException {
File file = new File(filePath);
FileInputStream inputStream = new FileInputStream(file);
BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));
TrieTree tree = new TrieTree("sorting");
String readerLine = "";
int line = 0;
while ((readerLine = reader.readLine()) != null) {
tree.insert(readerLine);
if (++line % Config.PART_NUMBER_COUNT == 0) {
System.out.println("LINE: " + line);
}
}
System.out.println("文件读取完毕");
writeTrieTree2File(Config.BIGDATA_NUMBER_FILEPATH_SORTED, tree);
reader.close();
}
(1)对字典树进行广度优先搜索
public static void sortNumberOrder(String filePath, Node node) throws IOException {
Queue<Node> queuing = new LinkedList<Node>();
queuing.offer(node);
while (!queuing.isEmpty()) {
Node currentNode = queuing.poll();
if (currentNode.isEnd()) {
buffer.append(getNodePath(currentNode) + "\n");
if (++index % 50000 == 0) {
write(filePath, buffer.toString());
}
}
Node[] children = currentNode.getChildren();
for (Node sonNode : children) {
if (sonNode != null) {
queuing.offer(sonNode);
}
}
}
}
/**
* 得到某一节点的上层节点，即前缀字符串
* @param node
* @return
*/
public static String getNodePath(Node node) {
StringBuffer path = new StringBuffer();
Node currentNode = node;
while (currentNode.getParent() != null) {
path.append(currentNode.getName());
currentNode = currentNode.getParent();
}
return path.reverse().toString();
}
5.小结：
在大数据的探索还远不止于此。还有不少东西等着咱们去了解，去发现，以及创造。
而对于大量数据的问题，咱们能够利用分治来化解它的大，从而能够更方便地去观察全局。也可使用咱们已经学习过的一些数据结构及算法来求解问题。不过随着咱们不断地学习，不断地探索，咱们可能会感受到本身学习的一些固有的数据结构和算法并不能彻底地解决咱们遇到的问题，那么就须要咱们的创造力了。