java – 从byte []数组中提取任意长度的位序列
我正在寻找在任意位置提取任意长度(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字节.在读取方法的每次调用之间,数组读取完全一次(完全).没有必要在getBits()中进行任何错误检查,例如超出数组等. 看来我上面的初步问题还不够清楚. N位的“位序列”形成N位的整数,我需要以最小的开销提取这些整数.我没有使用字符串,因为值被用作查找索引或直接馈入一些计算.所以基本上,上面显示的框架是一个真正的类,getBits()签名显示了其余代码如何与它进行交互. 将示例代码扩展到微基准,包括blitzpasta的解决方案(固定的丢失字节屏蔽).在我的旧的AMD盒子里,结果是?11400ms vs?38000ms. FYI:它的划分和模拟操作,杀死了性能.如果用>> 3和%8替换为&8,& 7,这两个解决方案彼此非常接近(jdk1.7.0ea104). 似乎有关于如何和什么工作有点混乱.示例代码的第一个原始帖子包括一个read()方法来指示字节缓冲区的填充位置和时间.当代码变成微架时,这丢失了.我重新介绍了它,使之更清楚一点. 我添加了一个版本0,它只会增加bitGet状态.总是返回0,以了解基准开销有多大.它只在那里进行比较. 此外,添加了对MSN的想法的适应(Version3).为了保持所有竞争对手的公平和可比性,字节数组填充现在是基准的一部分,以及准备步骤(见上文).最初MSN的解决方案并没有那么好,在准备int []缓冲区时有很多开销.我自由地优化了一步,这变成了一个激烈的竞争对手:) 结论(上面的代码示例更新包括基于所有适用的贡献的版本).在我老的AMD盒子(Sun JRE 1.6.0_21)上,他们出来了: V0没有实现了5384毫秒 注意:在这个基准测试中,平均每个调用getBits()获取7.5位,每个位只读一次.由于V3 / V4必须支付较高的初始化成本,所以它们倾向于以较短的获取时间来显示更好的运行时行为(因此更接近平均获取大小的最大值为16).尽管如此,V4在所有情况下仍然保持领先于所有其他方案. 解决方法
那么,根据你想要下降时间与内存跷跷板的距离,你可以在每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更快地查找面具? (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |