假设我有X GB的可用RAM空间，并且我需要对一个巨大的数据数组进行排序（该数组远大于所有可用内存。它存储在硬盘上）。您能否给出一些提示，如何实现这个问题？
6个回答
28
您正在寻找“外部排序”。
在这些场景中，最大的成本通常是磁盘IO。因此，诀窍是使用最小化磁盘IO的算法。
通常的方法是将适当大小的块读入内存中，对这些块进行排序，将其保存回磁盘，然后合并排序后的块。
搜索“外部排序”或“归并排序”以及您选择的技术应该会给出一些好的结果。
- philiphobgen
12
假设您有一个巨大的文件H和限制内存M，我有两种解决方案。
方案1： 步骤1：从文件中读取M，并将其写入缓冲区。 步骤2：对值进行排序（您应该使用原地排序算法，如QuickSort、HeapSort）。 步骤3：创建一个临时文件，并将缓冲区写入临时文件。保存临时文件的名称。 步骤4：重复步骤1到3，直到读取完文件H，将M分段并保存所有临时文件。 步骤5：将所有临时文件合并为一个新文件。创建一个新文件，打开所有临时文件，将文件句柄放入数组中。 步骤6：从文件读指针当前指向的数集中找到最小数。您可以使用普通的方法来比较每个数字，并使用临时变量来记住它（时间复杂度为O(n)）。或者您可以创建一个priorityQueue和map，map的键是数字，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： 步骤1：从文件中读取M，并将其写入缓冲区。 步骤2：对值进行排序（您应该使用原地排序算法，如QuickSort、HeapSort）。 步骤3：创建一个临时文件，并将缓冲区写入临时文件。保存临时文件的名称。 步骤4：重复步骤1到3，直到读取完文件H，将M分段并保存所有临时文件。 步骤5：将所有临时文件合并为一个新文件。创建一个新文件，打开所有临时文件，将文件句柄放入数组中。 步骤6：从文件读指针当前指向的数集中找到最小数。您可以使用普通的方法来比较每个数字，并使用临时变量来记住它（时间复杂度为O(n)）。或者您可以创建一个priorityQueue和map，map的键是数字，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，没有合并处理，但每个数字都被读取和写入了三次。
- Jiaji Li
1
1合并也需要一个好的算法。因为由于内存限制，您无法将所有文件合并在一起。 - codersaif
4
实际上，如果您不想编写太多代码，并且磁盘使用量不是问题，请将数据放入具有适当索引的数据库中，然后只需从中select * order by即可。
- grep
0
我想你可以构建一种索引系统，将排序后的数据分开。
想象一下图书馆里的书架。遍历1/x的数据，将所有元素分类放在书架上，并将每个书架缓存到磁盘上的单独文件中。然后对下一个1/x的数据进行排序，将其写回磁盘，以此类推。一旦你把所有的数据都放在书架上，就逐个对每个书架进行排序，最后将它们合并成一个漂亮的排序文件。
- Tomas
-1
您可以使用ZZZServer对许多大文件（排序结果可能达到几个TB甚至更大）进行排序。该产品是免费供非商业使用的。我与该产品有关联：
ZZZServer -sortinit -sort file1.txt
ZZZServer -sort file2.txt
ZZZServer -sort file3.txt
...
ZZZServer -sortsave sorted.txt
排序后结果保存在
sorted.txt
您的输入文件必须使用UTF-8或ASCII格式进行编码！
ZZZServer在对大文件进行排序时使用约1MB的RAM！
- Z. Georgiev
1
1当链接到您自己的网站或内容（或与您有关联的内容）时，您必须在答案中披露您的关联，以便不被视为垃圾邮件。在用户名中具有与URL相同的文本或在个人资料中提及它不被视为足够的披露根据Stack Exchange政策。 - cigien
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接