12

Xor演算を使用して効果的なスワップ関数を実装できることを学びました。このような：

template<class T>
void swap(T& a, T& b)
{
    a = a^b;
    b = a^b;
    a = a^b;
}

しかし、インターネット上で見つけることができるすべてのスワップの実装は、基本的に次のようになります。

template<class T>
void swap(T& a, T& b)
{
    T temp(a);
    a = b;
    b = temp;
}

VC ++ 2010でテストしたため、コンパイラは上記の2つの形式に対して同じコードを生成しなかったようです。最初のコードは、よりも速く実行されstd::swapます。最初のものにポータブルまたは他の問題がありますか？私は英語を母国語とせず、C ++が苦手なので、間違いを訂正してください。

（編集者注：テストは、std::swapインライン化できるリリースビルドではなく、最適化されていないデバッグビルドで行われた可能性があります。デバッグビルドのベンチマークは無意味です。コンパイラは通常、xor-swapをより効率的なものに最適化しません。）

4

5 に答える 5

20

Xor演算を使用して効果的なスワップ関数を実装できることを学びました

あなたは間違って学んだ、私は恐れている。XORスワップは時代遅れです。一時的な値を使用するよりも確実に高速である場合は、最新のコンパイラーやプロセッサー（「最新」とはおよそ過去20年以上を意味します）では使用しないでください。あなたはそれがあなたにとってより速かったと言います、おそらくあなたはあなたのベンチマークコードを見せて、他の人が同じ結果を得るかどうか見るべきです。

コードが整数型でしか機能しないという事実を除けば、根本的なバグがあります。お使いのバージョンのスワップでこれを試してください。

int a = 1;
swap(a,a);
std::cout << a << '\n';
于 2012-05-11T10:17:34.020 に答える
11

そして、効果はあなたがそれをどこで使うかによって異なります。

通常のCPUでは、2つの整数変数の通常のスワップは次のようになります。

$1 <- a
$2 <- b
a <- $2
b <- $1

4 ops、2ロード、2ストア、および最長の依存関係は2

xorの方法で：

$1 <- a
$2 <- b
$3 <- $1 ^ $2
$4 <- $3 ^ $2
$5 <- $3 ^ $4
a <- $5
b <- $4

7 ops、2ロード、2ストア、3ロジック、および最長の依存関係は4です。

したがって、少なくとも通常、xorとのスワップは、該当する場合でも遅くなります。

于 2012-05-11T10:05:46.520 に答える
4

最も明白な理由は、XOR演算子が整数型に対してのみ意味があることだと思います。

于 2012-05-11T09:55:09.737 に答える
2

もちろん、このxorトリックはPODタイプで機能するためです。

2つのユーザー定義の複合型を交換したい場合は、xor機能しません。生のメモリの直接コピーではなく、ディープコピーが必要になりますxor。

編集：

私はVC++2010でテストしましたが、最初のテストはより迅速に実行されます（std :: swapよりも高速です）。

本当に？デバッグモードでコンパイルしましたか？あなたの結果は何ですか？

于 2012-05-11T09:54:42.137 に答える
0

まず、XOR演算子は整数型に対してのみ定義されます。

次に、キャストトリックを使用して、非整数型を整数形式にすることができます。

しかし第3に、PODタイプを除くすべてのタイプで、これにより未定義の動作が発生します。

第4に、XOR演算で十分にサポートされているサイズ/配置がないタイプの場合は、より多くの調整が必要になります（ループは最も悪意がありません）。

をオーバーロードすることもできますがoperator^、それは、の各スペシャswap()ライゼーションがそれが存在することを確認するか、定義する必要があることを意味します。これにより、名前検索時に、その価値よりも混乱が生じる可能性があります。そしてもちろん、そのような演算子がすでに存在する場合、それは必ずしも正しい動作をするわけではなく、そのような過負荷は必ずしもまたはであるとは限らないため、パフォーマンスが低下する可能性がありinlineますconstexpr。

于 2012-05-11T09:59:31.253 に答える