| java.lang.Object
 org.apache.solr.util.OpenBitSet
| OpenBitSet | | public class OpenBitSet implements Cloneable,Serializable(Code) | | An "open" BitSet implementation that allows direct access to the array of words
storing the bits.
Unlike java.util.bitet, 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).
If you want a "safe", totally encapsulated (and slower and limited) BitSet
class, use java.util.BitSet.
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.
| cardinality | intersect_count | union | nextSetBit | get | iterator |
| 50% full | 3.36 | 3.96 | 1.44 | 1.46 | 1.99 | 1.58 |
| 1% full | 3.31 | 3.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.
| cardinality | intersect_count | union | nextSetBit | get | iterator |
| 50% full | 2.50 | 3.50 | 1.00 | 1.03 | 1.12 | 1.25 |
| 1% full | 2.51 | 3.49 | | 1.00 | | 1.02 |
author:
yonik
version:
$Id$ |
| Field Summary | |
| protected long[] | bits
| | protected int | wlen
|
| Constructor Summary | |
| public | OpenBitSet(long numBits)
Constructs an OpenBitSet large enough to hold numBits. | | public | OpenBitSet()
| | public | OpenBitSet(long[] bits, int numWords)
Constructs an OpenBitSet from an existing long[]. |
| Method Summary | |
| public void | and(OpenBitSet other)
| | public void | andNot(OpenBitSet other)
| | public static long | andNotCount(OpenBitSet a, OpenBitSet b)
Returns the popcount or cardinality of "a and not b"
or "intersection(a, not(b))". | | public static int | bits2words(long numBits)
| | public long | capacity()
| | public long | cardinality()
| | public void | clear(long index)
| | public Object | clone()
| | public void | ensureCapacity(long numBits)
Ensure that the long[] is big enough to hold numBits, expanding it if necessary. | | public void | ensureCapacityWords(int numWords)
Expand the long[] with the size given as a number of words (64 bit longs). | | public boolean | equals(Object o)
| | protected int | expandingWordNum(long index)
| | public void | fastClear(int index)
clears a bit. | | public void | fastClear(long index)
clears a bit. | | public void | fastFlip(int index)
flips a bit. | | public void | fastFlip(long index)
flips a bit. | | public boolean | fastGet(int index)
Returns true or false for the specified bit index. | | public boolean | fastGet(long index)
Returns true or false for the specified bit index. | | public void | fastSet(int index)
Sets the bit at the specified index. | | public void | fastSet(long index)
Sets the bit at the specified index. | | public void | flip(long index)
| | public void | flip(long startIndex, long endIndex)
| | public boolean | flipAndGet(int index)
flips a bit and returns the resulting bit value. | | public boolean | flipAndGet(long index)
flips a bit and returns the resulting bit value. | | public boolean | get(int index)
Returns true or false for the specified bit index. | | public boolean | get(long index)
| | public boolean | getAndSet(int index)
Sets a bit and returns the previous value. | | public boolean | getAndSet(long index)
Sets a bit and returns the previous value. | | public int | getBit(int index)
returns 1 if the bit is set, 0 if not. | | public long[] | getBits()
| | public int | getNumWords()
| | public int | hashCode()
| | public void | intersect(OpenBitSet other)
| | public static long | intersectionCount(OpenBitSet a, OpenBitSet b)
Returns the popcount or cardinality of the intersection of the two sets. | | public boolean | intersects(OpenBitSet other)
| | public boolean | isEmpty()
| | public int | nextSetBit(int index)
Returns the index of the first set bit starting at the index specified. | | public long | nextSetBit(long index)
Returns the index of the first set bit starting at the index specified. | | public void | or(OpenBitSet other)
| | public void | remove(OpenBitSet other)
Remove all elements set in other. | | public void | set(long index)
| | public void | setBits(long[] bits)
| | public void | setNumWords(int nWords)
| | public long | size()
Returns the current capacity of this set. | | public void | trimTrailingZeros()
Lowers numWords, the number of words in use,
by checking for trailing zero words. | | public void | union(OpenBitSet other)
| | public static long | unionCount(OpenBitSet a, OpenBitSet b)
Returns the popcount or cardinality of the union of the two sets. | | public void | xor(OpenBitSet other)
| | public static long | xorCount(OpenBitSet a, OpenBitSet b)
Returns the popcount or cardinality of the exclusive-or of the two sets. |
| bits | | protected long[] bits(Code) | | |
| OpenBitSet | | public OpenBitSet(long numBits)(Code) | | Constructs an OpenBitSet large enough to hold numBits.
Parameters:
numBits - |
| OpenBitSet | | public OpenBitSet()(Code) | | |
| OpenBitSet | | public OpenBitSet(long[] bits, int numWords)(Code) | | 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.
numWords are the number of elements in the array that contain
set bits (non-zero longs).
numWords should be <= bits.length, and
any existing words in the array at position >= numWords should be zero.
|
| andNotCount | | public static long andNotCount(OpenBitSet a, OpenBitSet b)(Code) | | Returns the popcount or cardinality of "a and not b"
or "intersection(a, not(b))".
Neither set is modified.
|
| bits2words | | public static int bits2words(long numBits)(Code) | | returns the number of 64 bit words it would take to hold numBits
|
| capacity | | public long capacity()(Code) | | Returns the current capacity in bits (1 greater than the index of the last bit)
|
| cardinality | | public long cardinality()(Code) | | the number of set bits |
| clear | | public void clear(long index)(Code) | | clears a bit, allowing access beyond the current set size
|
| ensureCapacity | | public void ensureCapacity(long numBits)(Code) | | Ensure that the long[] is big enough to hold numBits, expanding it if necessary.
getNumWords() is unchanged by this call.
|
| ensureCapacityWords | | public void ensureCapacityWords(int numWords)(Code) | | Expand the long[] with the size given as a number of words (64 bit longs).
getNumWords() is unchanged by this call.
|
| equals | | public boolean equals(Object o)(Code) | | returns true if both sets have the same bits set
|
| expandingWordNum | | protected int expandingWordNum(long index)(Code) | | |
| fastClear | | public void fastClear(int index)(Code) | | clears a bit.
The index should be less than the OpenBitSet size.
|
| fastClear | | public void fastClear(long index)(Code) | | clears a bit.
The index should be less than the OpenBitSet size.
|
| fastFlip | | public void fastFlip(int index)(Code) | | flips a bit.
The index should be less than the OpenBitSet size.
|
| fastFlip | | public void fastFlip(long index)(Code) | | flips a bit.
The index should be less than the OpenBitSet size.
|
| fastGet | | public boolean fastGet(int index)(Code) | | Returns true or false for the specified bit index.
The index should be less than the OpenBitSet size
|
| fastGet | | public boolean fastGet(long index)(Code) | | Returns true or false for the specified bit index. Allows specifying
an index outside the current size.
|
| fastSet | | public void fastSet(int index)(Code) | | Sets the bit at the specified index.
The index should be less than the OpenBitSet size.
|
| fastSet | | public void fastSet(long index)(Code) | | Sets the bit at the specified index.
The index should be less than the OpenBitSet size.
|
| flip | | public void flip(long index)(Code) | | flips a bit, expanding the set size if necessary
|
| flip | | public void flip(long startIndex, long endIndex)(Code) | | Flips a range of bits, expanding the set size if necessary
Parameters:
startIndex - lower index
Parameters:
endIndex - one-past the last bit to flip |
| flipAndGet | | public boolean flipAndGet(int index)(Code) | | flips a bit and returns the resulting bit value.
The index should be less than the OpenBitSet size.
|
| flipAndGet | | public boolean flipAndGet(long index)(Code) | | flips a bit and returns the resulting bit value.
The index should be less than the OpenBitSet size.
|
| get | | public boolean get(int index)(Code) | | Returns true or false for the specified bit index.
|
| get | | public boolean get(long index)(Code) | | Returns true or false for the specified bit index
The index should be less than the OpenBitSet size
|
| getAndSet | | public boolean getAndSet(int index)(Code) | | Sets a bit and returns the previous value.
The index should be less than the OpenBitSet size.
|
| getAndSet | | public boolean getAndSet(long index)(Code) | | Sets a bit and returns the previous value.
The index should be less than the OpenBitSet size.
|
| getBit | | public int getBit(int index)(Code) | | returns 1 if the bit is set, 0 if not.
The index should be less than the OpenBitSet size
|
| getBits | | public long[] getBits()(Code) | | Expert: returns the long[] storing the bits
|
| getNumWords | | public int getNumWords()(Code) | | Expert: gets the number of longs in the array that are in use
|
| hashCode | | public int hashCode()(Code) | | |
| intersectionCount | | public static long intersectionCount(OpenBitSet a, OpenBitSet b)(Code) | | Returns the popcount or cardinality of the intersection of the two sets.
Neither set is modified.
|
| intersects | | public boolean intersects(OpenBitSet other)(Code) | | returns true if the sets have any elements in common
|
| isEmpty | | public boolean isEmpty()(Code) | | Returns true if there are no set bits
|
| nextSetBit | | public int nextSetBit(int index)(Code) | | Returns the index of the first set bit starting at the index specified.
-1 is returned if there are no more set bits.
|
| nextSetBit | | public long nextSetBit(long index)(Code) | | Returns the index of the first set bit starting at the index specified.
-1 is returned if there are no more set bits.
|
| remove | | public void remove(OpenBitSet other)(Code) | | Remove all elements set in other. this = this AND_NOT other
|
| set | | public void set(long index)(Code) | | sets a bit, expanding the set size if necessary
|
| setBits | | public void setBits(long[] bits)(Code) | | Expert: sets a new long[] to use as the bit storage
|
| setNumWords | | public void setNumWords(int nWords)(Code) | | Expert: sets the number of longs in the array that are in use
|
| size | | public long size()(Code) | | Returns the current capacity of this set. Included for
compatibility. This is *not* equal to
OpenBitSet.cardinality |
| trimTrailingZeros | | public void trimTrailingZeros()(Code) | | Lowers numWords, the number of words in use,
by checking for trailing zero words.
|
| unionCount | | public static long unionCount(OpenBitSet a, OpenBitSet b)(Code) | | Returns the popcount or cardinality of the union of the two sets.
Neither set is modified.
|
| xorCount | | public static long xorCount(OpenBitSet a, OpenBitSet b)(Code) | | Returns the popcount or cardinality of the exclusive-or of the two sets.
Neither set is modified.
|
|
|