You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
immutable.BitSet's builder uses an immutable.BitSet inside, and every time a new element is added to the builder it copies this BitSet. This makes methods like BitSet.++, which use the builder, run in O(N^2) rather than O(N) time, which makes creating immutable.BitSets with large sets very difficult.
Here is a new implementation that solves this problem:
/** A builder that takes advantage of mutable BitSets. */defnewBuilder:Builder[Int, BitSet] =newBuilder[Int, BitSet] withProxy {
valself=new mutable.BitSetdef+=(x: Int):this.type= {self += x; this}
defclear() = {self.clear}
defresult:BitSet= self.toImmutable
}
The text was updated successfully, but these errors were encountered:
@dcsobral said (edited on May 25, 2011 8:02:09 PM UTC):
That doesn't look thread-safe to me. Then again, I'm not sure if a Builder is supposed to be thread-safe or not.
Stephen Marsh (smarsh) said:
It's not thread-safe. But the old builder using SetBuilder relies on updating a var without any synchronization, so it isn't thread-safe either, and neither were any of the other Builders I looked at (for List etc.). If it needs to be thread-safe, only the += method needs to be synchronized.
immutable.BitSet's builder uses an immutable.BitSet inside, and every time a new element is added to the builder it copies this BitSet. This makes methods like BitSet.++, which use the builder, run in O(N^2) rather than O(N) time, which makes creating immutable.BitSets with large sets very difficult.
Here is a new implementation that solves this problem:
The text was updated successfully, but these errors were encountered: