2

给定List[Int]Scala 中的 a ，我希望得到至少出现次数Set[Int]的所有s 。我可以使用or , then来做到这一点。例如：IntthreshgroupByfoldLeftfilter

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]非常大。很难说有多大，但无论如何这似乎很浪费，因为我不关心每个Ints 频率，我只关心它们是否至少是thresh. 一旦它通过thresh了，就不需要再检查了，只需Int将Set[Int].

问题是：对于一个非常大的，我可以更有效地做到这一点List[Int]，

a) 如果我需要一个真实、准确的结果（没有出错的余地）

b) 如果结果可以是近似的，例如通过使用一些散列技巧或布隆过滤器，其中Set[Int]可能包含一些误报，或者 {the frequency of an Int> thresh} 是否真的不是 aBoolean而是 a Doublein [0-1]。

4

4 回答 4

3

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

现在你可以尝试什么来提高效率：

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

我看不出任何近似解决方案如何更快（仅当您随机忽略某些元素时）。否则它仍然是 O(N)。

更新

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

基准测试结果（预热后 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
    }
}

完整的微基准测试源可在此处获得。

于 2015-08-12T20:21:14.930 回答
1

If by "more efficiently" you mean the space efficiency (in extreme case when the list is infinite), there's a probabilistic data structure called Count Min Sketch to estimate the frequency of items inside it. Then you can discard those with frequency below your threshold.

There's a Scala implementation from Algebird library.

于 2015-08-12T21:44:23.150 回答
1

您可以使用foldleft来收集匹配的项目，如下所示：

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

我可以用一个小列表测量大约 40% 的性能改进，所以这绝对是一个改进......

编辑为使用List和前置，这需要恒定的时间（见评论）。

于 2015-08-12T20:08:09.420 回答
0

foldLeft您可以使用增量构建的 a 稍微 更改您的示例mutable.Set，同时用作过滤器Seq以使用withFilter. 但是，因为我正在使用withFilter我不能使用foldLeft并且不得不使用foreach可变地图：

import scala.collection.mutable

def getItems[A](in: Seq[A], threshold: Int): Set[A] = {
  val counts: mutable.Map[A, Int] = mutable.Map.empty
  val result: mutable.Set[A] = mutable.Set.empty

  in.withFilter(!result(_)).foreach { x =>
    counts.update(x, counts.getOrElse(x, 0) + 1)

    if (counts(x) >= threshold) {          
      result += x
    }
  }
  result.toSet
}

Seq因此，这将丢弃在第一次运行时已经添加到结果集中的项目，因为在附加函数 ( ) 中withFilter过滤而不是返回过滤的。Seqmap, flatMap, foreachSeq

编辑：

正如Aivean正确指出的那样，我将解决方案更改为 not use Seq.count，这很愚蠢。

使用Aiveans microbench，我可以看到它仍然比他的方法稍慢，但仍然比作者的第一种方法好。

Authors solution
377
Ixx solution: 
399
Ixx solution2 (eliminated excessive map writes): 
110
Sascha Kolbergs solution: 
72
Aivean solution: 
54
于 2015-08-12T20:02:03.407 回答