1

アップデート：

この議論は予想以上に進んだので、この質問が頭に浮かんだときに実際に取り組んでいたコードでこれを更新しています。C++ 入門コースの三目並べゲームの勝者を決定するのは、8 行から 16 行のコードの決定でした。

注:これは、コースと同じレベルになるように設計されています。

注 2:トークンは、x または o または ' ' のいずれかの文字です)

これは最適化の問題です。これが繰り返しの場合は申し訳ありませんが、他の場所で答えを見つけることができませんでした.

基本的には、次のコードをループしたほうがよいかどうかにかかっていました。

    char CheckForWinner() {

    //returns the token of the player that satisfies one of the winning requirements
    if (Square[0][0] == Square[0][1] && Square[0][0] == Square[0][2] ) { //If all three tokens in the first row are the same
        return Square[0][0]; //Return the token
    } else if (Square[1][0] == Square[1][1] && Square[1][0] == Square[1][2] ) { //Check the next row
        return Square[1][0]; //Return the token
    } else if (Square[2][0] == Square[2][1] && Square[2][0] == Square[2][2] ) {
        return Square[2][0];
    } else if (Square[0][0] == Square[1][0] && Square[0][0] == Square[2][0] ) { //If no rows satisfy conditions, check columns
        return Square[0][0]; //Return the token
    } else if (Square[0][1] == Square[1][1] && Square[0][1] == Square[2][1] ) { 
        return Square[0][1];
    } else if (Square[0][2] == Square[1][2] && Square[0][2] == Square[2][2] ) { 
        return Square[0][2];
    } else if (Square[0][0] == Square[1][1] && Square[0][0] == Square[2][2] ) { //finally, check diagonals
        return Square[0][0];
    } else if (Square[0][2] == Square[1][1] && Square[0][2] == Square[2][0] ) {
        return Square[0][2];
    }

    return ' ';
}

これは、単に 100 行の cout を入力するだけで、システムに多かれ少なかれ負担がかかりますか?

100 の cout 行を実行するだけでなく、新しい変数をメモリに割り当て、コンピュータに 100 の数式を処理させてデータを出力させるように見えるので、興味深いです。

コンパイラがある程度の最適化を提供する可能性があることは理解できますが、より一般的なレベルで知りたいと思います。主に、VisualStudio 2012 または MingGW (g++) を使用してコンパイルします。

4

4 に答える 4

5

ループの 100 回の反復すべてを展開することが効果的かどうかについて、単一の答えはありません。

コード キャッシュのない「小規模な」システムの場合、少なくとも実行速度に関しては、100 回の反復すべてを展開することが最適である可能性がかなり高くなります。一方、CPU がキャッシュを持たないほど小さいシステムは、通常、他のリソースが十分に制約されているため、そうするのは非常にお勧めできません。

システムにキャッシュがある場合、ループの 100 回の反復すべてを展開すると実行速度が低下する可能性が非常に高くなります。ループ自体のオーバーヘッドは、ほぼ確実に、本質的に同一のコードを 100 回以上再フェッチするよりも短い時間で済みます。

通常、ループの展開は、ループの反復が数回展開される場合に最も効果的です (ただし、通常は反復が 100 回未満)。典型的なケースでは、展開される 4 ～ 16 回の反復のあたりで広いプラトーが見られます。

しかし、最適化に最初に挑戦する多くの人によくあることですが、あなたは本当に完全に間違った方向を見ていると思います。そのループを最適化したい場合、ループ内で行うことをわずかに変更することで (はるかに) 最大の利益が得られる可能性があります。ループをアンロールすることで得られる改善は小さすぎて確実に測定できないことは間違いありませんが、実際に気付くことは言うまでもありません (反復回数を 100 回から数百万回に増やしたとしても)。

一方、繰り返しごとに不要なバッファ フラッシュを削除するようにループを書き直すと、次のようになります。

for ( int i = 1; i <= 100; i++ ) 
    cout << i << "\n";

[ご存じない場合:std::endlストリームに改行を挿入し、ストリームをフラッシュします。ほとんどの場合（おそらくこれを含む）、バッファフラッシュは不要であり、おそらくお勧めできません。これを削除すると、速度が大幅に向上します。8 :1 または 10:1 の係数による改善はかなり一般的です。]

速度の違いを測定するのにそれほど時間はかからない可能性があります。100回の反復で測定できる可能性はかなり高く、さらに反復を試みると、違いがほとんど痛々しいほど明白になる可能性があります。

I/O バウンドではなく、このような大幅な改善が見込めないループを扱っている場合、ループ展開はより魅力的なオプションになる可能性があります。この場合、最初に、ほとんどのコンパイラが自動的にループ展開を行うことができることに注意する必要があります。そのため、ソース コードでそれを実行しようとしても、他の最適化の機会が開かれない限り(たとえば、ループがある場合) 、あまり役に立ちません。これは実際には偶数の反復で 1 つのことを実行し、奇数の反復で別のことを実行します。これら 2 つの反復をアンロールすると、条件とジャンプなどを完全に排除できます。そのため、手動で実行すると意味のある改善が得られる可能性があります。コンパイラは奇数/条件、ジャンプなどを均一にパターン化して排除します。

また、最新の CPU はコードを並列で実行でき (通常は実行する)、コードを投機的に実行できることにも注意してください。これにより、ループのオーバーヘッドのほとんどを排除できます。ループの分岐はほぼ常に実行されるため (つまり、最後の反復を除くすべての反復で)、CPU の分岐予測子は分岐が実行されると予測します。ループを展開しないでください。ループ自体のコード (たとえば、 incrementing i) のほとんどは、少なくともループ内の他のコードと並行して実行できるため、ループのオーバーヘッドはとにかく最小限に抑えられます。

編集 2: 目前の特定の質問を見ると、私はかなり違うやり方で仕事をすると思います。TTT ボードを 2D 配列として保存する代わりに、1 つは X 用、もう 1 つは O 用の 1 組のビットマップとして保存します。これにより、3 つの個別の比較ではなく、1 回のアクションですべての勝利の組み合わせをテストできます。各行は 3 ビットであるため、定数には 8 進数を使用するのがおそらく最も簡単です。

static const std::array<short, 8> winners = {
    /* rows */      0007, 0070, 0700, 
    /* columns */   0111, 0222, 0444, 
    /* diagonals */ 0124, 0421
};

この場合、ほぼ確実にループを使用します。

char CheckForWinner(short X, short O) { 
    // `winners` definition from above goes here.

    for (int i=0; i<winners.size(); i++) {
        if (X & winners[i] == winners[i])
            return 'X';
        if (O & winners[i] == winners[i])
            return 'O';
    }
    return ' ';
}

ここでの大きな問題は、本当に X ボードと O ボードを別々に渡したいのか、それとも 2 つのショートの配列を渡す方が理にかなっているのかということです。アレイを使用する明らかな利点は、反対側のボードへのアクセスが容易になることです。たとえば、あるボードで移動が許可されているかどうかをテストするには、そのビットが他のボードで設定されているかどうかを確認します。配列に格納されたボードnを使用すると、移動したいボードを示す を渡され、1-nそのビットが既に設定されているかどうかを確認する他のボードを取得するために使用できます。

于 2013-12-02T05:14:34.610 に答える
4

あなたが話していることは、ループの巻き戻しと呼ばれます。パフォーマンスのトレードオフは複雑で、コンパイラと実行環境の両方の多くの側面に依存します。問題の議論については、ループの巻き戻しに関するウィキペディアの記事を参照してください。

于 2013-12-02T05:11:05.987 に答える