如何在 Spark 中使用 MapReduce 查找集合中的所有两对集合和元素？

Question

我有一套集合，每套包含很多项目。我想使用 Spark 检索所有成对的集合和元素，其中减少处理后的每一对将包含两个项目和两个集合例如：

如果我有这个集合列表

Set A={1,2,3,4 }
Set B={1,2,4,5}
Set C= {2,3,5,6}

映射过程将是：

(A,1)
(A,2)
(A,3)
(B,1)
(B,2)
(B,4)
(B,5)
(C,2)
(C,3)
(C,5)
(C,6)

reduce后的目标结果为：

(A B, 1 2) // since 1 2 exist in both A and B
(A B, 1 4)
(A B, 2 4)
(A C,2 3)
(B C,2 5) 
here (A B,1 3) not in the result because 1 3 not exists in B

你能帮我用任何语言（Python、Scala 或 Java）用一个 map 和一个 reduce 函数解决这个问题吗？

Answer 1

让我们把这个问题分解成多个部分，我认为从输入列表到映射输出的转换是微不足道的。那么让我们从那里开始，

你有一个看起来像

的 (String, int) 列表

("A", 1)
("A", 2)
....

让我们忘记您首先在结果集中需要 2 个整数元素，然后让我们解决从映射输出中获取任意 2 个键之间的交集。

您输入的结果看起来像

(AB, Set(1,2,4))
(BC, Set(2,5))
(AC, Set(2,3))

为此，首先，从映射输出 (mappedOutput) 中提取所有键，它是 (String, Int) 的 RDD，转换为集合，并获得 2 个元素的所有组合（我使用的是一种愚蠢的方法在这里，一个很好的方法是使用组合生成器）

val combinations = mappedOutput.map(x => x._1).collect.toSet
.subsets.filter(x => x.size == 2).toList
.map(x => x.mkString(""))

输出为List(ab,ac,bc)，这些组合代码将作为要连接的键。

将映射输出转换为集合键列表 (a,b,c) => 元素集合

val step1 = mappedOutput.groupByKey().map(x => (x._1, x._2.toSet))

附加组合代码作为步骤 1 的关键

val step2 = step1.map(x => combinations.filter(y => y.contains(x._1)).map(y => (y, x))).flatMap(x => x)

输出将是（ab，（a，a中的元素集），（ac，（a，a中的元素集））等。由于过滤器，我们不会将组合代码bc附加到设置一个.

现在使用reduce得到我想要的结果

val result = step2.reduceByKey((a, b) => ("", a.intersect(b))).map(x => (x._1, x._2._2))

现在我们得到了我在开始时提到的我们想要的输出。剩下的就是把这个结果转化为你需要的，这个很简单。

val transformed = result.map(x => x._2.subsets.filter(x => x.size == 2).map(y => (x._1, y.mkString(" ")))).flatMap(x => x)

结束:)

How to find all two pairs of sets and elements in a collection using MapReduce in Spark?