c++ - 独特的大规模阵列/序列

Question

我想唯一化 n 元素的数组。

n 最大可达 10^9，甚至 10^11。

也就是说，元素可能无法全部放入内存中。因此，下面的简单排序和唯一方法将不起作用(太慢:排序和唯一一个 10^8 数组需要一个线程半分钟)。


排序( a.begin(), a.end() );
a.erase( unique(a.begin(), a.end() ), a.end() );


幸运的是，有一些东西可以帮助设计算法:

• 元素适合 64 位无符号整数 ( uint64_t )。由于元素是由哈希函数生成的，因此我们可以假设它满足均匀分布( ~U(0, 2^64-1) )。

• 我有一个不少于 10 台多核计算机/节点的集群，因此可以(并且应该)将算法设计为分布式。我有权运行 MPI C++ 代码。 (不过集群不属于自己，有时可能有其他程序在任何一台电脑/节点上争抢CPU时间。所以任务最好动态分配到每台电脑/节点)

• 每台计算机/节点不少于8核，不少于64G主内存，不少于100G SSD空闲空间。此外，它们通过千兆以太网连接。

谁能帮忙给一下设计算法的建议？该方法需要多次运行。我希望在集群上一小时内得到结果。

Answer 1

将您的数据分成两部分。假设一个部分很容易放入内存。排序并使每个部分都独一无二。将其保存到文件中(可以同时完成)。就像合并两个有序集合一样，你只需要每个部分的头部。处理后的元素可以写入磁盘。

从 2 个部分到 N 个部分的泛化很容易。