`

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  
一直想找一个外排的实现的例子。看了楼主的帖子很有想法。不过我是一个初学者。楼主能不能把代码给我发一份?xyueshan@sohu.com。谢了

相关推荐

    semasio-test:给定一个整数数组,从数组中找出两个数的最大乘积,即 3 的倍数

    要求给定一个整数数组,从数组中找出两个数的最大乘积,即 3 的倍数。 输入 {6,8,8,7,2,5} 的结果应该是 48 = 6 8。请注意,8 8 是最大的乘积 (64),但 64 不能被 3 整除。 给定输入 {1,9,2,4},结果应该是 36 = 9 4...

    g-p.rar_G-P_G——p_Matlab关联维数_关联维数_关联维数G-P

    总结来说,"g-p.rar_G-P_G——p_Matlab关联维数_关联维数_关联维数G-P"这个压缩包文件提供了一个基于Matlab的G-P方法实现,用于计算混沌系统的时间序列数据的关联维数,从而帮助我们理解和分析系统的复杂动态行为。...

    java排序算法使用及场景说明

    解决方案 1:首先是这一天,并且是访问百度的日志中的 IP 取出来,逐个写入到一个大文件中,然后采用映射的方法,找出每个小文件中出现频率最大的 IP,最后在这 1000 个最大的 IP 中,找出那个频率最大的 IP。...

    SQL数据库对于海量数据面试题及答案.pdf

    对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie 树/hash_map 等),并取出出现频率最大的100个词(可以用含100 个结点的最小堆) ,并把 100 词及相应的频率存入文件,这样又得到了5000 个文件...

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

    在实际操作中,可以将大文件映射为多个小文件,然后找出每个小文件中出现频率最大的 IP,并再在这些 IP 中找出频率最大的那个 IP。 二、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询...

    Oracle 最大并发数、会话数查询

    这将显示SQL语句文本、执行计数、CPU时间等信息,帮助你分析系统性能和找出潜在的性能瓶颈。 总结来说,掌握Oracle数据库的并发数和会话数的查询与调整方法,对于数据库管理员来说至关重要,这有助于优化资源分配,...

    大数据量,海量数据处理

    12. 给定100w个数中,需要找最大的前100个数。解决方法是使用堆排序来输出最大的前100个数。 13. 需要寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255...

    mysql数据库my.cnf配置文件

    # 你的操作系统在这个队列大小上有它自己的限制(可以检查你的OS文档找出这个变量的最大值),试图设定back_log高于你的操作系统的限制将是无效的。 max_connections = 500 # MySQL的最大连接数,如果服务器的并发...

    Everything 全球速度最快的电脑文件搜索工具 快到你吐血喷饭

    目前我已经设置成常驻任务栏了,你每次检索的时候,每输入一个字幕或者单词,就立刻瞬间将文件找出。 支持高亮、支持and or 等语法以及正则表达式,完美支持中文,完全免费。 吐血推荐。太强了。 btw,用了...

    最大颜色值平衡方法

    在“最大颜色值平衡方法”中,目标是找出图像中最大颜色值,并以此为基准进行调整。这通常涉及以下步骤: 1. **读取图像**:使用MATLAB的`imread`函数读取图像文件,如`1.jpg`。 2. **像素分析**:遍历图像的每一个...

    阿里大数据笔试

    这个问题要求处理一个100GB的日志文件,统计其中每个英文单词出现的频率,并打印出出现次数最多的10个不重复的单词。在Java或Python中,可以使用MapReduce或Pandas等工具进行分布式处理。首先,需要将大文件切分成...

    数字练习题答案.txt

    编写一个Java程序,找出100至999之间所有的水仙花数。水仙花数是指一个三位数,其各个位上的数字立方和等于该数本身。例如,153是一个水仙花数,因为1^3 + 5^3 + 3^3 = 153。 #### 解析 代码通过循环遍历100到999...

    AIX之文件系统使用率高查询思路.docx

    1. 定位并处理大文件:找出占用空间大的文件,视情况进行备份或删除。 2. 扩展文件系统:检查VG的剩余空间,如果足够,可以考虑对文件系统进行扩容。 此外,还有其他命令可用于查询硬盘大小,如`lsfs -c -k`,它...

    由图的连接矩阵返回图中所有的完全子图

    接着,`gonstatis.m`文件的作用是对`maximalCliques.m`找出的极大完全子图进行进一步处理,生成所有完全子图。这可能涉及到对极大完全子图的点进行全组合,即对于每个极大完全子图,生成所有可能的子集,这些子集...

    SQL数据库日志文件容量超大解决方法[参照].pdf

    1. **识别问题**:通过SQL Server Management Studio (SSMS)查询`sys.master_files`视图,找出占用空间大的日志文件。 2. **安全分离**:在不影响业务的情况下,选择目标数据库并执行“分离”操作。这将使数据库与...

    上海电机学院C语言实训答案

    (12)编写程序验证以下说法:输入一个4位数,该数个、十、百、千位上的数互不相等,由个、十、百、千位上的数组成一个最大数和一个最小数,最大数-最小数,构成一个新的4位数。反复以上运算,使其最终结果为:6174...

    最大流_最大流模板_

    最大流问题是一个经典的图论问题,它在计算机科学和网络流理论中占有重要地位,尤其在运筹学、算法设计和优化等领域应用广泛。在信息学奥林匹克竞赛中,选手们经常需要解决这类问题来求解网络中的最大传输能力。本文...

    大数据常见算法题.txt

    同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,...

    数据挖掘的一些题目

    解决方案是首先提取出这一天的日志中的 IP,然后使用映射的方法将其分割为 1000 个小文件,最后找出每个小文件中出现频率最大的 IP。 知识点: * 海量日志数据分析 * 映射方法 * 频率统计 5. 整数去重复:在 2.5 ...

Global site tag (gtag.js) - Google Analytics