10亿个字符串的排序问题
一、问题描述
有一个大文件,里面有十亿个字符串,乱序的,要求将这些字符串以字典的顺序排好序
?
二、解决思路
? ? ? ? 将大文件切割成小文件,每个小文件内归并排序;
? ? ? ? 对所有的小文件进行归并排序——多重归并排序
?
三、解决方案
3.1?模拟产生10亿个随机字符
public static void generateDate() throws IOException { BufferedWriter writer = new BufferedWriter(new FileWriter(ORIGINALPATH)); Random random = new Random(); StringBuffer buffer = new StringBuffer( "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"); int range = buffer.length(); int length = 1; for (int i = 0; i < BIGDATALENGTH; i++) { StringBuffer sb = new StringBuffer(); length = random.nextInt(20)+1; //System.out.println("length--->"+length); for (int j = 0; j < length; j++) { //System.out.println("j--->"+j); sb.append(buffer.charAt(random.nextInt(range))); } System.out.println("sb---->"+sb); writer.write(sb.toString() + "\n"); } writer.close(); }
?
3.2?对大文件进行切割
/** * 将原始数据分成几块 并排序 再保存到临时文件 * @throws IOException */ public static void splitData() throws IOException { @SuppressWarnings("resource") BufferedReader br = new BufferedReader(new FileReader(ORIGINALPATH)); tempFiles = new File[BIGDATALENGTH / TEMPFILELENGTH];//将会产生的临时文件列表 for (int i = 0; i < tempFiles.length; i++) { tempFiles[i] = new File(TEMPFILEPATH + "TempFile" + i + ".txt"); BufferedWriter writer = new BufferedWriter(new FileWriter(tempFiles[i])); HashMap<Integer,String> hashMap = new HashMap<Integer,String>();//未排序 //每次读出TEMPFILELENGTH个文件 保存到smallLine中 for (int j = 1; j <= TEMPFILELENGTH; j++) { String text = null; if ((text = br.readLine()) != null) { hashMap.put(j, text); } } hashMap = MergeSort.sort(hashMap); for(int k=1; k<=TEMPFILELENGTH; k++){ writer.write(String.valueOf(hashMap.get(k)) + System.getProperty("line.separator")); //System.getProperty("line.separator")相当于\n } writer.close(); } }
?
3.3?对小文件进行递归归并?
/** * 多路归并排序 * @param files * @throws IOException */ public static void multiWaysMergeSort(String[] files) throws IOException { System.out.println("归并文件-----第 "+mergeSortCount+" 次-----"); //当最后只有一个文件的时候 数据已经排序成功 直接复制保存到结果文件 if (files.length == 1) { String lastFilePath = LASTFILEPATH + LASTFILENAME; copyFile(files[0], lastFilePath, false); //deleteFile(files[0]); return; } for (int i = 0; i < files.length; i+=2) { //开始合并两个相邻的文件 所以一次跳两个 if (i == files.length - 1) { //这时候已经只剩下最后一个文件了 不需要合并 本趟归并结束 renameFile(files[i], i); break; } //将br1 和 br2 写入到Write BufferedReader br1 = new BufferedReader(new FileReader(files[i])); BufferedReader br2 = new BufferedReader(new FileReader(files[i + 1])); BufferedWriter writer = new BufferedWriter(new FileWriter(TEMPFILEPATH + "last_" + mergeSortCount + "_" + i + ".txt")); String s1 = br1.readLine(); String s2 = br2.readLine(); while (s1 != null || s2 != null) { if (s1 != null && s2 != null) { //都不为空 才有比较的必要 int mergeResult = s1.compareTo(s2); if (mergeResult > 0) {//s1在s2后面 writer.write(s2); writer.write(System.getProperty("line.separator")); s2 = br2.readLine(); } if (mergeResult == 0) {//s1=s2 writer.write(s1); writer.write(System.getProperty("line.separator")); writer.write(s2); writer.write(System.getProperty("line.separator")); //System.out.println("write time : " + writeTime++); s1 = br1.readLine(); s2 = br2.readLine(); } if (mergeResult < 0) {//s1在s2前面 writer.write(s1); writer.write(System.getProperty("line.separator")); s1 = br1.readLine(); } } if (s1 == null && s2 != null) { writer.write(s2); writer.write(System.getProperty("line.separator")); s2 = br2.readLine(); } if (s2 == null && s1 != null) { writer.write(s1); writer.write(System.getProperty("line.separator")); s1 = br1.readLine(); } } br1.close(); br2.close(); // deleteFile(files[i]); // deleteFile(files[i + 1]); writer.close(); } mergeSortCount++; multiWaysMergeSort(getTempFiles("last_" + (mergeSortCount-1) + "_")); }
?
3.4?运行结果分析
①生成10亿个随机字符串,时间太久了,,字符串长度随机在[1,20]之间时,文件大小大概在10.7?GB?(11,500,161,591?字节)
②?切割成小文件,小文件内归并排序,每个文件内的数据100万条时,随机选取五个排序时间如下:
一共发生了410832612?次对比一共发生了?899862656?次交换执行时间为3545毫秒
一共发生了429506513?次对比一共发生了?940765504?次交换执行时间为3512毫秒
一共发生了448181315?次对比一共发生了?981668352?次交换执行时间为3497毫秒
一共发生了466856137?次对比一共发生了?1022571200?次交换执行时间为3497毫秒
一共发生了485530473?次对比一共发生了?1063474048?次交换执行时间为3981毫秒
总共1000个文件切割耗时为
切割小文件所用时间--->4341734ms--->4341.734s--->72.36m--->1.206h
③??小文件递归归并,1000个文件,
共发生了10次归并,
产生临时文件总共1999个,
总大小为127.8?GB?(137,201,789,278?字节),
产生结果文件11.6?GB?(12,500,161,591?字节)
比源文件多了10亿个字节......
总耗时为--->7374129ms--->7374.129s--->122.9m--->2.048h
不得不提的是,最后执行结果成功,也不枉我苦苦等待
四、相关技术
4.1?归并排序
排序原理不多介绍,各种到处都有,如果一时不记得,看下面的原理图。秒懂。
??
? ? 4.2?文件读写
本程序很重要的一点就是对于文件的读写,Buffer的文件读写可以很大程度的改善速率
写操作:
BufferedWriter?writer?=?new?BufferedWriter(new?FileWriter(PATH));
writer.write("hhf\n");
读操作:
BufferedReader?br?=?new?BufferedReader(new?FileReader(PATH));
text?=?br.readLine()
?
五、关于优化
5.1分小文件时优化
前提:数据均匀,保证每个小文件大小不会超过内存的容量
处理:在分数据到小文件时,按字符串按首字母将其分到指定文件中,如A-C分配到1.txt,D-F分配到2.txt.......
优点:只需要小文件内数据排序,排序号后,即可将1.txt、2.txt、3.txt直接连接起来,极大的缩短了归并时间,相当于把递归归并变成了文件连接而已
缺点:前提不是很容易把握,若有一个小文件内的数据量大于内存的大小,则排序失败,存在一定的风险
?
5.2小文件内排序时优化
前提:保证每个小文件内数据量比较不是特别的大
处理:将小文件内的数据进行快速排序
优点:快排的时间效率是高于归并的
以下是测试数据
排序数量级??10 ?1000 ?100000
归并排序7ms ?71ms ?3331ms
快速排序6ms ?52ms ?java.lang.StackOverflowError
缺点:缺点已经显示在测试数据内了,小文件内的数据量过大就可能导致当前线程的栈满
(附上源代码工程:Merge.zip)
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。