Class OpenBitSet
An "open" BitSet implementation that allows direct access to the array of words storing the bits.
NOTE: This can be used in .NET any place where a java.util.BitSet is used in Java.
Unlike java.util.BitSet, the fact that bits are packed into an array of longs
is part of the interface. This allows efficient implementation of other algorithms
by someone other than the author. It also allows one to efficiently implement
alternate serialization or interchange formats.
OpenBitSet is faster than java.util.BitSet in most operations
and much faster at calculating cardinality of sets and results of set operations.
It can also handle sets of larger cardinality (up to 64 * 2**32-1)
The goals of OpenBitSet are the fastest implementation possible, and maximum code reuse. Extra safety and encapsulation may always be built on top, but if that's built in, the cost can never be removed (and hence people re-implement their own version in order to get better performance).
Performance Results
Test system: Pentium 4, Sun Java 1.5_06 -server -Xbatch -Xmx64M
BitSet size = 1,000,000
Results are java.util.BitSet time divided by OpenBitSet time.
| cardinalityIntersectionCountUnionNextSetBitGetGetIterator | |
|---|---|
| 50% full | 3.363.961.441.461.991.58 |
| 1% full | 3.313.90 1.04 0.99 |
Test system: AMD Opteron, 64 bit linux, Sun Java 1.5_06 -server -Xbatch -Xmx64M
BitSet size = 1,000,000
Results are java.util.BitSet time divided by OpenBitSet time.
| cardinalityIntersectionCountUnionNextSetBitGetGetIterator | |
|---|---|
| 50% full | 2.503.501.001.031.121.25 |
| 1% full | 2.513.49 1.00 1.02 |
Inherited Members
Assembly: DistributedLucene.Net.dll
Syntax
public class OpenBitSet : DocIdSet, IBitsConstructors
| Name | Description |
|---|---|
| OpenBitSet() | Constructor: allocates enough space for 64 bits. |
| OpenBitSet(Int64) | Constructs an OpenBitSet large enough to hold |
| OpenBitSet(Int64[], Int32) | Constructs an OpenBitSet from an existing long[]. The first 64 bits are in long[0], with bit index 0 at the least significant bit, and bit index 63 at the most significant. Given a bit index, the word containing it is long[index/64], and it is at bit number index%64 within that word.
|
Fields
| Name | Description |
|---|---|
| m_bits | |
| m_wlen |
Properties
| Name | Description |
|---|---|
| Bits | |
| Capacity | Returns the current capacity in bits (1 greater than the index of the last bit). |
| IsCacheable | This DocIdSet implementation is cacheable. |
| IsEmpty | Returns |
| Length | Returns the current capacity of this set. This is not equal to Cardinality(). NOTE: This is equivalent to size() or length() in Lucene. |
| NumWords | Expert: gets the number of |
Methods
| Name | Description |
|---|---|
| And(OpenBitSet) | |
| AndNot(OpenBitSet) | |
| AndNotCount(OpenBitSet, OpenBitSet) | Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified. |
| Bits2words(Int64) | Returns the number of 64 bit words it would take to hold |
| Cardinality() | Get the number of set bits. |
| Clear(Int32, Int32) | Clears a range of bits. Clearing past the end does not change the size of the set. |
| Clear(Int64) | Clears a bit, allowing access beyond the current set size without changing the size. |
| Clear(Int64, Int64) | Clears a range of bits. Clearing past the end does not change the size of the set. |
| Clone() | |
| EnsureCapacity(Int64) | Ensure that the long[] is big enough to hold numBits, expanding it if necessary. |
| EnsureCapacityWords(Int32) | Expand the long[] with the size given as a number of words (64 bit longs). |
| Equals(Object) | Returns |
| ExpandingWordNum(Int64) | |
| FastClear(Int32) | Clears a bit.
The |
| FastClear(Int64) | Clears a bit.
The |
| FastFlip(Int32) | Flips a bit.
The |
| FastFlip(Int64) | Flips a bit.
The |
| FastGet(Int32) | Returns |
| FastGet(Int64) | Returns |
| FastSet(Int32) | Sets the bit at the specified |
| FastSet(Int64) | Sets the bit at the specified |
| Flip(Int64) | Flips a bit, expanding the set size if necessary. |
| Flip(Int64, Int64) | Flips a range of bits, expanding the set size if necessary. |
| FlipAndGet(Int32) | Flips a bit and returns the resulting bit value.
The |
| FlipAndGet(Int64) | Flips a bit and returns the resulting bit value.
The |
| Get(Int32) | Returns |
| Get(Int64) | Returns |
| GetAndSet(Int32) | Sets a bit and returns the previous value.
The |
| GetAndSet(Int64) | Sets a bit and returns the previous value.
The |
| GetBit(Int32) | Returns 1 if the bit is set, 0 if not.
The |
| GetBits() | Expert: returns the long[] storing the bits. |
| GetHashCode() | |
| GetIterator() | |
| Intersect(OpenBitSet) | this = this AND other |
| IntersectionCount(OpenBitSet, OpenBitSet) | Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified. |
| Intersects(OpenBitSet) | returns |
| NextSetBit(Int32) | Returns the index of the first set bit starting at the |
| NextSetBit(Int64) | Returns the index of the first set bit starting at the |
| Or(OpenBitSet) | |
| PrevSetBit(Int32) | Returns the index of the first set bit starting downwards at
the |
| PrevSetBit(Int64) | Returns the index of the first set bit starting downwards at
the |
| Remove(OpenBitSet) | Remove all elements set in other. this = this AND_NOT other. |
| Set(Int64) | Sets a bit, expanding the set size if necessary. |
| Set(Int64, Int64) | Sets a range of bits, expanding the set size if necessary. |
| TrimTrailingZeros() | Lowers numWords, the number of words in use, by checking for trailing zero words. |
| Union(OpenBitSet) | this = this OR other |
| UnionCount(OpenBitSet, OpenBitSet) | Returns the popcount or cardinality of the union of the two sets. Neither set is modified. |
| Xor(OpenBitSet) | this = this XOR other |
| XorCount(OpenBitSet, OpenBitSet) | Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified. |
