- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
给定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
。
最佳答案
首先,您不能做得比 O(N) 更好,因为您需要至少检查一次初始数组的每个元素。您当前的方法是 O(N),假设 IntMap
的操作实际上是恒定的。
现在您可以尝试以下方法来提高效率:
Array
代替IntMap
(索引作为键)。另一种可能的选择是具有足够 initail 容量的可变 HashMap。正如我的基准测试所示,它实际上产生了显着的差异我不明白任何近似解决方案如何能够更快(仅当您随机忽略某些元素时)。否则仍然是 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 .
关于scala - 如何在 Scala 中编写高效的 groupBy-size 过滤器,可以近似,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31973386/
我是一名优秀的程序员,十分优秀!