14

任意の位置で任意の長さ（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メソッドの各呼び出しの間に1回だけ（完全に）読み取られます。配列を超えるなど、getBits（）でエラーチェックを行う必要はありません。

上記の私の最初の質問は十分に明確ではないようです。Nビットの「ビットシーケンス」はNビットの整数を形成し、最小限のオーバーヘッドでそれらの整数を抽出する必要があります。値はルックアップインデックスとして使用されるか、何らかの計算に直接入力されるため、文字列は使用しません。したがって、基本的に、上記のスケルトンは実際のクラスであり、getBits（）シグネチャは、コードの残りの部分がどのように相互作用するかを示します。

サンプルコードをマイクロベンチマークに拡張し、blitzpastaのソリューションを含めました（欠落しているバイトマスキングを修正しました）。私の古いAMDボックスでは、〜11400ms対〜38000msであることがわかりました。参考：パフォーマンスを損なうのは除算とモジュロ演算です。/ 8を>>3に、％8を＆7に置き換えると、両方のソリューションは互いにかなり近くなります（jdk1.7.0ea104）。

どのように、何に取り組むべきかについて少し混乱があったようです。サンプルコードの最初の元の投稿には、バイトバッファがいつどこでいっぱいになったのかを示すread（）メソッドが含まれていました。これは、コードがマイクロベンチに変換されたときに失われました。これをもう少し明確にするために、再導入しました。アイデアは、getBits（）とprepareBitGet（）を実装する必要があるBitArrayの別のサブクラスを追加することによって、既存のすべてのバージョンを打ち負かすことです。後者は空の場合があります。ソリューションに利点を与えるためにベンチマークを変更しないでください。既存のすべてのソリューションに対して同じことができるため、これは完全に無意味な最適化になります。（本当！！）

私はVersion0を追加しました。これは、bitGet状態をインクリメントするだけです。ベンチマークのオーバーヘッドがどれほど大きいかを大まかに把握するために、常に0を返します。比較のためだけにあります。

また、MSNのアイデアへの適応が追加されました（バージョン3）。すべての競合他社にとって公平で比較可能なものを維持するために、バイト配列の入力がベンチマークの一部であり、準備ステップでもあります（上記を参照）。もともとMSNのソリューションはあまりうまく機能しなかったため、int[]バッファの準備に多くのオーバーヘッドがありました。私はそのステップを少し自由に最適化したので、それは激しい競争相手になりました:)また、私があなたのコードを少しデコンボリューションしたことに気付くかもしれません。getBit（）を3ライナーに凝縮し​​て、おそらく1〜2パーセント削減することができます。コードを読みやすくするために、また他のバージョンも可能な限り凝縮されていないため、意図的にこれを行いました（これも読みやすさのためです）。

結論（上記のコード例は、該当するすべての貢献に基づくバージョンを含むように更新されています）。私の古いAMDボックス（Sun JRE 1.6.0_21）では、次のように表示されます。

V0実装なし5384ミリ秒
V1デュランダル（元）は10283ミリ秒かかりました
V2ブリッツパスタ（適応）は12212ミリ秒かかりました V3 MSN（投稿）は11030ミリ秒かかりました V4 MSN（ハーフバッファー変更）は9700ミリ秒かかりました

注：このベンチマークでは、getBits（）の呼び出しごとに平均7.5ビットがフェッチされ、各ビットは1回だけ読み取られます。V3 / V4は高い初期化コストを支払う必要があるため、フェッチが多く、フェッチが短いほど、実行時の動作が向上する傾向があります（その結果、平均フェッチサイズが最大16に近づくほど悪化します）。それでも、V4は、すべてのシナリオで他のすべてよりもわずかに進んでいます。実際のアプリケーションでは、キャッシュの競合を考慮に入れる必要があります。これは、V3 / v4に必要な余分なスペースにより、キャッシュミスが増加し、V0がより適切なポイントになる可能性があるためです。アレイを複数回トラバースする場合は、V4を優先する必要があります。これは、アレイが他のすべてよりも高速にフェッチし、最初のパス後にコストのかかる初期化が償却されるためです。

4

5 に答える 5

4

符号なしビットシーケンスをintとして使用したい場合。

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

/*
 * bytes: byte array, with the bits indexed from 0 (MSB) to (bytes.length * 8 - 1) (LSB)
 * offset: index of the MSB of the bit sequence.
 * len: length of bit sequence, must from range [0,16].
 * Not checked for overflow
 */
