100亿个数字的大文件如何快速找出最小的值?

JAVA herman 816浏览 0评论

又到了一年一度的面试季,最近有网友给出一道高级java工程师的面试题。100亿个数字的大文件如何快速找出最小的值?我这里给出一些思路,提供参考!

这道题我们首先想到的是使用外部排序的方式,由于内存的原因,内部排序肯定不被允许,或者不是最佳选择!

外部排序

内存极少的情况下,利用分治策略,利用外存保存中间结果,再用多路归并来排序。

map-reduce的嫡系

map-reduce

大文件排序

分割大文件

内存中维护一个极小的核心缓冲区memBuffer,将大文件bigdata按行读入,搜集到memBuffer满或者大文件读完时,对memBuffer中的数据调用内排进行排序,排序后将有序结果写入磁盘文件bigdata.xxx.part.sorted.
循环利用memBuffer直到大文件处理完毕,得到n个有序的磁盘文件:

大文件排序分割

合并多个排序结果

现在有了n个有序的小文件,怎么合并成1个有序的大文件?
把所有小文件读入内存,然后内排?
利用如下原理进行归并排序:

多排序结果合并

我们举个简单的例子:

文件1:3,6,9
文件2:2,4,8
文件3:1,5,7

第一回合:
文件1的最小值:3 , 排在文件1的第1行
文件2的最小值:2,排在文件2的第1行
文件3的最小值:1,排在文件3的第1行
那么,这3个文件中的最小值是:min(1,2,3) = 1
也就是说,最终大文件的当前最小值,是文件1、2、3的当前最小值的最小值,绕么?
上面拿出了最小值1,写入大文件.

第二回合:
文件1的最小值:3 , 排在文件1的第1行
文件2的最小值:2,排在文件2的第1行
文件3的最小值:5,排在文件3的第2行
那么,这3个文件中的最小值是:min(5,2,3) = 2
将2写入大文件.

也就是说,最小值属于哪个文件,那么就从哪个文件当中取下一行数据.(因为小文件内部有序,下一行数据代表了它当前的最小值)

最终的排序结果

less bigdata.sorted.text
...
9999966
9999967
9999968
9999969
9999970
9999971
9999972
9999973
9999974
9999975
9999976
9999977
9999978
...

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847,QQ3群:187424846。QQ群进群密码:xttblog,想加微信群的朋友,可以微信搜索:xmtxtt,备注:“xttblog”,添加助理微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 100亿个数字的大文件如何快速找出最小的值?