scala - 如何在 Scala 中编写高效的 groupBy-size 过滤器，可以近似

Question

给定Scala中的List[Int]，我希望获得至少出现的所有Int的Set[Int] 脱粒次。我可以使用 groupBy 或 foldLeft，然后使用 filter 来完成此操作。例如:

val thresh = 3
val myList = List(1,2,3,2,1,4,3,2,1)
myList.foldLeft(Map[Int,Int]()){case(m, i) => m + (i -> (m.getOrElse(i, 0) + 1))}.filter(_._2 >= thresh).keys

将给出Set(1,2)。

现在假设List[Int]非常大。很难说有多大，但无论如何，这似乎很浪费，因为我不关心每个 Int 频率，我只关心它们是否至少 thresh.一旦通过了 thresh，就不再需要检查，只需将 Int 添加到 Set[Int] 即可。

问题是:对于非常大的 List[Int]，我能否更有效地执行此操作，

a) 如果我需要真实、准确的结果(不允许出现错误)

b) 如果结果可以是近似值，例如通过使用一些哈希技巧或布隆过滤器，其中 Set[Int] 可能包含一些误报，或者是否{Int 的频率 > thresh} 并不是真正的 Boolean，而是 [0-1] 中的 Double。

Answer 1

首先，您不能做得比 O(N) 更好，因为您需要至少检查一次初始数组的每个元素。您当前的方法是 O(N)，假设 IntMap 的操作实际上是恒定的。

现在您可以尝试以下方法来提高效率:

• 仅当当前计数器值小于或等于阈值时更新映射。这将消除大量最昂贵的操作—— map 更新
• 尝试更快的映射而不是 IntMap。如果您知道初始List的值在固定范围内，则可以使用Array代替IntMap(索引作为键)。另一种可能的选择是具有足够 initail 容量的可变 HashMap。正如我的基准测试所示，它实际上产生了显着的差异
• 正如 @ixx 所建议的，在增加映射中的值后，检查它是否等于 3，在这种情况下立即将其添加到结果列表中。这将为您节省一次线性遍历(对于大输入来说似乎并不那么重要)

我不明白任何近似解决方案如何能够更快(仅当您随机忽略某些元素时)。否则仍然是 O(N)。

更新

我创建了微基准测试来衡量不同实现的实际性能。对于足够大的输入和输出，Ixx 关于立即将元素添加到结果列表的建议不会产生显着的改进。然而，可以使用类似的方法来消除不必要的 map 更新(这似乎是最昂贵的操作)。

基准测试结果(预热后 1000000 个元素的平均运行时间):

Authors solution:
447 ms
Ixx solution:
412 ms
Ixx solution2 (eliminated excessive map writes):
150 ms
My solution:
57 ms

我的解决方案涉及使用可变的HashMap而不是不可变的IntMap，并包括所有其他可能的优化。

Ixx 的更新解决方案:

val tuple = (Map[Int, Int](), List[Int]())
val res = myList.foldLeft(tuple) {
  case ((m, s), i) =>
    val count = m.getOrElse(i, 0) + 1
    (if (count <= 3) m + (i -> count) else m, if (count == thresh) i :: s else s)
}

我的解决方案:

val map = new mutable.HashMap[Int, Int]()
val res = new ListBuffer[Int]
myList.foreach {
  i =>
    val c = map.getOrElse(i, 0) + 1
    if (c == thresh) {
      res += i
    }
    if (c <= thresh) {
      map(i) = c
    }
}

完整的微基准源已可用 here .