MyException - 我的异常网
当前位置:我的异常网» Java相关 » java对大数据量文件内容的多线程读取和排序,该怎么

java对大数据量文件内容的多线程读取和排序,该怎么处理

www.MyException.Cn  网友分享于:2013-03-26  浏览:816次
java对大数据量文件内容的多线程读取和排序
1.Generate a random text file, which contains at least 100 Million lines. Each line must contain over 100 characters.
2.Compose a Java program to sort the file within a standard qualified time (time for data IO is also counted). Less running time used, the performance is better. The program MUST NOT consume memory over 512M Bytes, and the usage of CPU is not limited.
各位大侠,大家好,我现在有个棘手的题目,请大家帮忙,有满意答案后可给分
题目翻译入下:
1:生成一个随机的文本文件,其中包含至少10亿行,每一行必须包括100个字符。
2:编写一个java程序,对此文本内容进行排序,排序计时,时间越少性能越好,内存不得大于512MB,CPU满意限制。

  个人愚见:可以考虑外部排序中使用线程来提高运行效率(cpu没有限制),到文件太大需分割(使用缓存)。如何组织好一个程序还望高手指教。最好有程序。谢谢了。

------解决方案--------------------
先翻译准确了,100M是1亿
------解决方案--------------------
感觉楼主的需求还没有描述完全,问题漏洞太多。

1.生成这样的文件,每行的信息内容是什么,是否包含格式?
2.排序依据是什么,如何排序。
3.排序结果是什么,如何体现。

我自己臆测下你这个题目锁涉及的难点吧。

1.文件过大,不可能一次性load。基于效率问题,批量读取,控制buffer大小提高效率。
如果是xml文件就使用Sax解析方式,基于流。

2.排序后结果统计非常麻烦,如果是把排好序的文件重新生成难度就体现出来了了,如何插入排序方式无需整理结果文件,但需要遍历原始10亿*10亿次。
需要人为策略优化。


我个人优化思路如下:
1. 读取文件基于流,每次读一行,自行判断换行符号,将排序方式编码成权计算,计算出比较权值。
形成 [文件流byte[offset]:length:行号:权值] 信息。将索引信息存放内存,因为数据量小不会耗费大量内存。
(该过程可以通过String buffer[] 来缓存一定数量的lineString信息[文件流offset,length],起用多线程并发并发计算权值)

2. 对权值进行散列,适当控制散列堆大小,散列到不同的散列堆,然后进行排序。
一个堆即一个具备排序功能的链式结构。
通过权值散列到不同的排序堆堆。


3.通过randeAccessFile 读取源文件,输出排序文件。如果排序文件可以分多个文件输出,可以依照排序堆,并给输出文件命名。
sorted_1.txt sorted_2.txt ....... sorted_n.txt,这样在写文件时可以使用多线程进行提速。






------解决方案--------------------
IO 操作无法使用多线程,IO 操作的并发率为 0,也就是说不支持并发。

使用多个线程读写文件,比单个线程会更慢,因为带来了更多的寻道时间。
------解决方案--------------------
探讨
OS 有的应该可以限制文件最大长度吧。

这么大的文件,应该早就进行人为控制大小的切分,如果这是个面试题考考反映就合理了。

一切皆可假设。

------解决方案--------------------
这个问题我也遇到过,我们公司考试考了一个这样的题,但是题不太一样,那是一个移动号码排序,139号码段,每天要把前面放出的号和当天放出的号合并成一个文件,并排序,以前放出的号没有说已经排好序,手机号码11位,去除前面3位还有8位基本上快到1亿,号码是一行一个号,txt格式,我这里给你一个思路,可以用内存映射,这种方式应该是java里能读的最大文件的方式了,这里只是读,另外就是排序,因为不知道你的文件内容是什么,所以不太好说,我就说移动这个吧,我们把文件读出来的时候对他分拆,设一个段,每一个段一个文件比如,以139001(139001*****)开头的写一个文件,以139002(139002*****)开头的写一个文件这样分成若干个小文件,再排序,最后把这几个文件合并就可以了。

文章评论

十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
漫画:程序员的工作
漫画:程序员的工作
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
代码女神横空出世
代码女神横空出世
我是如何打败拖延症的
我是如何打败拖延症的
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
那些争议最大的编程观点
那些争议最大的编程观点
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
老程序员的下场
老程序员的下场
10个调试和排错的小建议
10个调试和排错的小建议
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员和编码员之间的区别
程序员和编码员之间的区别
鲜为人知的编程真相
鲜为人知的编程真相
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
一个程序员的时间管理
一个程序员的时间管理
程序员必看的十大电影
程序员必看的十大电影
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
为什么程序员都是夜猫子
为什么程序员都是夜猫子
每天工作4小时的程序员
每天工作4小时的程序员
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员的鄙视链
程序员的鄙视链
程序员都该阅读的书
程序员都该阅读的书
总结2014中国互联网十大段子
总结2014中国互联网十大段子
中美印日四国程序员比较
中美印日四国程序员比较
我的丈夫是个程序员
我的丈夫是个程序员
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员应该关注的一些事儿
程序员应该关注的一些事儿
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
编程语言是女人
编程语言是女人
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
 程序员的样子
程序员的样子
如何成为一名黑客
如何成为一名黑客
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有