scala - 述語からScalaでビットセットを構築しますか？

Question

0からnまでのすべての整数を含むBitSetを作成して、いくつかの述語を満たすとし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ませんが、2番目のパラメーターリストがないため、機能しません。

Answer 3

パフォーマンスが本当にあなたの主な関心事である場合、最良のオプションはおそらくamutable.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
}