在给定内存限制的情况下对具有大量数据的文件进行排序

Question

要点：

• 我们一天同时处理数千个平面文件。
• 内存限制是一个主要问题。
• 我们为每个文件进程使用线程。
• 我们不按列排序。文件中的每一行（记录）都被视为一列。

不能做：

• 我们不能使用 unix/linux 的排序命令。
• 我们不能使用任何数据库系统，无论它们有多轻。

现在，我们不能只加载集合中的所有内容并使用排序机制。它会耗尽所有内存，程序会出现堆错误。

在那种情况下，您将如何对文件中的记录/行进行排序？

原文由 Erika Gomez 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

看起来您正在寻找的是 external sorting 。

基本上，您首先对小块数据进行排序，将其写回磁盘，然后迭代这些数据以对所有数据进行排序。

原文由 phisch 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

正如其他人提到的，您可以分步处理。

我想用我自己的话来解释一下（第 3 点不同）：

1. 按顺序读取文件，在内存中一次处理 N 条记录（N 是任意的，取决于你的内存限制和你想要的临时文件的数量 T）。

2. 对内存中的 N 条记录进行排序，将它们写入临时文件。循环 T 直到完成。

3. 同时打开所有 T 临时文件，但每个文件只读取一条记录。 （当然，有缓冲区）。对于这些T记录中的每一个，找出较小的，写入最终文件，只在那个文件中前进。

---

优点：

• 内存 消耗低到你想要的。
• 与内存中的所有内容策略相比，您只需进行 两倍的磁盘访问。不错！ :-)

---

以数字为例：

1. 具有 100 万条记录的原始文件。
2. 选择拥有 100 个临时文件，因此一次读取和排序 10 000 条记录，并将它们放入它们自己的临时文件中。
3. 一次打开100个临时文件，读取内存中的第一条记录。
4. 比较第一条记录，写入较小的记录并推进此临时文件。
5. 循环步骤 5，一百万次。

---

已编辑

你提到了一个多线程应用程序，所以我想知道……

正如我们从这些关于此需求的讨论中看到的那样，使用较少的内存会降低性能，在这种情况下会产生很大的影响。所以我也可以建议 只使用一个线程一次 只处理一种类型，而不是作为多线程应用程序。

如果你处理十个线程，每个线程只有十分之一的可用内存，你的性能会很糟糕，远低于初始时间的十分之一。如果你只使用一个线程，将其他 9 个需求排队并依次处理它们，你的全局性能会好得多，你会更快地完成这 10 个任务。

---

阅读此回复后： Sort a file with huge volume of data given memory constraint 我建议您考虑这种分布排序。在您的上下文中，这可能是巨大的收获。

对我的建议的改进是您不需要一次打开所有临时文件，您只需打开其中一个。它可以节省您的一天！ :-)

原文由 KLE 发布，翻译遵循 CC BY-SA 3.0 许可协议