スワップ（コンピュータプログラミング）

コンピュータプログラミングにおいて、 2 つの変数を交換するという行為は、変数の値を相互に交換することを指します。通常、これはメモリ内のデータを使用して行われます。たとえば、プログラムでは、2 つの変数が次のように定義されます (疑似コード)。

データ項目 x := 1
データ項目 y := 0

スワップ(x,y);

swap() を実行すると、x には値 0 が含まれ、y には 1 が含まれます。つまり、それらの値が交換されます。この操作は、文字列や集約データ型などの他の種類の値に一般化できます。比較ソートでは、スワップを使用してデータの位置を変更します。

多くのプログラミング言語では、 swap関数が組み込まれています。C++では、オーバーロードが提供されており、 std::swap は O(1) 時間でいくつかの大きな構造体を交換できます。

2 つの変数を交換する最も簡単で、おそらく最も広く使用されている方法は、3 番目の一時変数を使用することです。

swap (x, y) を定義する
    温度:=x
    x := y
    y := 温度

これは概念的には単純で、多くの場合、2 つの変数を交換する唯一の便利な方法ですが、余分なメモリを使用します。ほとんどのアプリケーションでは問題にはなりませんが、交換される値のサイズが非常に大きい場合 (つまり、一時変数も大量のメモリを占有する場合があります)、またはソート アルゴリズムのように交換操作を何度も実行する必要がある場合があります。

さらに、C++などのオブジェクト指向言語で 2 つの変数を交換すると、一時変数のクラスコンストラクターとデストラクタが1 回呼び出され、コピー コンストラクターが 3 回呼び出される場合があります。一部のクラスでは、コンストラクターでメモリを割り当て、デストラクタでメモリの割り当てを解除するため、システムへの呼び出しコストが高くなります。配列など、大量のデータを含むクラスのコピー コンストラクターでは、データを手動でコピーする必要がある場合もあります。

XOR スワップは、XOR演算を使用して 2 つの数値変数を交換します。これは通常、上記の単純な方法よりも高速であるとされていますが、欠点もあります。XOR スワップは通常、整数などの低レベルのデータ型を交換するために使用されます。ただし、理論上は、固定長のビット文字列で表すことができる任意の 2 つの値を交換できます。

このメソッドは、2 つの変数の値を加算および減算して、それらの変数を交換します。このメソッドは、主に次の理由から、実際のアプリケーションではほとんど使用されません。

• 数値変数のみを交換できます。コンテナーなどの複雑なデータ型を加算または減算することは不可能または論理的ではない可能性があります。
• 固定サイズの変数を交換する場合、算術オーバーフローが問題になります。
• 浮動小数点演算は非結合的であるため、一般に浮動小数点値には機能しません。

ポインタを使用してヒープからメモリを割り当てるコンテナは、ポインタのみを交換することで、1回の操作で交換できます。これは通常、CやC++などのポインタをサポートするプログラミング言語で見られます。標準テンプレートライブラリは、組み込みの swap 関数をオーバーロードして、コンテナの内容をこのように効率的に交換します。^[1]

ポインタ変数は通常、固定サイズ (たとえば、ほとんどのデスクトップ コンピューターのポインタの長さは 64ビット) であり、数値であるため、XOR スワップを使用してすばやくスワップできます。

RubyやPythonなどの一部の言語では並列割り当てがサポートされており、2 つの変数を交換する表記が簡素化されます。

a, b = b, a

これは、中間データ構造 (Python ではタプル、Ruby では配列) を伴う操作の省略形です。

Javascript 6 以降では、同じことを実行する構造化分解演算子をサポートしています。

[a, b] = [b, a];

ここでは、グローバルスコープの 2 つの変数が関数を通じて値渡しされるため、一時的なストレージ変数は不要になります。

ｘ= 1 ; ｙ= 2 ;  
  

console.log ( x + "" + y ); // 1 2を出力     

関数swap ( a , b ) { x = b ; y = a ; }   
    
    


スワップ( x , y ); 

console.log ( x + "" + y ) ; //出力は21     

コンピュータでデータを交換するアプリケーションは数多くあるため、現在ではほとんどのプロセッサが組み込み命令を通じて変数を直接交換する機能を提供しています。たとえば、x86プロセッサには、 3 番目の一時レジスタを使用せずに2 つのレジスタを直接交換するXCHG命令が含まれています。プロセッサ アーキテクチャによっては、2 つのレジスタを比較して条件付きで交換する比較交換命令も提供されています。これは、排他制御技術 をサポートするために使用されます。

XCHG は見た目ほど効率的ではないかもしれません。たとえば、x86プロセッサでは、XCHG はメモリ内のオペランドへのアクセスを暗黙的にロックして操作がアトミックであることを保証するため、メモリをスワップするときには効率的でない可能性があります。このようなロックは、ミューテックスのようにスレッドセーフな同期を実装するために使用される場合に重要です。ただし、XCHG は通常、レジスタ内にある 2 つのマシン サイズのワードをスワップする最も高速な方法です。レジスタの名前変更を使用してレジスタを効率的にスワップすることもできます。

現代のコンピュータやマルチコア プロセッサの命令パイプライン化により並列コンピューティングが容易になり、2 つ以上の操作を同時に実行できるようになりました。これにより、一時変数を使用したスワップを高速化でき、他のアルゴリズムよりも優位に立つことができます。たとえば、XOR スワップ アルゴリズムでは、3 つの命令を順番に実行する必要があります。ただし、2 つの一時レジスタを使用すると、並列に実行される 2 つのプロセッサで 2 つの変数を 2 つのクロック サイクルでスワップできます。

ステップ1
 プロセッサ1: temp_1 := X
 プロセッサ2: temp_2 := Y

ステップ2
 プロセッサ1: X := temp_2
 プロセッサ2: Y := temp_1

より多くの一時レジスタが使用され、3 つの命令ではなく 4 つの命令が必要になります。いずれにせよ、これは並列コンピューティングの Bernstein の条件に違反するため、実際には別々のプロセッサに実装することはできません。このスワップが従来のバージョンよりも大きな利点を持つようにするには、プロセッサを互いに十分に同期させることは不可能です。ただし、複数のロード/ストア ユニットを備えた単一のプロセッサのスワップを最適化するために使用できます。