登录 注册

【经验】大文件排序实验—实验记录

针对超出内存大小的大文件排序的简单算法和性能实验
时间:2016-07-24 16:15:46 作者:Mr.d

之前去某家公司面试

面试官:有一个大文件,文件大概几个G,超过了你服务器的内存,你怎样对其内部数据进行排序呢?

我:额...先把大文件切割,分成若干个小文件,然后排序的话肯定是根据每行数据中的一个字段,把这个字段单独拿出来,和分割的小文件做内存关联,然后把这个排序字段当做索引去排序,单独一个字段的数据量应该不会那么大,排序完了之后根据这个字段和文件的对应关系去找那一行数据,最终生成一个排序后的文件。

面试官:不错,思路对了,先分割成小文件是正确的,但是如果这个文件里每一行只有一个字段怎么办?比如一行一个身份证号,这个文件有好几个G,你的索引拿出来也排不了序了吧?

我:......

面试官:其实这个就是一个简单的分布式计算的例子,把一个大的任务分成多个子任务,最终汇总,其实这个题你可以在分割的时候就先对每个文件内部进行排序,然后分别获取每个文件的第一行进行比较,获取最小的,写到新文件里,然后以此类推,就完成了整个大文件的排序

我:......


        好吧,老司机说的确实是对的,当年我也好年轻,没觉得什么不过后来想想,人家确实牛逼....

        这几天突然想起来这件事了,突发奇想, 来吧,试验一下吧....

实验场景

        阿里云服务器配置:单核CPU、1G内存

实验过程及记录

        实验思路

  1. 将大文件分割成小文件,并对每个小文件进行排序(从小到大)

  2. 初始化创建一个map,key为每个小文件的标识,value为每个小文件的第一行数据

  3. 根据map计算出一个最小值,并写入文件

  4. 从最小值所在的文件中读取一行,并放入map中替换原有的值

  5. 开启循环,当其中一个小文件读取到最后一行后,在map中remove掉该小文件对应的数据

  6. 当map中数据为空时,则认为排序结束


第一次试验

        第一次试验的时间在凌晨,所以很多数据和记录没有截图

1、创建大文件,99999999条数据大约占用1G左右空间

-rw-r--r-- 1 root root 1044427787 Jul 24 00:16 data2.txt

2、逐行读取大文件,并将读取的数据放入List中,结果不出意外,一会儿的时间,就OutOfMemoryException异常了

3、排序算法,见下图

    3.1 结果:本次实验中,每获取到一个最小值时,会将数值写入到文件中,并且将数值输出到控制台中,在输出结果中可以看到,从上到下的输出,依次也都是从小到大的,所以可以证明此排序算法是正确的。

    3.2 耗时:每次将数据写入到文件中耗时基本在0ms(日志耗时计算的级别为毫秒),那么可以认为每一次的的写入其实耗时是在纳秒级别的,但是总时间是为4466884ms,折合一下大概是在74分钟左右,其实这里虽然每次写入都在纳秒级别,但是架不住99999999次的写入过程,积少成多,所以耗时极多。


第二次实验

1、第一次的实验已经证明了排序算法的正确性,所以第二次实验时,将每次计算出最小值就写入文件,改为先放入到内存中,10W条记录写入一次。

2、在文件分割的过程中,CPU使用率基本上在90-99%之间

3、文件分割过程中,写入每个文件的耗时平均在45-55ms,总时间在310s,差不多是5分钟,另外在我自己的电脑上测试执行分割文件时,基本上每个文件的耗时在15-25ms之间,我的是SSD硬盘,估计阿里云是传统的硬盘吧,所以两者有些差距

4、排序的过程中,CPU使用率也在90-99%之间

5、排序过程中,第二次每次批量写入10W数据,基本上耗时在7-20ms,我不太清楚是我代码监控时间的位置有问题,还是有什么其他因素存在。这里的总耗时为896211,折合一下大概在15分钟左右


        下一篇文章里会将我实验所写的代码粘出来,有兴趣的可以看看,什么框架都没用,就是java基础的东西

        【经验】大文件排序实验—代码


结论

        不管怎样,我用了一个1G内存的服务器,对一个1G的文件做了一个排序,虽然时间最少也是用了20分钟(最多用了接近90分钟),但是至少算是实现了某种算法,也算是对传说中的“大文件”,“大数据”进行了一个摸索,也算是个经验吧,这个程序还有很多可以改进的地方,实验的记录和结果中还有很多不清楚的地方,如果有兴趣的话,可以与我联系,沟通。

QQ:2410508062   Q群:346884762








评论


暂无评论