scala - 在 Scala 中从谓词构造位集？

Question

假设我想构造一个 BitSet，其中包含从 0 到 n 满足某个 predicate 的所有整数f: Int => Boolean。

我可以写类似的东西

BitSet((0 until n):_*).filter(f)

这当然有效。但是感觉效率很低！我计划在一个非常紧凑的循环中执行此操作，并希望提供更有效方法的建议。

Answer 1

这是我目前能想到的最好的

BitSet((0 until n).view.filter(f):_*)

视图部分使filter方法变得懒惰。这确保当BitSet从给定序列创建时，它将即时过滤。您的原始建议在创建BitSet第一个建议后会创建一个新建议。

Answer 2

我认为最有效的“功能”方式是使用foldLeft：

(1 to 5).foldLeft(BitSet())((s,i) => if (f(i)) s + i else s)

它不会创建中间集合，而是在过滤时从头开始构建集合。

我想到的第一件事是使用breakOut，但它不适用于filter：

scala> val set: BitSet = (0 until 10).filter(f)(collection.breakOut)
<console>:11: error: polymorphic expression cannot be instantiated to expected type;
 found   : [From, T, To]scala.collection.generic.CanBuildFrom[From,T,To]
 required: Int
       val set: BitSet = (0 until 10).filter(f)(collection.breakOut)
                                                           ^

scala> val set: BitSet = (0 until 10).map(_+1)(collection.breakOut)
set: scala.collection.immutable.BitSet = BitSet(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

breakOut也不会创建中间集合，但是因为filter没有第二个参数列表，所以它不能工作。

Answer 3

如果性能确实是您最关心的问题，最好的选择可能是使用一个mutable.BitSet和一个while循环，然后调用toImmutable结果。

val bitSet = {
  val tmp = new scala.collection.mutable.BitSet(n)
  var i = 0;
  while (i < n) {
    if (f(i)) {
      tmp += i
    }
    i = i + 1
  }
  tmp.toImmutable
}