1

コードブックには 8 ビットの値がたくさんあります (約 200 個)。

私のプログラムは、入力に応じて 8 ビット値を生成するので、同じビットが設定されているコードブック内の一致をすべて (または最初の値でさえも) 見つける必要があります。設定されていないビットは重要ではありません。

a) コードブックを保存し、b) コードブックを検索してすべての一致を見つけるための最適な方法を考えられますか? 私は標準的な線形検索を行っていますが、もちろんそれはかなり非効率的です。

どうもありがとう...

アケヴァン

4

5 に答える 5

2

もちろん、スペース効率はあまり良くありませんが、もちろん、256 ビット パターンすべての一致を事前に計算できます。256 個のリストの配列があり、各リストにはコードブック内の各コードが含まれており、それらのビットが設定されています。

256 バイト (11 ワードのメモリ) で最初の一致を取得できます。

初期化:

u_int8_t bitpatterns[256];
memset(bitpatterns,0,sizeof(bitpatterns));

for(x=sizeof(codebook)-1;x>=0;x--)
  for(y=0;y<256;y++)
    if (y&codebook[x] == y)
      bitpatterns[y] = x;

調べる：

codeword = codebook[bitpatterns[input]];
于 2011-06-29T17:24:58.143 に答える
1

8 ビット ルックアップのみを実行している場合、すべての回答を事前に計算してから、それらを 256 エントリ テーブルに格納するのは簡単です。そうすれば、一定時間のクエリを取得でき、メモリ ストレージは 256 エントリ程度になります。

于 2011-06-29T17:24:16.477 に答える
1

最適化の 1 つは、設定されているビット数に応じてコードを異なるバケットに格納することです。コードを検索するときは、コードの 1/2 を調べるだけで済みます (平均して、コードが均一に分散されている場合)。これは非常に単純な最適化ですが、アルゴリズムの複雑さは変わりません (O(n))。セットされたビット数に基づいて 1 つの配列を並べ替えると、コードをバケットに格納することなく、同様の最適化を行うことができます。

補足: 200 は非常に小さい数だと思います。多くのルックアップを行わない限り、これをどのように最適化しても、線形アプローチからのパフォーマンスの大きな変化は見られないと思います。しかし、それはこの演習のポイントではないと思います...

于 2011-06-29T17:06:59.240 に答える
0

新しい（そしてより良い提案）を得たので、別の回答を投稿しています：

  1. コードブックを値で並べ替える
  2. 検索しているコードごとに、最初にバイナリ下限境界検索を実行して、最初に一致する可能性のあるものを見つけます (検索している値より小さい値は一致できません)。
  3. 最初の可能な一致から最後の要素までの範囲を検索して、一致するものがあるかどうかを確認します。

アルゴリズムは依然として線形ですが、(できれば) ほとんどの値をカットオフするために O(log N) ルックアップを使用します。小さな値のルックアップはまだ高価ですが、大きな値のルックアップは安くなります。

また、ブルームフィルターを使用して最初の検索を行ってほとんどのケースをカットオフし、残りを線形検索することもできます。フィルターには誤検知がある可能性があるため、フィルターが true を返す場合は線形検索を行う必要があります。このデータ構造では、大量の独立したハッシュ関数が必要です(たとえば、設定されたビット数、設定されたすべてのビットの積、奇数と偶数、数値自体などに基づく)。コードがたまにしか見つからないことが予想される場合、これは適切な最適化になる可能性があります (フィルターが false を返す場合、コードはコードブックにないことが保証されます)。ただし、これは実際の最適化よりも理論的な関心事であると思います。

于 2011-06-29T18:35:59.193 に答える
0

私が理解している場合、応答にビット1、3、5のみが設定されている場合、フラグ1、3、5が設定されているコードブック内のすべてのコードが必要であり、ビット2、4、6は気にしないと言っています,7,8.

もしそうなら、ここにあなたの疑似コードがあります：

matchingCodes = new List<Code>
foreach(code in codebook)
    if((response & code) == response) matchingCodes.add(code);
于 2011-06-23T17:32:56.740 に答える