有效地从byte []数组中提取任意长度的位序列

Question

我正在寻找在任意位置提取任意长度(0 <=长度<= 16)的(无符号)位序列的最有效方法.骨架类显示了我当前的实现如何处理问题:

public abstract class BitArray {

byte[] bytes = new byte[2048];
int bitGet;

public BitArray() {
}

public void readNextBlock(int initialBitGet, int count) {
    // substitute for reading from an input stream 
    for (int i=(initialBitGet>>3); i<=count; ++i) {
        bytes[i] = (byte) i;
    }
    prepareBitGet(initialBitGet, count);
}

public abstract void prepareBitGet(int initialBitGet, int count);

public abstract int getBits(int count);

static class Version0 extends BitArray {
    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
    }

    public int getBits(int len) {
        // intentionally gives meaningless result
        bitGet += len;
        return 0;
    }
}

static class Version1 extends BitArray {
    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet - 1;
    }

    public int getBits(int len) {
        int byteIndex = bitGet;
        bitGet = byteIndex + len;
        int shift = 23 - (byteIndex & 7) - len;
        int mask = (1 << len) - 1;
        byteIndex >>= 3;
        return (((bytes[byteIndex] << 16) | 
               ((bytes[++byteIndex] & 0xFF) <<  8) |
                (bytes[++byteIndex] & 0xFF)) >> shift) & mask;
    }
}

static class Version2 extends BitArray {
    static final int[] mask = { 0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF,
                0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };

    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
    }

    public int getBits(int len) {
        int offset = bitGet;
        bitGet = offset + len;
        int byteIndex = offset >> 3; // originally used /8
        int bitIndex = offset & 7;   // originally used %8
        if ((bitIndex + len) > 16) {
            return ((bytes[byteIndex] << 16 |
                    (bytes[byteIndex + 1] & 0xFF) << 8 |
                    (bytes[byteIndex + 2] & 0xFF)) >> (24 - bitIndex - len)) & mask[len];
        } else if ((offset + len) > 8) {
            return ((bytes[byteIndex] << 8 |
                    (bytes[byteIndex + 1] & 0xFF)) >> (16 - bitIndex - len)) & mask[len];
        } else {
            return (bytes[byteIndex] >> (8 - offset - len)) & mask[len];
        }
    }
}

static class Version3 extends BitArray {
    int[] ints = new int[2048];

    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
        int put_i = (initialBitGet >> 3) - 1;
        int get_i = put_i;
        int buf;
        buf = ((bytes[++get_i] & 0xFF) << 16) |
              ((bytes[++get_i] & 0xFF) <<  8) |
               (bytes[++get_i] & 0xFF);
        do {
            buf = (buf << 8) | (bytes[++get_i] & 0xFF);
            ints[++put_i] = buf;
        } while (get_i < count);
    }

    public int getBits(int len) {
        int bit_idx = bitGet;
        bitGet = bit_idx + len;
        int shift = 32 - (bit_idx & 7) - len;
        int mask = (1 << len) - 1;
        int int_idx = bit_idx >> 3;
        return (ints[int_idx] >> shift) & mask;
    }
}

static class Version4 extends BitArray {
    int[] ints = new int[1024];

    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
        int g = initialBitGet >> 3;
        int p = (initialBitGet >> 4) - 1;
        final byte[] b = bytes;
        int t = (b[g]  <<  8) | (b[++g] & 0xFF);
        final int[] i = ints;
        do {
            i[++p] = (t = (t << 16) | ((b[++g] & 0xFF) <<8) | (b[++g] & 0xFF));
        } while (g < count);
    }

    public int getBits(final int len) {
        final int i;
        bitGet = (i = bitGet) + len;
        return (ints[i >> 4] >> (32 - len - (i & 15))) & ((1 << len) - 1);
    }
}

public void benchmark(String label) {
    int checksum = 0;
    readNextBlock(32, 1927);
    long time = System.nanoTime();
    for (int pass=1<<18; pass>0; --pass) {
        prepareBitGet(32, 1927);
        for (int i=2047; i>=0; --i) {
            checksum += getBits(i & 15);
        }
    }
    time = System.nanoTime() - time;
    System.out.println(label+" took "+Math.round(time/1E6D)+" ms, checksum="+checksum);
    try { // avoid having the console interfere with our next measurement
        Thread.sleep(369);
    } catch (InterruptedException e) {}
}

