0

C++ で分岐を削除して遊んで、出力の背後にある理由を解読できません。

PopHi()昇順の並べ替えられた int の 2 つのベクトルと、これまでで最大のものの現在のインデックスを取ります。2つのうち大きい方のインデックスをデクリメントすることにより、すべての最大のintを「ポップ」します。

コード

オリジナル：

void PopHi(vector<int> &arrA, vector<int> &arrB, int &idxHiA, int &idxHiB) {
    int hi = max(arrA[idxHiA], arrB[idxHiB]);
    if (hi == arrA[idxHiA])
        --idxHiA;
    else
        --idxHiB;
}

Nobranch バージョン 1:

void PopHi(vector<int> &arrA, vector<int> &arrB, int &idxHiA, int &idxHiB) {
    idxHiA -= (arrA[idxHiA] > arrB[idxHiB]);
    idxHiB -= (!(arrA[idxHiA] > arrB[idxHiB]));
}

Nobranch バージョン 2。それらが等しい場合、どちらを選択してもかまわないためです。

void PopHi(vector<int> &arrA, vector<int> &arrB, int &idxHiA, int &idxHiB) {
    idxHiA -= (arrA[idxHiA] >= arrB[idxHiB]);
    idxHiB -= (!(arrA[idxHiA] >= arrB[idxHiB])); // extra paranoia parens
}

そして、これが私がそれを使用している方法です：

// compiled with g++ -std=c++11 main.cpp -o run
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    vector<int> arrA({1, 3, 5});
    vector<int> arrB({5});
    int idxHiA = 2;
    int idxHiB = 0;
    cout << idxHiA << ", " << idxHiB << endl;
    PopHi(arrA, arrB, idxHiA, idxHiB);
    cout << idxHiA << ", " << idxHiB << endl;
    return 0;
}

出力

オリジナル：

2, 0
1, 0 // ok

バージョン 1:

2, 0
2, -1 // also ok

バージョン 2:

2, 0
1, -1 // wtf??
4

1 に答える 1

3 
idxHiA -= (arrA[idxHiA] >= arrB[idxHiB]);

あなたはここで変わりidxHiAます...

idxHiB -= (!(arrA[idxHiA] >= arrB[idxHiB]));

...ここであなたを噛みます。の古い値を使用したいのですがidxHiA、デクリメントされた値を使用しています (これは違法である可能性があります)。その位置の要素はもはや最大ではありません。

比較の結果をブール変数に保存することをお勧めします。これにより、読みやすくなります。

PS: アセンブラーで、「分岐なし」バージョンが実際に分岐がないことを確認します。ブール変数を使用した操作は、ブランチを使用して変換されることがあります。

于 2012-11-01T00:03:10.410 に答える