Geek Answers Handbook

Java is the fastest way to get BitSet junction power

The function below takes two BitSets , makes a copy of the first (it should not be redefined), intersects the copy with the second (bitwise AND) and returns the power of the result.

 public int getIntersectionSize(BitSet bits1, BitSet bits2) { BitSet copy = (BitSet) bits1.clone(); copy.and(bits2); return copy.cardinality(); }

I am wondering if this code can be accelerated? This function is called a billion times, so even microsecond speed makes sense, and I'm curious about the fastest code.

+6
source share
3 answers

If you intend to use each BitSet several times, it may be advisable to create a long array corresponding to each BitSet . For each BitSet :

 long[] longs = bitset.toLongArray();

Then you can use the following method, which avoids the overhead of creating a cloned BitSet . (This assumes that both arrays are the same length).

 int getIntersectionSize(long[] bits1, long[] bits2) { int nBits = 0; for (int i=0; i<bits1.length; i++) nBits += Long.bitCount(bits1[i] & bits2[i]); return nBits; }
+2
source

Here is an alternate version, but I'm not sure if it is really faster, depends on nextSetBit .

 public int getIntersectionsSize(BitSet bits1, BitSet bits2) { int count = 0; int i = bits1.nextSetBit(0); int j = bits2.nextSetBit(0); while (i >= 0 && j >= 0) { if (i < j) { i = bits1.nextSetBit(i + 1); } else if (i > j) { j = bits2.nextSetBit(j + 1); } else { count++; i = bits1.nextSetBit(i + 1); j = bits2.nextSetBit(j + 1); } } return count; }

The above version is hopefully good enough for the compiler, but you can optimize it manually, I think:

 public int getIntersectionsSize(BitSet bits1, BitSet bits2) { int count = 0; for (int i = bits1.nextSetBit(0), j = bits2.nextSetBit(0); i >= 0 && j >= 0; ) { while (i < j) { i = bits1.nextSetBit(i + 1); if (i < 0) return count; } if (i == j) { count++; i = bits1.nextSetBit(i + 1); } while (j < i) { j = bits2.nextSetBit(j + 1); if (j < 0) return count; } if (i == j) { count++; j = bits2.nextSetBit(j + 1); } } return count; }
+1
source

I recently searched for a solution to this problem, and here is what I came up with:

 int intersectionCardinality(final BitSet lhs, final BitSet rhs) { int lhsNext; int retVal = 0; int rhsNext = 0; while ((lhsNext = lhs.nextSetBit(rhsNext)) != -1 && (rhsNext = rhs.nextSetBit(lhsNext)) != -1) { if (rhsNext == lhsNext) { retVal++; rhsNext++; } } return retVal; }

Maybe someone would like to take the time to compare different solutions here and post the results ...

0
source

More articles:


All Articles