1

2 つの変数があるとします。 

x = 1  
y = 2

最終結果は次のようになります。 

x = 2  
y = 1

そのために以下の方法を考えました。

temp = x // clone x
x = y
y = temp

または (XOR スワップ)

x = x XOR y
y = x XOR y
x = y XOR x

低レベルのメモリなどについて回答を得たいのですが...
最も速い方法は何ですか?

注：
仮説的に、（コード、CPUの）副作用なしでボーナス回答を得たいと思います。これは最速ですか、それとも他に高速なものはありますか？

4

3 に答える 3

6

問題は、最新の CPU アーキテクチャではこの答えが得られないことです。それらは多くの効果を隠し、多くの非常に微妙な効果を露出させます。

CPU レジスタに値があり、予備のレジスタがある場合、そのtempウェイは最速のウェイか、消費電力が最も少ないウェイです。

XOR または +/- (ちなみにとてもきちんとしています!) メソッドを使用するのは、追加の場所 (追加のメモリ変数または追加のレジスタ) を持つ余裕がない状況です。これは奇妙に思えるかもしれませんが、たとえば C プリプロセッサ マクロ内では、新しい変数を (簡単に) 宣言することはできません。

変数がメモリ内にある場合、すべてのバリアントは高性能 CPU で同じように動作する可能性が非常に高くなります。コンパイラがコードを最適化しない場合でも、CPU は事実上すべてのメモリ アクセスを回避し、レジスタ アクセスと同じくらい高速にします。

全体として、私は次のように言う傾向があります。この速度について心配する必要はありません。このレベルで最適化することは重要ではありません。スワップを完全に避けるようにしてください。これが最速です。

于 2013-11-08T20:06:53.557 に答える
4

http://en.wikipedia.org/wiki/XOR_swap_algorithm

最新のコンパイラのほとんどは、ナイーブ スワップの一時変数を最適化して取り除くことができます。この場合、ナイーブ スワップは XOR スワップと同じ量のメモリと同じ数のレジスタを使用し、少なくとも同じくらい高速であり、多くの場合より高速です。また、XOR スワップは読みにくく、この手法に慣れていない人には完全に不透明です。最新の CPU アーキテクチャでは、XOR 手法は、一時変数を使用してスワッピングを行うよりもかなり遅くなります。その理由の 1 つは、最新の CPU が命令パイプラインを介して並列に命令を実行しようとしていることです。XOR 手法では、各操作への​​入力は前の操作の結果に依存するため、厳密に順番に実行する必要があります。

この質問も参照してください。

整数型の std::swap はどれくらい速いですか?

XOR スワップでは、2 つの変数が同じメモリ位置を参照していないことを最初に確認する必要があることに注意してください。もしそうなら、あなたはそれをゼロに設定することになります.

于 2013-11-08T20:14:53.063 に答える
1

最近のほとんどの CPU アーキテクチャは命令を並列化しようとしますが、XOR スワップでは、各行は前の結果に依存します (並列化できません)。一時変数スワップの場合、ほとんどのコンパイラは一時変数を最適化します。これにより、同じ量のメモリを使用するだけでなく、単純な方法で同じ速度または速度で実行されます。

別のスワップの代替手段は次のとおりです。

x = x + y
y = x - y
x = x - y

同様に、XOR スワップの効率と速度に関する議論もここに当てはまります。

編集：hatchetが言ったように、（+/-）アプローチも慎重に行わないとオーバーフローを引き起こす可能性があります

于 2013-11-08T20:02:40.360 に答える