Schnellste Möglichkeit, Bits in einem Java-Array zu permutieren

Question

Was ist der schnellste Weg, um alle Bits innerhalb eines Java-Byte-Arrays zufällig (aber wiederholt) zu permutieren? Ich habe es erfolgreich mit einem BitSet versucht, aber gibt es einen schnelleren Weg? Offensichtlich verbraucht die For-Schleife den Großteil der CPU-Zeit.

Ich habe gerade ein Profiling in meiner IDE gemacht und die for-Schleife macht 64% der CPU-Zeit innerhalb der gesamten Methode permute() aus.

Um zu verdeutlichen, enthält das Array (preRound) eine bestehende Reihe von Zahlen, die in die Prozedur gehen. Ich möchte, dass die einzelnen gesetzten Bits dieses Arrays zufällig gemischt werden. Dies ist der Grund für P []. Es enthält eine zufällige Liste von Bitpositionen. Wenn also zum Beispiel das Bit 13 von preRound gesetzt ist, wird es an den Platz von P [13] von postRound übertragen. Dies könnte an Position 20555 von postRound sein. Das Ganze ist Teil eines Ersatz-Permutations-Netzwerkes, und ich suche den schnellsten Weg, die eingehenden Bits zu permutieren.

Mein Code so weit ...

private byte[] permute(byte[] preRound) { 
    BitSet beforeBits = BitSet.valueOf(preRound); 
    BitSet afterBits = new BitSet(blockSize * 8); 


    for (int i = 0; i < blockSize * 8; i++) { 
     assert i != P[i]; 


     if (beforeBits.get(i)) { 
      afterBits.set(P[i]); 
     } 
    } 


    byte[] postRound = afterBits.toByteArray(); 
    postRound = Arrays.copyOf(postRound, blockSize);  // Pad with 0s to the specified length 
    assert postRound.length == blockSize; 


    return postRound; 
} 

FYI, blocksize etwa 60000 und P ist eine zufällige Lookup-Tabelle.

Answer 1

Ich habe keine Leistungstests durchgeführt, aber Sie sollten folgendes beachten: Den Aufruf von Arrays.copyOf weglassen (wodurch die Kopie des langen [] interaktiv kopiert wird, was irgendwie nervig ist) Setzen Sie einfach das letzte Bit für den Fall, dass es vorher nicht gesetzt wurde, und deaktivieren Sie es anschließend.

Darüber hinaus gibt es ein nettes Idiom über die gesetzten Bits in der Eingabe Permutation zu iterieren.

private byte[] permute(final byte[] preRound) { 
    final BitSet beforeBits = BitSet.valueOf(preRound); 
    final BitSet afterBits = new BitSet(blockSize*8); 
    for (int i = beforeBits.nextSetBit(0); i >= 0; i = 
      beforeBits.nextSetBit(i + 1)) { 
     final int to = P[i]; 
     assert i != to; 
     afterBits.set(to); 
    } 
    final int lastIndex = blockSize*8-1; 
    if (afterBits.get(lastIndex)) { 
     return afterBits.toByteArray(); 
    } 
    afterBits.set(lastIndex); 
    final byte[] postRound = afterBits.toByteArray(); 
    postRound[blockSize - 1] &= 0x7F; 
    return postRound; 
} 

Wenn das auch nicht schneiden, falls Sie die gleiche P für viele Iterationen verwenden, kann es sich lohnen, die Permutation in Zyklus-Notation zu betrachten Transformation und die Transformation an Ort und Stelle durchführen. Auf diese Weise können Sie linear über P iterieren, wodurch Sie Caching besser ausnutzen können (P ist 32 mal so groß wie das Byte-Array, vorausgesetzt, es handelt sich um ein int-Array). Sie werden jedoch den Vorteil verlieren, dass Sie nur 1s betrachten müssen und am Ende um jedes einzelne Bit im Byte-Array verschoben werden müssen, egal ob gesetzt oder nicht.

Wenn Sie die BitSet vermeiden möchten, können Sie tun Sie es einfach von Hand:

private byte[] permute(final byte[] preRound) { 
    final byte[] result = new byte[blockSize]; 
    for (int i = 0; i < blockSize; i++) { 
     final byte b = preRound[i]; 
     // if 1s are sparse, you may want to use this: 
     // if ((byte) 0 == b) continue; 
     for (int j = 0; j < 8; ++j) { 
      if (0 != (b & (1 << j))) { 
       final int loc = P[i * 8 + j]; 
       result[loc/8] |= (1 << (loc % 8)); 
      } 
     } 
    } 
    return result; 
}