Najszybszy sposób na uzyskanie Javy liczności przecięcia BitSet

Question

Poniższa funkcja pobiera dwie wartości: BitSets, tworzy kopię pierwszej (nie może być przesłonięta), przecina kopię z drugą (bitową ORAZ) i zwraca liczność wyniku .

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

Jestem zainteresowany, czy ten kod może zostać przyspieszony? Ta funkcja nazywa się miliard razy, więc nawet mikrosekundowe przyspieszenie ma sens i jestem ciekawy najszybszego możliwego kodu.

Answer 1

Oto alternatywna wersja, ale nie jestem pewien, czy jest naprawdę szybszy, zależy od 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; 
} 

Powyższa wersja jest czytelny, mam nadzieję, że wystarczająco dobre dla kompilatora, ale można je zoptymalizować ręcznie Chyba:

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; 
} 

Answer 2

Jeśli masz zamiar użyć każdy BitSet kilkakrotnie go warto byłoby utworzyć tablicę long odpowiadającą każdemu BitSet. Dla każdego BitSet:

long[] longs = bitset.toLongArray(); 

Następnie można użyć następującą metodę, która unika napowietrznej tworzenia sklonowany BitSet. (Zakłada się, że obie tablice mają tę samą długość).

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; 
}