static int getBitSeqAsInt(byte[] bytes, int offset, int len){

    int byteIndex = offset / 8;
    int bitIndex = offset % 8;
    int val;

    if ((bitIndex + len) > 16) {
        val = ((bytes[byteIndex] << 16 | bytes[byteIndex + 1] << 8 | bytes[byteIndex + 2]) >> (24 - bitIndex - len)) & lookup[len];
    } else if ((offset + len) > 8) {
        val = ((bytes[byteIndex] << 8 | bytes[byteIndex + 1]) >> (16 - bitIndex - len)) & lookup[len];
    } else {
        val = (bytes[byteIndex] >> (8 - offset - len)) & lookup[len];
    }

    return val;
}

文字列として必要な場合（Margusの回答の変更）。

static String getBitSequence(byte[] bytes, int offset, int len){

    int byteIndex = offset / 8;
    int bitIndex = offset % 8;
    int count = 0;
    StringBuilder result = new StringBuilder();        

    outer:
    for(int i = byteIndex; i < bytes.length; ++i) {
        for(int j = (1 << (7 - bitIndex)); j > 0; j >>= 1) {
            if(count == len) {
                break outer;
            }                
            if((bytes[byteIndex] & j) == 0) {
                result.append('0');
            } else {
                result.append('1');
            }
            ++count;
        }
        bitIndex = 0;
    }
    return  result.toString();
}
于 2010-10-02T21:03:59.550 に答える
2

さて、時間とメモリのシーソーをどれだけ下げたいかに応じて、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);
}

分岐を回避します（メモリフットプリントを4倍にするという犠牲を払って）。そして、マスクの検索は（1 << len）-1よりもはるかに高速ですか？

于 2010-10-07T23:55:26.897 に答える
1

なんで使えないのかしらjava.util.BitSet;

基本的にあなたができることは、データ全体をとして読み取り、byte[]それをフォーマットのバイナリに変換し、仕事をするのとstring同じように文字列ユーティリティを使用することです。.substring()これも機能しbit sequences > 16ます。

3バイト1, 2, 3あり、5番目から16番目のビットのビットシーケンスを抽出するとします。

2進数

1      00000001
2      00000010
3      00000011

コード例：

public static String getRealBinary(byte[] input){
    StringBuilder sb = new StringBuilder();

    for (byte c : input) {
        for (int n =  128; n > 0; n >>= 1){
            if ((c & n) == 0)
                sb.append('0');
            else sb.append('1');
        }
    }

    return sb.toString();
}
public static void main(String[] args) {
    byte bytes[] = new byte[]{1,2,3};
    String sbytes = getRealBinary(bytes);
    System.out.println(sbytes);
    System.out.println(sbytes.substring(5,16));
}

出力：

000000010000001000000011
00100000010

スピード：

私は1m回テストランを行いましたが、私のコンピューターでは0.995秒かかったので、かなり高速です。

自分でテストを繰り返すコード：

public static void main(String[] args) {
    Random r = new Random();
    byte bytes[] = new byte[4];
    long start, time, total=0;

    for (int i = 0; i < 1000000; i++) {
        r.nextBytes(bytes);
        start = System.currentTimeMillis();
        getRealBinary(bytes).substring(5,16);
        time = System.currentTimeMillis() - start;
        total+=time;
    }
    System.out.println("It took " +total + "ms");
}
于 2010-10-02T17:17:37.883 に答える
0

バイトの配列から取得した最大16ビットが必要です。16ビットは最大3バイトにまたがることができます。考えられる解決策は次のとおりです。

    int GetBits(int bit_index, int bit_length) {
          int byte_offset = bit_index >> 3;
          return ((((((byte_array[byte_offset]<<8)
                    +byte_array[byte_offset+1])<<8)
                    +byte_array[byte_offset+2]))
                   >>(24-(bit_index&7)+bit_length))))
                  &((1<<bit_length)-1);
         }

[未テスト]

これを頻繁に呼び出す場合は、連結された3バイトの24ビット値を事前に計算し、それらをint配列に格納する必要があります。

これをx86のCでコーディングしている場合は、24ビット配列を事前に計算する必要さえありません。32ビット値として必要なオフセットでbyte配列にアクセスするだけです。x86は、整列されていないフェッチを問題なく実行します。[コメンターは、エンディアンがこれを台無しにしているので、答えではないことを指摘しました。OK、24ビットバージョンを実行してください。]

于 2010-10-09T21:00:57.463 に答える
0

Java 7BitSetにはtoLongArrayメソッドがあるので、質問が求めることを正確に実行できると私は信じています。

int subBits = (int) bitSet.get(lowBit, highBit).toLongArray()[0];

これには、intまたはlongよりも大きいシーケンスで機能するという利点があります。BitSet新しいオブジェクトを割り当てる必要があり、結果を保持するために新しい配列オブジェクトを割り当てる必要があるというパフォーマンス上の欠点があります。

これがベンチマークの他の方法とどのように比較されるかを見るのは本当に興味深いでしょう。

于 2018-02-01T09:22:19.447 に答える