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)

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。