2

バイナリ データのメモリ ブロックをバイト単位で実行しています。

現在、私は次のようなことをしています：

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

マスクの場所:

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

(ループやインライン関数でどうにかして高速に実行できなかったので、書き出しました。)

この最初のループを改善する方法について何か提案はありますか? 私はビットに到達することにかなり慣れていません。

これは愚かなことのように思えるかもしれません。しかし、私は圧縮アルゴリズムを実装中です。ビットアクセス部分を右下にしたいだけです。

ありがとう！

PS: これは Visual Studio 2008 コンパイラに含まれています。したがって、提案がそのコンパイラに適用されるとよいでしょう。

PPS: 2 つのカウントをインクリメントする必要がないことに気付きました。1つで十分です。次に、最後に合計ビット数との差を計算します。しかし、それはカウントするだけに固有のものです。私が本当に早くしたいのは、ビット抽出です。

編集: 持ち出されたルックアップ テーブルのアイデアは素晴らしいです。タイトルで間違った質問をしたことに気づきました。最終的に私がやりたいことは、ビットを数えるのではなく、各ビットにできるだけ速くアクセスすることだからです。

別の編集: データ内でポインタを 1 ビットだけ進めることは可能ですか?

別の編集: これまでのすべての回答に感謝します。

次のステップで実装したいのは、コンテキストを分析しない単純なバイナリ算術コーダーです。だから私は今のところ単一のビットにしか興味がありません。最終的には Context-adaptive BAC になりますが、それについては後で説明します。

1 バイトではなく 4 バイトを処理することもできます。しかし、32 ビットのループもコストがかかりますね。

4

11 に答える 11

16

おそらく最速の方法は、バイト値とそのバイトに設定されたビット数のルックアップ テーブルを作成することです。少なくとも、私が Google でインタビューしたときの答えはそれでした。

于 2009-01-06T21:38:34.763 に答える
5

各バイト値 (256) をその中の 1 の数にマップするテーブルを使用します。(0 の数は (8 - 1 の数) です)。次に、バイトを繰り返し処理し、複数のルックアップと比較ではなく、バイトごとに 1 回のルックアップを実行します。例えば：

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;
于 2009-01-06T21:42:13.713 に答える
2

事前に計算されたルックアップ テーブルを使用できます。つまり、次のようになります。

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];
于 2009-01-06T21:41:03.917 に答える
2

あなたが何をしようとしているのか、私にはよくわかりませんでした。ただし、ビットマップのビットにアクセスしたいだけの場合は、次の (テストされていない!!!) 関数を使用できます。

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

編集:わかりました、私はあなたが何をしたいのか理解していると思います:一連のビットに対する高速反復。したがって、上記のランダムアクセス関数を使用したくはありませんが、データのワード全体を一度に読み取ります。

任意の符号なし整数型を使用できますが、アーキテクチャのワード サイズに対応する可能性が高いものを選択する必要があります。私はuint_fast32_tから行きますstdint.h：

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

内側のループから、ビットを設定できます

*data |= mask;

でビットをアンセットします

*data &= ~mask;

でビットを切り替えます

*data ^= mask;

警告:ビッグ エンディアン アーキテクチャでは、コードが予期しない動作をする可能性があります。

于 2009-01-06T23:00:08.733 に答える
1

これは、単一の 32 ビット値のみを使用して作成した単純なものですが、任意の数のビットに適応させるのは難しくないことがわかります....

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

ただし、その過程で値が変更されることに注意してください。保持する必要があるデータに対してこれを行う場合は、最初にそのコピーを作成する必要があります。

__asm でこれを行うと、おそらくより良い、おそらくより高速な方法になりますが、コンパイラがどれだけ最適化できるかを言うのは難しいです...

検討する各ソリューションには、それぞれに欠点があります。ルックアップ テーブルまたはビット シフター (私のようなもの) には、どちらにも欠点があります。

ラリー

于 2009-01-06T22:04:14.447 に答える
1

Integer.bitCount(i)以下は、32 ビット整数の 1 ビットをカウントする方法です (Java の方法に基づく)。

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

したがって、データを int にキャストして、4 バイト単位で進めることができます。

于 2009-01-06T21:49:58.720 に答える
1

ttobiass - あなたが話しているようなアプリケーションではインライン関数が重要であることに注意してください。しかし、心に留めておく必要があることがあります。インライン コードからパフォーマンスを引き出すことができます。いくつかのことを覚えておいてください。

  • デバッグ モードの inline は存在しません。(無理やりしなければ)
  • コンパイラは、適切と思われる関数をインライン化します。多くの場合、関数をインライン化するように指示しても、まったく実行されないことがあります。__forceinline を使用しても。インライン化の詳細については、MSDN を確認してください。
  • インライン化できるのは特定の関数だけです。たとえば、再帰関数をインライン化することはできません。

C/C++ 言語のプロジェクト設定と、コードの作成方法から最高のパフォーマンスを引き出すことができます。この時点で、ヒープとスタックの操作、呼び出し規則、メモリ アライメントなどを理解することが重要です。

これがあなたの質問に正確に答えていないことはわかっていますが、パフォーマンスと、最高のパフォーマンスを得る方法について言及しており、これらが重要です。

于 2009-01-06T22:27:11.063 に答える
0

「 BeautifulCode」という本には、このためのさまざまなテクニックに関する章全体があります。ここから始まるGoogleブックスで（ほとんど）読むことができます。

于 2009-01-06T21:54:41.893 に答える
0

ビットを抽出するより高速な方法は、次を使用することです。

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

ビット セットをカウントするだけの場合は、キャッシュごとに LUT を使用すると高速ですが、この回答のリンクにあるインターリーブ ビット カウント方法を使用して一定時間でカウントすることもできます。

于 2009-02-27T21:32:46.520 に答える
0

リンクワゴンに参加するには： ビットを数えます

于 2009-01-06T21:43:17.907 に答える
0

これが時期尚早の最適化のケースではなく、本当に最後のフェムト秒ごとに絞り出す必要がある場合は、各バイト値のビット数を一度入力する 256 要素の静的配列を使用する方がよいでしょう。

Stats.FreqOf1 += bitCountTable[バイト]

ループが完了すると、次のようになります。

Stats.FreqOf0 = ((data->Count * 8) - Stats.FreqOf1)

于 2009-01-06T21:47:09.117 に答える