1

私は次の定義を持っています：

typedef enum
{
    def   = 0,
    m1    = 1,
    m2    = 2,
    m3    = 4,
    m4    = 6,
    m5    = 17,
    m6    = 33,
    m7    = 41,
    m8    = 47,
    m9    = 50,
    m10   = 51,
    m11   = 58,
    m12   = 89,
    m13   = 132,
    m14   = 135
} my_enums;

そして、関数への引数がこれらの値 m1..m14 のいずれかに該当するかどうかを確認する最速の方法を探しています。明らかな実装は、if (p == m1 || p == m2 ...) またはスイッチケースの代替です。

もっと速いものはありますか？m1~m14 の値は固定されており、連続した範囲にあることはできません。

ありがとう。

4

7 に答える 7

7

switch ステートメントの方が適しています。(ほとんどの場合) switch ステートメントを非常に最適化するためにコンパイラが使用できるトリックを知っておくと役立ちます。多くの場合、自分で思いつくよりも優れています。

値が連続していない場合、コンパイラは O(log(n)) パフォーマンスの静的二分決定木に頼ることができます。連続値リストの場合、O(1) のジャンプ テーブルが作成されます。比較すると、if-else コンストラクトは O(n) です。

他の方法に頼る前に、switch ステートメントから何が得られるかを完全に理解することをお勧めします。

于 2013-09-05T18:57:43.933 に答える
6

オフハンドで考えることができる最も速いのは、0 から 135 までのバイトの配列です。アイテムが有効な列挙型の 1 つである場合は値を 1 に設定し、そうでない場合は 0 に設定します。次に、次のように記述できます。

if (valuesArray[x])
    YahooItsGood();

もちろん、あなたの範囲が巨大な場合、それはうまくいきません。

渡された値がその範囲外になる可能性がある場合は、もう少しロジックが必要になります。

if (x >= 0 && x < 136 && valuesArray[x])
    YahooItsGood();

もちろん、実際には項目ごとに 1 ビットしか必要ないため、サイズが 1/8 の配列を使用することで多くのメモリを節約できます。値をテストするロジックは少し複雑になりますが、それでも一連の if/else や二分探索よりは高速です。

はるかに大きなセットがある場合は、おそらくハッシュ テーブルを作成する必要があります。直接参照ほど高速ではありませんが、値の範囲がはるかに大きい場合は、使用するメモリが大幅に少なくなります。

于 2013-09-05T18:26:38.437 に答える
1

入力が 8 ビット幅になることを保証できる場合の簡単なアイデア: サイズ 256 の静的 int 配列を作成し、列挙型で指定されたインデックスに 1 を指定し、それ以外の場所に 0 を指定します。あとは、配列を 1 回検索するだけです。

于 2013-09-05T18:27:11.657 に答える
1

My 2-cents - MSB のビットごとの操作を使用して分割して征服します。ここでは 32 が中央値に近いため、テーブルを半分に分割することから始めます。

    if (p & 32)

次のレベルでは、偽のケースを (p & 4) と比較し、真のケースを (p & 64) と比較します。これにより、各ブランチに正確に 3 つのオプションが残ります (論理 OR でカバーできます)。 32 と 64、(p & 48) を使用してさらに分解できます (これは 2 の累乗ではないため、一部のケースでのみ機能します。MSB が等しい場合にのみ機能すると思います)

ここでの利点は、バイナリ検索を実行したことです (数値が連続している最悪の場合でも、領域全体でバイナリ検索に陥り、それでもログ (MAX_N) になります)、安価なを使用してそうしていますコンパイラが述語できる可能性のあるビット単位の操作 (または、先に進んで自分で行うことができます)

于 2013-09-05T20:11:59.703 に答える
1

値が順番になっているので、二分探索を好むでしょう。

1 つは配列を定義します。 

  my_enums enumv[17] = {def, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12, m13, m14, -1, -1};

(最後の 2 つの値はセンチネルで、結果には影響しません)。

次に、バイナリ検索を実行します。 

  int s = 0;
  for (int i = 8; i; i /= 2)
        if (p >= enumv[s+i])
           s += i;
  if ( p >= 0 && p == enumv[s])
     printf("Happy\n");
  else
     printf("Unhappy\n");

すべての「for」を必要とせず、値が 15 個しかないため、このアルゴリズムを展開して「手元に」書き込むと、高速化できます。 

  int s = 0;
  s += 8*(p >= enumv[s+8]); 
  s += 4*(p >= enumv[s+4]);
  s += 2*(p >= enumv[s+2]);
  s +=   (p >= enumv[s+1]);

  if (p >= 0 && p == enumv[s])
     printf("Happy\n");
  else
     printf("Unhappy\n");
于 2013-09-05T20:09:08.913 に答える
0

最速のものを求めているので、ビット操作はバイトよりも高速である必要があります。

17 オクテットを持つことができます。各ビットについて、そのビットが必要なものであれば 1 としてマークし、それ以外の場合は 0 としてマークします。ルックアップごとに、チェックしたいオクテット ID とビットを計算し、それをチェックすると結果が得られます。

于 2013-09-05T18:53:54.143 に答える
0 
if(p/7==0 && (p%6!=3 ||p%6!=5))
 // p is present, p = 0,1,2,4,6
if(p==17||p==33.....remaining 7 numbers)
//p is present

それで、条件評価を 14 から 12 に減らしました...おそらく、上記で行ったように、値間の関係を見つけてみてください。

于 2013-09-05T18:51:03.090 に答える