2

次の関数は2つの配列を比較し、許容誤差を考慮してすべての要素が等しい場合にtrueを返します。

// Equal
template<typename Type>
bool eq(const unsigned int n, const Type* x, const Type* y, const Type tolerance)
{
    bool ok = true;
    for(unsigned int i = 0; i < n; ++i) {
        if (std::abs(x[i]-y[i]) > std::abs(tolerance)) {
            ok = false;
            break;
        }
    }
    return ok;
}

この機能のパフォーマンスを打ち負かす方法はありますか？

4

3 に答える 3

2

ループの外側でabs（tolerance）を計算します。

ループを「メジャー」ループと「マイナー」ループに展開してみてください。「マイナー」ループの唯一のジャンプはその先頭にあり、「メジャー」ループには「if」と「break」のものがあります。分岐を避けるために、マイナーループのように実行します-の代わりにok &= (x[i]-y[i] < abstol) & (y[i]-x[i] < abstol);注意してください。&&&

次に、マイナーループを部分的に展開してベクトル化します。次に、実際に使用している浮動小数点タイプに特化し、プラットフォームのSIMD命令を使用してマイナーループを実行します。

もちろん、これを行う前によく考えてください。コードサイズが大きくなり、システムの他の部分の保守性やパフォーマンスに悪影響を与える可能性があるためです。

于 2012-12-05T03:26:45.077 に答える
1

これらの戻り変数の割り当てを回避し、許容値の絶対値を事前に計算できます。

// Equal
template<typename Type>
bool eq(const unsigned int n, const Type* x, const Type* y, const Type tolerance) {
    const Type absTolerance = std::abs(tolerance);
    for(unsigned int i = 0; i < n; ++i) {
        if (std::abs(x[i]-y[i]) > absTolerance) {
            return false;
        }
    }
    return true;
}

また、許容誤差が常に正であることがわかっている場合は、その絶対値を計算する必要はありません。そうでない場合は、それを前提条件と見なすことができます。

于 2012-12-04T05:07:18.777 に答える
1

私はこのようにします。クラスファンクターを使用してC++03バージョンをロールすることもできます。これはより冗長になりますが、同様に効率的である必要があります。

std::equal(x, x+n, y, [&tolerance](Type a, Type b) -> bool { return ((a-b) < tolerance) && ((a-b) > -tolerance); }

主な違いは、absを削除することです。実装Type方法によってabsは、条件付き実行パスが余分に取得される可能性があり、ブランチの予測ミスが多いため、これは確実に回避されます。abの重複計算は、コンパイラーによって最適化される可能性があります（必要と見なされる場合）。

もちろん、Typeに追加の演算子要件が導入され、演算子<または>が遅い場合は、abs（測定）よりも遅くなる可能性があります。

また、std::equalすべてのループと早期ブレークを実行する標準アルゴリズムであるため、これには標準ライブラリを使用することをお勧めします。通常は（少なくともC ++ 11では）維持する方が適切であり、意図を明確に示すため、最適化が向上する可能性があります。

于 2012-12-04T10:45:17.963 に答える