Java più veloce per ottenere la cardinalità dell'intersezione BitSet

Question

La funzione seguente richiede due BitSets, crea una copia del primo (non deve essere sovrascritta), interseca la copia con il secondo (bit AND) e restituisce la cardinalità del risultato .

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

Sono interessato se questo codice può essere velocizzato? Questa funzione è chiamata miliardi di volte quindi anche un accelerazione in microsecondi ha senso, più sono curioso del codice più veloce possibile.

Answer 1

Ecco una versione alternativa, ma non sono sicuro se è molto più veloce, dipende da 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; 
} 

Quanto sopra è la versione leggibile, si spera abbastanza buono per il compilatore, ma si potrebbe ottimizzare manualmente immagino:

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

Se avete intenzione di utilizzare ogni BitSet più volte, potrebbe essere utile creare un array long corrispondente a ogni BitSet. Per ogni BitSet:

long[] longs = bitset.toLongArray(); 

quindi è possibile utilizzare il seguente metodo, che evita il sovraccarico di creare un clonato BitSet. (Ciò presuppone che entrambi gli array abbiano la stessa lunghezza).

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