c++ - 有效地删除所有重复记录

Question

我有一个文件可能 30+GB 或更多。这个文件中的每一行都称为一条记录，由2列组成，如下所示

id1 id2

所有这 2 个 ID 都是整数(32 位)。我的工作是编写一个程序来删除所有重复的记录，使记录唯一，最后将唯一的 id2 输出到文件中。

有一些限制，最多允许30G内存，最好通过非多线程/进程程序高效地完成工作。

最初我想到了一个想法:由于内存限制，我决定读取文件n次，每次只在内存中保留那些记录为id1 % n = i (i = 0,1,2,..,n-1)的记录。 .我使用的数据结构是 std::map<int, std::set<int> > ，它以id1为key，将id2放在id1的std::set中.

这样，不会违反内存限制，但速度很慢。我认为这是因为作为 std::map和 std::set变大，插入速度下降。此外，我需要读取文件 n 次，每轮完成后，我必须清除 std::map下一轮也需要一些时间。

我也尝试了hash，但它也不令我满意，我认为即使是300W buckets 也可能有太多的碰撞。

所以，我把我的问题贴在这里，帮助你们提供更好的数据结构或算法。

非常感谢。

附言

脚本(shell，python)是需要的，如果它能有效地完成的话。

Answer 1

除非我忽略了一个要求，否则应该可以在 Linux shell 上这样做

sort -u inputfile > outputfile

许多实现也使您能够以并行方式使用排序:

sort --parallel=4 -u inputfile > outputfile

最多四个并行执行。

请注意，sort 可能会暂时占用 /tmp 中的大量空间。如果那里的磁盘空间不足，您可以使用 -T 选项将其指向磁盘上的另一个位置以用作临时目录。

---

(编辑:)关于效率的一些评论:

• 执行过程中花费的大部分时间(对您的问题的任何解决方案)将花在 IO 上，sort 已针对此进行了高度优化。
• 除非您有非常多的 RAM，否则您的解决方案很可能最终会在磁盘上执行一些工作(就像排序)。同样，优化这意味着大量工作，而对于 sort，所有这些工作都已完成。
• sort 的一个缺点是它对输入行的字符串表示形式进行操作。如果您要编写自己的代码，您可以做的一件事(类似于您已经建议的)是将输入行转换为 64 位整数并对其进行哈希处理。如果你有足够的 RAM，这可能是一种在速度方面击败 sort 的方法，如果你让 IO 和整数转换非常快的话。我怀疑这可能不值得付出努力，因为 sort 易于使用，而且我认为速度足够快。