`
java--hhf
  • 浏览: 308731 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

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)

  • 大小: 231.8 KB
9
2
分享到:
评论
10 楼 QuarterLifeForJava 2014-12-17  
是62说错了~
9 楼 QuarterLifeForJava 2014-12-17  
一共“0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”82个字符,我觉得是不是可以采用空间换时间的桶排序算法来实现,开辟62(10+26+26)个空间的数组长度。另外分割文件和各单文件排序等操作,也可以利用多核的优点,多线程处理。
8 楼 lvwenwen 2014-12-16  
mark 
7 楼 lienhe 2014-12-16  
大文件分小文件时是不是可以使用字符来分而不是直接分,这样文件本身就有序了,避免之后的归并操作,如:
假设字符串由"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"这些字符组成,
    1. 按首字母分组,分为62组
    2. 按次一位字符分组,每组再分为62组,如果有组达到阀值(如100),跳4
    3. 递归2,直到所有都有标记,跳5
    4. 排序本组并标记本组不再继续递归
    5. 按顺序合并文件,结束
(没有实际,只是一些想法)
   
6 楼 易水寒vn 2014-12-16  
先对10亿字符串做索引,再对索引进行排序,不知是否会更快一些
5 楼 james_lover 2014-12-15  
zoven 写道
是在什么场景下会有需要实现类似的排序,谢谢

数据库引擎里,access日志统计里。比如按IP统计,按时间统计,按URL统计
4 楼 j781215081 2014-12-15  
System.out.println("sb---->"+sb); 好多sb啊
3 楼 nishilaiyuan 2014-12-15  
2 楼 zoven 2014-12-15  
是在什么场景下会有需要实现类似的排序,谢谢
1 楼 雨一直下 2014-12-14  

相关推荐

    C语言中压缩字符串的简单算法小结

    应用中,经常需要将字符串压缩成一个整数,即字符串散列。比如下面这些问题: (1)搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。请找出最热门的10个检索串。 ...

    java对大数据量文件内容的多线程读取和排序.pdf

    - 创建一个10亿行的随机文本文件,每行包含超过100个字符。这可以通过生成随机字符串并写入文件来实现。可以使用Java的`Random`类生成随机字符串,然后使用`BufferedWriter`写入文件。 2. **多线程读取**: - ...

    《C 程序员面试算法宝典》读书笔记模板x.pptx

    3. 如何判断两个字符串是否为换位字符串 4. 如何判断两个字符串的包含关系 5. 如何对由大小写字母组成的字符数组排序 6. 如何消除字符串的内嵌括号 7. 如何判断字符串是否是整数 8. 如何实现字符串的匹配 9. 如何求...

    NOIP2007程序

    这个问题要求选手统计一系列不超过15亿(1.5*10^9)的自然数出现的次数,并按升序输出。输入文件`count.in`包含自然数的数量`n`,以及`n+1`行的自然数。输出文件`count.out`则应按照自然数及其出现次数输出。数据...

    经典算法题_嵌入式-常用知识&面试题库_大厂面试真题.doc

    8. 求出 10 亿个杂乱无章的数中的前 1000 大的数 知识点:堆、BIT manipulation、文件读写 解决方案:使用堆来存储前 1000 个数,然后使用 BIT manipulation 来标识每个数的存在与否,最后使用文件读写来存储结果。 ...

    孙浩天的ACM模板1

    这个问题是寻找数组中连续子数组的最大和。有多种解决方案,如Kadane's算法,可以在一次遍历中找到最大子数组的和。 6. **素数筛选**: 筛选1000亿以内的素数,通常使用埃拉托斯特尼筛法(Sieve of Eratosthenes...

    2011年最新面试笔试题

    1. 对每个字符串进行排序,然后比较排序后的字符串是否相同。 2. 使用哈希表来存储字符串的字符频率分布,然后比较两个字符串的频率分布是否一致。 ### 知识点四:DNS Cache结构设计 #### 问题描述 设计一个DNS...

    burrow wheeler transformation

    波拉克-惠勒变换(Burrow Wheeler Transformation,BWT)是一种在生物信息学中广泛使用的字符串排序算法,其主要用途在于序列比对,特别是在处理由新一代DNA测序技术产生的大量短读序列时。短读序列是长度较短的DNA...

    2009-2013百度校园招聘笔试题

    这实际上是一个字符串排序问题,需要自定义比较函数,用于比较两个字符串连接起来后的大小,从而确定正确的排序方式。 **知识点6:贪心算法** 解决此问题的一个常用方法是贪心算法,每次选择当前状态下最优的选择。...

    微盟算法工程师岗.pdf

    面试还提到了大规模数据处理的问题,如何对10亿个词语进行排序并找出最常使用的100个,这通常需要运用到高效的数据结构和排序算法,如哈希表和堆排序等。 三面则结合了自我介绍和项目经验,以及更深入的技术问题,...

    大厂面试系列二.pdf

    找出给定字符串对应的序号问题,需要根据序列的编号规则来确定字符串的编号,这可能涉及排序算法或其他特定的规则。 找出第k大的数字所在的位置,可以通过调整排序算法来实现,例如快速选择算法可以在平均O(n)时间...

    海量数据处理:十道面试题与十个海量数据处理方法总结

    - 一种树形数据结构,特别适合于字符串的搜索和排序。 - 可以有效地统计词频或查询串的出现次数。 5. **外部排序**: - 当数据量过大无法完全加载到内存时,可以使用外部排序算法。 - 包括外部归并排序等,适用...

    个人整理部分年度百度笔试题

    函数filter_ansi()可以使用双指针法,一个指针处理原始字符串,另一个指向新字符串,只将GBK编码的汉字复制到新字符串中。 4. 芯片测试问题 - 知识点:二分查找,最小化比较次数 - 解决方案:可以使用二分查找的...

    大数据的一些面试题.pdf

    例如,要统计100台电脑上的数据Top10,MapReduce可以有效地解决这个问题。 综合这些知识点,面试时可能会遇到的具体问题包括:在内存有限的情况下,如何统计大量数据的不重复元素、计算中位数、建立索引、实现倒排...

    沈阳建筑大学 810C语言程序设计

    - 使用循环遍历字符串中的每个字符,判断奇偶数是否交替出现。 - 输出判断结果。 #### 13. 工业总产值预测 - **知识点**: 数学模型预测。 - **实现思路**: - 设初始产值为200亿,年增长率4.5%。 - 使用公式`V =...

    C语言面试题(经典)

    3. **最大堆**:维护一个大小为10的最大堆,用于存储出现频率最高的10个字符串。 4. **更新堆**:遍历哈希表,更新最大堆。 5. **结果输出**:输出堆中的10个字符串及其出现次数。 ### 知识点四:大型论坛系统的...

    PilotEdit Lite v12.7.0.zip

    单击即可添加一个自定义的字符串 在所选文本的前后分别添加自定义的字符串 12. 正则表达式 用正则表达式查找/替换多行文本 13. 脚本文件 可以把常用的正则表达式定义在脚本中,直接运行脚本即可替换文字 14. ...

    常见算法笔试或面试题

    这些题目来自各大 IT 公司的历年笔试或面试题,涵盖了链表、哈希表、排序、搜索、字符串处理等多个方面。 1. 判断链表是否有环 问题:判断链表是否有环?可以使用 O(n) 时间和 O(1) 空间复杂度来解决该问题。 ...

Global site tag (gtag.js) - Google Analytics