phi*_*gen 20
您正在寻找外部排序.这些方案中最大的成本通常是磁盘IO.因此,诀窍是使用最小化磁盘IO的算法.通常的方法是在内存中读取适当的大块,对这些块进行排序,将它们保存回磁盘,然后合并已排序的块.
搜索"外部排序"或"排序合并"以及您选择的技术应该会产生一些好的结果.
让我们假设您有一个巨大的文件H并限制内存M.
我有两个解决方案.
解决方案1:
步骤1:从文件中读取M并将其写入临时缓冲区.
第2步:排序(您应该使用就地排序算法,如QuickSort,HeapSort)的值.
步骤3:创建临时文件并将缓冲区写入临时文件.保存临时文件的名称.
步骤4:重复步骤1到3,直到读取文件H out,并排除M out并保存所有临时文件.
步骤5:将所有临时文件合并到新文件.创建一个新文件,并打开所有临时文件,将文件句柄放入一个数组中.
步骤6:从文件读指针当前指向的数字集中查找最小数字.您可以使用常规方法来执行此操作,比较每个数字,并使用临时变量来记住它(时间复杂度为O(n).或者您可以创建priorityQueue和地图,地图的关键是数字,并且map的值是文件句柄的序列.(时间复杂度是O(lgn),第二种方式浪费更多内存,但性能更好,如果你想要更好的方法,你可以使用int来替换列表使用位图,因为临时文件名被占用.
步骤7:将号码保存到新文件.
步骤8:从步骤6中包含最小号码的文件中读取另一个号码.
步骤9:重复步骤7到8直到所有已处理所有临时文件中的数字.
解决方案2:步骤1:创建N个临时文件,每个临时文件的编号范围不同(例如,temp_file_1的范围是0到1000000,下一个临时文件是1000001到2000000 ... )
步骤2:从H文件中读取m并将数字写入不同的临时文件,直到无法从文件H中读取任何内容.
步骤3:对每个临时文件进行排序.
步骤4:创建一个新文件,将所有临时文件逐个合并到这个新文件中.
解决方案之间有什么区别.根据解决方案1,每个数字被排序一次并且被多次比较(步骤5),但是只读取和写入两次.关于解决方案2,没有合并处理,但是每个数字都被读取并写入三次.
您正在寻找的是外部排序.
http://en.wikipedia.org/wiki/External_sorting