public static void main(String[] argv) {
    BitArray test;
    // for the sake of getting a little less influence from the OS for stable measurement
    Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
    while (true) {
        test = new Version0();
        test.benchmark("no implementaion");
        test = new Version1();
        test.benchmark("Durandal's (original)");
        test = new Version2();
        test.benchmark("blitzpasta's (adapted)");
        test = new Version3();
        test.benchmark("MSN's (posted)");
        test = new Version4();
        test.benchmark("MSN's (half-buffer modification)");
        System.out.println("--- next pass ---");
    }
}
}

这有效,但我正在寻找一种更有效的解决方案(性能明智).保证字节数组相对较小,在几个字节之间,最大为~1800字节.在每次调用read方法之间,只读取一次(完全)数组.getBits()中不需要任何错误检查,例如超出数组等.

---

看来我上面的初步问题还不够明确.N比特的"比特序列"形成N比特的整数,并且我需要以最小的开销提取那些整数.我没有使用字符串,因为这些值既可以用作查找索引,也可以直接输入到某些计算中.所以基本上,上面显示的骨架是一个真正的类,getBits()签名显示了其余代码如何与它交互.

---

将示例代码扩展到微基准测试中,包括blitzpasta的解决方案(修复丢失的字节屏蔽).在我的旧AMD盒子上,结果为~11400ms vs~38000ms.仅供参考:其分裂和模数操作会破坏性能.如果您要更换/ 8与>> 3和%8与和7,这两种解决方案都相当接近对方(jdk1.7.0ea104).

---

关于如何工作以及如何工作似乎有点混乱.示例代码的第一个原始帖子包含一个read()方法,用于指示填充字节缓冲区的位置和时间.当代码变成微基座时,这就丢失了.我重新介绍它,使它更清晰一点.我们的想法是通过添加另一个需要实现getBits()和prepareBitGet()的BitArray子类来击败所有现有版本,后者可能是空的.不要更改基准测试以使您的解决方案具有优势,对所有现有解决方案也可以这样做,这使得这完全没有实际优化!(真!!)

我添加了一个Version0,它只会增加bitGet状态.它总是返回0,以便大致了解基准开销有多大.它仅用于比较.

此外,还增加了对MSN思想的改编(版本3).为了使所有竞争对手保持公平和可比性,字节数组填充现在是基准测试的一部分,以及准备步骤(见上文).最初MSN的解决方案做得不好,准备int []缓冲区有很多开销.我冒昧地优化了一步,将其变成了一个激烈的竞争对手:)你也可能会发现我对你的代码进行了一些解构.你的getBit()可以压缩成3线,可能会削减一到两个百分点.我故意这样做是为了保持代码的可读性,因为其他版本也没有尽可能浓缩(同样为了可读性).

---

结论(上面的代码示例更新包括基于所有适用的贡献的版本).在我的旧AMD盒子(Sun JRE 1.6.0_21)上,它们出现为:

V0没有实现花了5384 ms
V1 Durandal(原版)花了10283 ms
V2 blitzpasta(改编)花了12212 ms
V3 MSN(已发布)花了11030 ms
V4 MSN(半缓冲修改)花了9700 ms

注意:在此基准测试中,每次调用getBits()时都会获取7.5位的平均值,并且每个位只读取一次.由于V3/V4必须支付较高的初始化成本,因此它们倾向于显示更好的运行时行为,具有更多,更短的提取(并且因此越接近平均提取大小的最大值16).尽管如此,在所有情况下,V4仍然领先于其他所有人.在实际应用中,必须考虑缓存争用,因为V3/v4所需的额外空间可能会将缓存未命中增加到V0将是更好选择的点.如果要遍历数组不止一次,那么V4应该受到青睐,因为它比其他所有数据都要快,并且在第一次通过后,昂贵的初始化将分摊.

Answer 1

好吧，根据您想要将时间与内存拉锯的时间缩短多远，您可以在每个 16 位偏移量处分配一个每 32 位的边表，然后根据 16 位进行掩码和移位抵消：

byte[] bytes = new byte[2048];   
int bitGet;   
unsigned int dwords[] = new unsigned int[2046];

public BitArray() {   
    for (int i=0; i<bytes.length; ++i) {   
        bytes[i] = (byte) i;   
    }   

    for (int i= 0; i<dwords.length; ++i) {
        dwords[i]= 
            (bytes[i    ] << 24) | 
            (bytes[i + 1] << 16) | 
            (bytes[i + 2] <<  8) | 
            (bytes[i + 3]);
    }
}   

int getBits(int len)
{
    int offset= bitGet;
    int offset_index= offset>>4;
    int offset_offset= offset & 15;

    return (dwords[offset_index] >> offset_offset) & ((1 << len) - 1);
}

您可以避免分支（代价是内存占用量增加四倍）。查找掩码真的比 (1 << len) - 1 快得多吗？