C#: Gute/beste Implementierung der Swap-Methode

Question

Ich lese diese post about card shuffling und in vielen Misch- und Sortieralgorithmen müssen Sie zwei Elemente in einer Liste oder einem Array tauschen. Aber wie sieht eine gute und effiziente Swap-Methode aus?

Sagen wir für eine T[] und für eine List<T>. Wie würden Sie am besten eine Methode implementieren, bei der zwei Elemente in diesen beiden ausgetauscht werden?

Swap(ref cards[i], ref cards[n]); // How is Swap implemented? 

Answer 1

Nun, der Code, den Sie geschrieben haben (ref cards[n]) nur mit einem Array (keine Liste) arbeiten - aber Sie würden verwenden Sie einfach (wo foo und bar die beiden Werte):

static void Swap(ref int foo, ref int bar) { 
    int tmp = foo; 
    foo = bar; 
    bar = tmp; 
} 

Oder vielleicht (wenn Sie wollen Atom):

Interlocked.Exchange(ref foo, ref bar); 

Persönlich glaube ich nicht, dass ich mich mit einer Tauschmethode beschäftigen würde - tu es einfach direkt; Dies bedeutet, dass Sie (entweder für eine Liste oder für ein Array) verwenden können:

int tmp = cards[n]; 
cards[n] = cards[i]; 
cards[i] = tmp; 

Wenn Sie wirklich eine Swap-Methode schreiben, arbeitete entweder auf eine Liste oder ein Array wollen, dann würden Sie müssen so etwas wie:

static void Swap(IList<int> list, int indexA, int indexB) 
{ 
    int tmp = list[indexA]; 
    list[indexA] = list[indexB]; 
    list[indexB] = tmp; 
} 

(es trivial wäre, diese generisch zu machen) - aber die Original „inline“ Version (dh keine Methode) auf einem Array arbeiten wird schneller sein.

Answer 2

Ein guter Austausch ist einer, wo Sie den Inhalt nicht austauschen. In C/C++ wäre dies vergleichbar mit dem Vertauschen von Zeigern, anstatt den Inhalt auszutauschen. Diese Art des Swappings ist schnell und kommt mit einer gewissen Ausnahmegarantie. Leider ist meine C# zu rostig, um es in den Code zu schreiben. Für einfache Datentypen bietet dieser Stil nicht viel. Aber sobald Sie gewöhnt sind und mit größeren (und komplizierteren) Objekten zu tun haben, kann es Ihr Leben retten.

Answer 3

Verwendung:

void swap(int &a, int &b) 
{ 
    // &a != &b 
    // a == b OK 
    a ^= b; 
    b ^= a; 
    a ^= b; 
    return; 
} 

ich nicht wusste, war ich in der C# Abschnitt. Dies ist C++ - Code, sollte aber die gleiche Grundidee haben. Ich glaube^ist auch XOR in C#. Es sieht aus wie anstelle von & benötigen Sie "Ref" (?). Ich bin nicht sicher.

Answer 4

Was ist damit? Es ist eine generische Implementierung einer Swap-Methode. Der Jit wird eine kompilierte Version NUR für Sie geschlossene Typen erstellen, so dass Sie sich keine Gedanken über die Leistung machen müssen!

/// <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

Answer 5

Für alle fragen, Tauschen kann auch auch mit Erweiterungsmethoden (.NET 3.0 und höher) durchgeführt werden.

Im Allgemeinen scheint es keine Möglichkeit zu geben zu sagen, dass Erweiterungsmethoden "dieser" Wert ref ist, also müssen Sie es zurückgeben und den alten Wert überschreiben.

int val1 = 10; 
int val2 = 20;  
val1 = val1.SwapWith(ref val2);