我有 n 组(分布在 n 秩上)代表网格节点的数据，我想知道一种有效的并行算法来找到这些集合的交集，即公共(public)节点。一旦任何 2 个集合共享一个节点，就会定义一个交集。
例如；
输入:
Rank 0: Set 1 - [0, 1, 2, 3, 4]
Rank 1: Set 2 - [2, 4, 5, 6]
Rank 2: Set 3 - [0, 5, 6, 7, 8]
执行并行算法 --> 结果:(找到交集后)
Rank 0: [0, 2, 4]
Rank 1: [2, 4, 5, 6]
Rank 2: [0, 5, 6]
该算法需要在 n-ranks 上完成，每个 ranks 设置 1。
最佳答案
您应该能够使用哈希表并行地实现如此快速的 O(N)。
对于每个集合 S_i，对于每个成员 m_x(所有这些都可以并行完成)，将集合成员放入与集合名称关联的哈希表中，例如 .任何时候你在集合 S_j 的 m_x 上的哈希表中得到一个命中，你现在有相应的集合号 S_i，并且你立即知道 S_i 与 S_j 相交。您可以将 m_x 放在派生的交集中。
您需要一个并行安全的哈希表。这很容易;在更新期间锁定存储桶。
[另一个答案建议对集合进行排序。对于大多数排序算法，时间为 O(N ln N)，没有那么快]。
关于algorithm - 集合交集的并行算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13846054/