algorithm - 集合交点的并行算法

Question

我有 n 组（分布在 n 列上）表示网格节点的数据，我想知道一种有效的并行算法来找到这些组的交集，即公共节点。只要任何 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-rank 上完成，每个 rank 有 1 个集合。

Answer 1

您应该能够使用哈希表并行处理这种快速 O(N)。

对于每个集合 S_i，对于每个成员 m_x（所有这些都可以并行完成），将集合成员放入与集合名称关联的哈希表中，例如，。每当你从集合 S_j 在 m_x 的哈希表中命中时，你现在就有了相应的集合编号 S_i，并且你立即知道 S_i 与 S_j 相交。您可以将 m_x 放在派生的交集中。

您需要一个并行安全的哈希表。这很容易; 在更新期间锁定存储桶。

[另一个答案建议对集合进行排序。对于大多数排序算法，将是 O(N ln N) 时间，而不是那么快]。