java - 置换 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;
}

仅供引用，blockSize 约为 60,000，P 是一个随机查找表。

Answer 1

我没有执行任何性能测试，但您可能需要考虑以下内容:要省略对 Arrays.copyOf 的调用(它会复制内部使用的 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;
}