2

010101...や0011001100...などの正確に等しい繰り返しバイナリパターンである128ビットのグループをすばやくスキャンするにはどうすればよいですか？

128ビットブロックの数があり、1の数が0の数に等しいパターンに一致するかどうかを確認したいと思います。たとえば、010101....または00110011...または0000111100001111...ですが、001001001ではありません。 ..

問題は、パターンが境界で開始しない可能性があるため、パターン00110011 .. 0110011 ...で始まり、1ビットシフトで終了することです（128ビットは循環していないため、開始は結合されません。終わり）

010101 ...ケースは簡単で、単純に0xAAAA...または0x5555...です。ただし、パターンが長くなると、順列も長くなります。現在、この質問で概説されているような繰り返しシフト値を使用しています。ビットストリーム内のビットパターンをスキャンする最速の方法ですが、このルーチンですべてのCPUの70％を使用しているため、もっと速い方法がいいでしょう。他のポスターには一般的なケースの解決策がありますが、私のパターンの対称的な性質がより最適なものにつながることを願っています。

それが役立つ場合、私は最大63ビット長のパターンにのみ関心があり、2つのパターン（0101 ... 00110011 ... 0000111100001111 ...など）の累乗に最も関心がありますが、5つの1/5のゼロなどのパターンは現在、これらの非累乗2シーケンスは0.1％未満であるため、一般的なケースをより迅速に進めるのに役立つ場合は無視できます。

完璧なソリューションを実現するためのその他の制約は、アセンブラ命令の数が少なく、ランダムなメモリアクセスがないことです（つまり、大きなレインボーテーブルは理想的ではありません）。

編集。より正確なパターンの詳細。

私は主に、各パターンが128ビット内で連続的に繰り返される0011と0000,1111と0000,0000,1111,1111と16zeros/onesと32zeros/ ones（コンマのみ）のパターンに興味があります。繰り返し部分の長さが2、4、8、16、32ビットでないパターンはそれほど面白くなく、無視できます。（例：000111。。。）

スキャンの複雑さは、パターンが01または10トランジションだけでなく、任意の位置から開始する可能性があることです。したがって、たとえば、次のすべては00001111の4ビット繰り返しパターンに一致します...（読みやすさのために4ビットごとにコンマ）（省略記号は同じように繰り返すことを意味します）

0000,1111....または0001,1110...または0011,1100...または0111,1000...または1111,0000...または111,0001...または1100,0011...または1000,0111

128ビット内では、同じパターンを繰り返す必要があります。2つの異なるパターンが存在することは重要ではありません。たとえば、これは有効なパターンではありません。0000,1111,0011,0011...4ビットの繰り返しから2ビットの繰り返しに変更したため。

1の数が64であることをすでに確認しました。これは、すべての2乗パターンに当てはまります。次に、繰り返しパターン（2、4、8、16、32）を構成するビット数と、パターンの量を特定する必要があります。シフトしました。たとえば、パターン0000,1111は4ビットパターンで、0シフトされます。0111,1000...は4ビットパターンで3シフトされます。

4

4 に答える 4

2

パターンが境界で始まる場合から始めましょう。最初のビットを確認し、それを使用して状態を判断できます。次に、ブロックのループを開始し、最初のビットをチェックし、カウントをインクリメントし、左シフトして、反対のビットを取得するまで繰り返します。この初期長をビットセット長として使用できるようになりました。カウントを 1 にリセットしてから、反対のビットの次のセットをカウントします。切り替えるときは、長さを最初の長さと比較してチェックし、等しくない場合はエラーを出します。簡単な関数を次に示します。これは char に対して期待どおりに機能するようで、32 バイトのブロックを処理するために拡張するのはそれほど難しくありません。

unsigned char myblock = 0x33;
unsigned char mask = 0x80, prod = 0x00;
int setlen = 0, count = 0, ones=0;

prod = myblock & mask;
if(prod == 0x80)
  ones = 1;

for(int i=0;i<8;i++){
  prod = myblock & mask;
  myblock = myblock << 1;
  if((prod == 0x80 && ones) || (prod == 0x00 && !ones)){
    count++;
  }else{
    if(setlen == 0) setlen = count;
    if(count != setlen){
      printf("Bad block\n");
      return -1;
    }
    count = 1;
    ones = ( ones == 1 ) ? 0 : 1;
  }
}

printf("Good block of with % repeating bits\n",setlen);
return setlen;

オフセットがあるブロックを処理するために、最初の「反転」までのビット数をカウントすることをお勧めします。この数を保存し、残りのセットとは異なる長さを持つ最後のセグメントに到達するまで、上記のルーチンを実行します。最初のビットを最後のセグメントの長さに追加すると、それを残りのセットのサイズと正しく比較できるはずです。

このコードは非常に小さく、バッファを介したビット シフトは、CPU 側であまり多くの作業を必要としません。このソリューションが現在のソリューションに対してどのように機能するかを知りたいです。

于 2013-03-22T02:06:05.320 に答える
1

この種の問題の一般的な解決策は、パターンに適したハッシュ関数を作成し、各パターンをハッシュマップに格納することです。パターン用にハッシュマップを作成したら、入力ストリームを使用してテーブルを検索してみてください。私はまだコードを持っていませんが、あなたがコードに打たれたら私に知らせてください。それを投稿してください、そして私はそれに取り組むことができます。

于 2013-03-22T02:38:14.017 に答える
1

128ストリーム全体でパターンが繰り返されるという制限により、組み合わせの数が制限され、シーケンスには次のようなプロパティが含まれるため、簡単に確認できます。

高い部分と低い部分が同じであるかどうかを繰り返しチェックする必要があります。それらが反対である場合は、その特定の長さに連続したものが含まれているかどうかを確認してください。

 8-bit repeat at offset 3:  00011111 11100000 00011111 11100000
 ==> high and low 16 bits are the same
 00011111 11100000 ==> high and low parts are inverted.
 Not same, nor inverted means rejection of pattern.

その時点で、1のシーケンスがあるかどうかを確認する必要があります。左側に「1」を追加し、2の累乗かどうかを確認します。n==（n＆-n）はそのための教科書チェックです。

于 2013-03-22T05:28:42.837 に答える
1

ステート マシンを作成することを考えたので、次のバイト (16 のうち) ごとにその状態が進み、16 回の状態遷移の後、パターンが識別されます。しかし、それはあまり有望ではないようです。データ構造とロジックはより複雑に見えます。

代わりに、これら 126 のパターン (01 から 32 個のゼロ + 32 個の 1) をすべて事前計算し、それらを並べ替えて、二分探索を実行してみませんか? これにより、バイナリ検索の最大 7 回の反復が得られます。また、すべてのパターンの 16 バイトすべてを格納する必要はありません。半分は同じだからです。これにより、パターンの配列に 126*16/2=1008 バイトが与えられます。また、ゼロ (1) ランの長さと、シフトされていないと見なすパターンに関連するシフトを格納するために、パターンごとに 2 バイトのようなものが必要です。これは、合計 126*(16/2+2)=1260 バイトのデータ (データ キャッシュに優しいはずです) であり、非常に単純で小さなバイナリ検索アルゴリズムです。基本的に、質問で言及した回答に対する単なる改善です。

二分探索を 4 ～ 5 回繰り返した後、線形探索に切り替えてみることをお勧めします。これにより、アルゴリズム全体がわずかに向上する可能性があります。

最終的に、勝者はテスト/プロファイリングによって決定されます。そして、それがあなたがすべきことです。いくつかの実装を取得し、実際のシステムの実際のデータと比較してください。

于 2013-03-22T05:58:12.783 に答える