質問
私はこれを読みました カードのシャッフルについて投稿します そして、多くのシャッフルおよびソートアルゴリズムでは、リストまたは配列に2つのアイテムを交換する必要があります。しかし、優れた効率的なスワップ方法はどのように見えますか?
と言ってみましょう T[]
そしてaの List<T>
. 。これら2つのアイテムを交換する方法をどのように実装しますか?
Swap(ref cards[i], ref cards[n]); // How is Swap implemented?
解決
さて、あなたが投稿したコード(ref cards[n]
)配列でのみ動作することができます(リストではありません) - ただし、単純に使用します(ここで foo
と bar
2つの値です):
static void Swap(ref int foo, ref int bar) {
int tmp = foo;
foo = bar;
bar = tmp;
}
またはおそらく(アトミックが必要な場合):
Interlocked.Exchange(ref foo, ref bar);
個人的には、私はスワップ方法を気にするとは思わない - 直接それを行うだけです。これは、(リストまたは配列のいずれか)を使用できることを意味します。
int tmp = cards[n];
cards[n] = cards[i];
cards[i] = tmp;
どちらかのリストで機能したスワップ方法を本当に書きたいと思ったら また 配列、あなたは次のようなことをする必要があります:
static void Swap(IList<int> list, int indexA, int indexB)
{
int tmp = list[indexA];
list[indexA] = list[indexB];
list[indexB] = tmp;
}
(このジェネリックを作るのは些細なことです) - ただし、配列で動作する元の「インライン」バージョン(つまり、メソッドではありません)はより速くなります。
他のヒント
使用する:
void swap(int &a, int &b)
{
// &a != &b
// a == b OK
a ^= b;
b ^= a;
a ^= b;
return;
}
私はC#セクションにいることに気づきませんでした。これはC ++コードですが、同じ基本的なアイデアが必要です。私も ^であると信じています。代わりに見えます &
「ref」(?)が必要になる場合があります。私はわかりません。
良いスワップとは、コンテンツを交換しないものです。 C/C ++では、これはコンテンツを交換する代わりにポインターを交換することに似ています。このスワッピングのスタイルは高速で、例外保証が付属しています。残念ながら、私のc#はさびたもので、コードに入れることができません。簡単なデータ型の場合、このスタイルはあまり得られません。しかし、あなたが慣れていて、より大きな(そしてより複雑な)オブジェクトに対処しなければならないと、それはあなたの命を救うことができます。
これはどうですか?これは、スワップ方法の一般的な実装です。 JITは、閉じたタイプのためだけにコンパイルされたバージョンを作成するので、パフォーマンスを心配する必要はありません!
/// <summary>
/// Swap two elements
/// Generic implementation by LMF
/// </summary>
public static void Swap<T>(ref T itemLeft, ref T itemRight) {
T dummyItem = itemRight;
itemLeft = itemRight;
itemRight = dummyItem;
}
Hth Lorenzo
不思議に思う人にとっては、スワッピングも拡張メソッド(.NET 3.0以降)で行うこともできます。
一般に、拡張方法「この」値がrefであると言う可能性はないようです。したがって、それを返して古い値をオーバーライドする必要があります。
public static class GeneralExtensions {
public static T SwapWith<T>(this T current, ref T other) {
T tmpOther = other;
other = current;
return tmpOther;
}
}
この拡張法は次のように使用できます。
int val1 = 10;
int val2 = 20;
val1 = val1.SwapWith(ref val2);