1

次の形式の式を最適化する必要があります。

(a > b) || (a > c)

いくつかの最適化されたフォームを試しましたが、そのうちの 1 つは次のとおりです。

(a * 2) > (b + c)

最適化は、コンパイラの観点からではありません。2 つの > を 1 つに減らしたいと思います。

これは、1 <= (a, b, c) <= 26 という仮定に基づいています。

ただし、これは一部のケースでのみ機能します。私が行おうとしている最適化は本当に可能ですか? はいの場合、開始は本当に役に立ちます。

4

3 に答える 3

4

答えはおそらく、それを最適化したくないということです。さらに、これをより効率的に書く方法があるとは思えません。a、b、c が 1 から 26 の間の値であると言う場合、とにかく (サイズを) 最適にしたいのであれば、整数を使用すべきではありません (その精度は必要ありません)。

a > b の場合、式 a > c はとにかく実行されません。したがって、最大 2 つ (および最小 1 つ) の条件付き操作があり、最適化する価値はありません。

于 2013-02-25T15:59:02.663 に答える
2

ほとんどの場合、これが最適化でさえあるとは思えません。

 a > b || a > c

は次のように評価されます:

 compare a b
 jump not greater
 compare a c
 jump not greater

どこ

 a * 2 > b + c

与えます：

 shift a left 1 (in temp1)
 add b to c (in temp2)
 compare temp1 temp2
 jump if not greater

パフォーマンスの場合と同様に、実際のパフォーマンス測定 (できればプロセッサ アーキテクチャの選択) に基づいて決定することをお勧めします。

于 2013-02-25T16:00:31.157 に答える
1

私が思いつくことができる最高のものはこれです

char a, b, c;
std::cin >> a >> b >> c;

if (((b-a) | (c-a)) & 0x80) {
    // a > b || a > c
}

これによりgcc -O2、条件分岐が1つだけ生成されます

40072e:       29 c8                   sub    %ecx,%eax
400730:       29 ca                   sub    %ecx,%edx
400732:       09 d0                   or     %edx,%eax
400734:       a8 80                   test   $0x80,%al
400736:       74 17                   je     40074f <main+0x3f>

これは、入力値の制約を利用します。値が 26 を超えることはできないため、 から減算aするbと負の値になりa > bます。2 の補数7では、その場合にビットが設定されることがわかっていcます。次に、ビットが かどうかを示すように両方をORし、最後に 0x80 を使用してANDでビットを検査し、それで分岐します。7a > b || a > c7

更新:好奇心から、これをコーディングする 4 つの異なる方法を計りました。テスト データを生成するために、単純な線形合同疑似乱数ジェネレーターを使用しました。1億回の繰り返しのループで時間を計りました。簡単にするために、条件が true の場合はカウンターに 5 を追加し、それ以外の場合は何もしないと仮定しました。私は使用中の最適化レベルで使用g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)して時間を計りました。Intel Xeon X5570 @ 2.93GHz-O2

コードは次のとおりです (条件付きバリアントの 1 つを除いてすべてコメントアウトします)。

#include <iostream>
unsigned myrand() {
    static unsigned x = 1;
    return (x = x * 1664525 + 1013904223);
}

int main() {
    size_t count = 0;
    for(size_t i=0; i<100000000; ++i ) {
        int a = 1 + myrand() % 26;
        int b = 1 + myrand() % 26;
        int c = 1 + myrand() % 26;

        count += 5 & (((b-a) | (c-a)) >> 31);       // 0.635 sec
        //if (((b-a) | (c-a)) & 0x80) count += 5;     // 0.660 sec
        //if (a > std::max(b,c)) count += 5;          // 0.677 sec
        //if ( a > b || a > c) count += 5;            // 1.164 sec
    }
    std::cout << count << std::endl;
    return 0;
}

最も速いのは、私の回答の提案に対する変更です。ここでは、符号拡張を使用して、条件が true または false であるかどうかに応じて321sまたは 32のいずれかであるマスクを生成し、それを使用して追加されるものをマスクして、追加するようにします。 5 または 0。このバリエーションには分岐がありません。時刻は各行のコメントにあります。最も遅いのは元の式でした。0s5( a > b || a > c)

于 2013-02-25T16:16:23.277 に答える