100G的大文件中找出最大的100个数

题目：

有一个100G大小的文件里存的全是数字，并且每个数字见用逗号隔开。现在在这一大堆数字中找出100个最大的数出来。

++++++++++++++++++++++++++++++++++++++++++++

 

无意间看到这个题目 觉得挺有意思的，尝试了下

 

电脑是 intel E7500 @2.93G 4G内存 64位

 

网上搜了一下，看到一篇，他用的测试数据是1.2G 大约花了10秒吧。

 

我自己写了个 在cmd下最好一次只有大约3秒，eclipse下约总共耗时：5666ms

 

我想可能电脑也有差异

 

+++++++++++++++++++++++++++++++++++++++++++++

 

其实这个 题目我第一反应是 文件系统的I/O瓶颈应该大于排序算法

 

*首先类似这种无序的数据，只能一一读取，比较之，也就是排序算法的优化 应该是有限的

 

*考虑到数据量的却很大，肯定要想种方法或者策略缓解之

 

++++++++++++++++++++++++++++++++++++++++++++++

 

其实上边那篇文章已经提到了挺好的两个做法，我也基本照做了，但是测试的性能好像要好些

*线程

将大数据分解为几个小数据，同时可以合理使用多核CPU。在单线程下基本上cpu只能用到50%左右

 

*内存映射

这个是提高I/O效率的很好的方法吧

 

++++++++++++++++++++++++++++++++++++++++++++++

 

至于排序，我直接使用了java的Arrays包中的sort方法，其本身已经很好了

 

 

这段是主要代码

 

*分段进行内存映射

 

*对每次读取的数据进行必要的比较，排序

 

*最后将本段找出的前100个数据插入到缓存集中

 

*缓存集再次排序，找出最大的100个数

 

private void memoryMappingRead(FileChannel fc, long begin, long length) throws IOException {
		MappedByteBuffer out = fc.map(FileChannel.MapMode.READ_ONLY, begin, length); 
		
		int temp;
		
		for(long i = 0; i < length / GROUP_SIZE; i++) {
			temp = out.getInt();
			out.getChar();
		if(temp <= data[0]) {  
         	   continue;               
            } else if(temp > data[0]){  
            	data[0] = temp;
//直接使用java的排序方法
         	Arrays.sort(data);
            }  
			
	}
		
		SortData.addList(data);		
	}

 

 

评论

1 楼 xyueshan 2010-11-14  

一直想找一个外排的实现的例子。看了楼主的帖子很有想法。不过我是一个初学者。楼主能不能把代码给我发一份？[e-mail]。谢了