你将如何对 30gb 文件进行排序，其中重复包含 1 - 1000 个数字

Question

我有 30 GB 的文件，其中重复只有 1-1000 个数字。我想知道如何对该文件进行排序，您需要先将文件加载到内存中。

我已经通过 SO 中的其他链接，但不同意对多个文件块进行排序并将其保存在临时文件中的观点。我相信在流程结束时，我将留下两个大文件（每个 15 GB）进行排序。我无法加载每个以进行合并和排序。

有什么建议吗？

Answer 1

鉴于所有值都在 1..1000 范围内，您可以使用 Counting Sort.

的简单版本来执行此操作

• 创建一个 counters[1000] 的数组（1001，如果你的数组是 从零开始）全部初始化为零。
• 读取文件，当你从文件增量counters[n]读取值n时。
• 现在您知道每个值在输入文件中出现了多少次了。
• 循环 counters，为每个索引 n 将 n 的 counters[n] 个副本写入输出。比如counters[100] == 5那么写100输出5次。

您不需要将整个文件保存在内存中。您只需要计算每个值在文件中出现的次数。这足以创建原始文件的排序版本。