时间戳

首页 > 解决方案 > Scala 中集合的交集

scala - Scala 中集合的交集

问题描述

我HashMap在 Scala 中有以下形式：

HashMap(
37 -> HashSet(5, 1, 6, 9, 13, 12, 3, 8, 4),
20 -> HashSet(5, 1, 6, 9, 13, 12, 3, 8, 4), 
45 -> HashSet(5, 6, 9, 13, 3, 8, 4), 
49 -> HashSet(5, 6, 9, 13, 3, 8, 4), 
39 -> Set(5, 12, 3, 9), 
31 -> HashSet(5, 6, 9, 13, 3, 8, 4),
15 -> Set(5, 9, 3), 
28 -> Set(5, 3, 9), 
21 -> HashSet(5, 6, 9, 13, 3, 8, 4), 
33 -> Set(9, 3), 
40 -> HashSet(5, 1, 6, 9, 13, 12, 3, 8, 4), 
26 -> Set(9, 3, 5), 
55 -> Set(6, 4, 8),
23 -> Set(9, 5, 3, 12), 
36 -> Set(7, 2), 
19 -> Set(5, 9, 3))

获取地图中所有集合的交集的最有效方法是什么？

问题是这些映射和集合可能会变得很大，并且在递归算法中需要大量的交集（一次执行中最多调用 10K 次），而For comprehensionScala 中的方法并没有有效地解决这个问题。

编辑 ：

至于For comprehension我只是做了一个简单的函数来计算它（它有一个可以优化的无用交集，第一个，与大量调用无关。我也可以在交集为空时停止计算，但很少发生但我避免空值的交集，因为理论上在我的算法中，地图不应该有空值的键：

def stateIntersection(m: Map[Int, Set[Int]]): Set[Int] = {
    var acc = m.head._2
    for ((k, v) <- m) {
      if (v.nonEmpty)
        acc = acc.intersect(v)
    }
    acc
  }

标签： scalafunctional-programminghashmapset

解决方案

您的集合中的值是否有下限和上限？如果他们这样做，并且范围相当小（例如，0..1000），一种有效的方法（在任何语言中）可能是创建一个固定大小的数组 int[0..1000]，然后遍历所有集合并增加相应的数组元素。这是一个恒定时间操作，不像在集合中搜索，这将不可避免地成为上述算法的一部分。

counters = int[1000] // assuming it's initialized with 0's
for set in sets {
  for element in set.elements {
    counters[element]++
  }
}

然后，您只需收集值等于集合数的数组元素。

推荐阅读