在Java數組中排列位的最快方法

Question

對Java字節數組中的所有位進行隨機（但重複）置換的最快方法是什麼？我試過用BitSet成功做到這一點，但是有沒有更快的方法？很明顯，for循環消耗了大部分CPU時間。

我剛剛在我的IDE中完成了一些分析，for循環構成了整個permute（）方法中64％的cpu時間。

爲了說明問題，數組（preRound）包含一個現有的數組數組。我希望將該數組的各個設置位以隨機方式混合起來。這是P []的原因。它包含一個隨機的比特位置列表。例如，如果preRound的第13位被設置，它將被傳送到postRound的P [13]位置。這可能在postRound的位置20555。整個事情是替代 - 置換網絡的一部分，我正在尋找以最快的方式來排列傳入的比特。

到目前爲止我的代碼...

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

僅供參考，塊大小是約60000和P是隨機查找表。

Answer 1

我沒有執行任何性能測試，但您可能需要考慮以下內容： 要省略對Arrays.copyOf的調用（它複製使用interally的long []的副本，這非常煩人） ，只需設置最後一位，以防之前未設置，然後再取消設置。

此外，還有一個很好的習慣用法是迭代輸入置換中的置位。

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

如果不削減，如果你使用了大量的重複相同的P，它可能是值得考慮改造成的置換週期符號和就地進行改造。 通過這種方式，您可以對P進行線性迭代，使您可以更好地利用緩存（P是字節數組的32倍，假設它是一個int數組）。然而，你將失去這樣的優勢，你只需要看1並最終在字節數組中的每個位周圍移動，不管是否設置。

如果你想避免使用BitSet中，你可以自己動手完成它：

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