Java教程

大文件小内存排序问题

本文主要是介绍大文件小内存排序问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
比如外存中有100G的字符串文件,1G的内存,对字符串进行排序操作。 1.首先将100G的内容分成若干个小部分,每个部分不超过500MB。分别读取这些小部分进行排序,然后写入到外存中。这样就得到了若干个已经排好序的小部分。 2.多路归并排序,(相对二路归并而言)。对于k个已经排好序的小部分,每次取出它们各自的最小值,找到最小值中的最小值,写入到外存,同时将最小值所在外存区域指针向右移动。 每次比较最小值需要比较k-1次,总共有n-1轮,所以时间复杂度为O((n-1)*(k-1))。 这里还可以使用胜者树(完全二叉树)优化找最小值的过程。对第一次的查找建立一颗胜者树,如下所示: 找到最小值后,读取最小值所在外存区域的新值,然后修改胜者树对应节点的值,沿着从该结点到根结点的路径修改这棵二叉树,最多操作log(k)次。这样总体排序的时间复杂度就可以降为O(nlogk)。

这篇关于大文件小内存排序问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!