bester Algorithmus zum Tauschen?

Ich habe von einem Freund von mir gehört, dass der beste Algorithmus zum Tauschen ist "(a^= b^= a^= b)" wobei a und b sind zwei ganze Zahlen zu vertauschen. aber wenn ich dies mit der Sprache c anwendete, kam es zu einem Absturz. kann jemand von Ihnen feine Leute den möglichen Grund dafür erklären? schlagen Sie bitte den besten Algorithmus für das Tauschen vor. danke !!!! Jungs Ich würde gerne den Grund für den Absturz wissen.bester Algorithmus zum Tauschen?

Quelle

2010-03-13 Ashish Yadav

Ich kann nicht glauben, das ist sogar eine Frage zu SO. Was ist falsch mit 'std :: swap'? –

+14

@BillyONeal: da std :: swap ist C++ und diese Frage ist mit C markiert. – LiraNuna

OK - Sorry - Lassen Sie mich das zu "Was ist falsch mit der einfachen Implementierung typisch für' std :: swap "? temp = eins; eins = zwei; zwei = temp; 'Ernsthaft - wenn swap ein Geschwindigkeitsbegrenzer Ihres Programms ist, dann haben Sie ein Problem, das ich gerne haben würde. –

dieser Swapping-Trick ist manchmal gefährlich, ich habe gesehen, dass ein falsches Quicksort-Programm mit diesem Swap falsche Ergebnisse erzeugt. Aber ein üblicher Austausch erzeugt ein korrektes Programm.

In Anbetracht der Geschwindigkeit generiert der Compiler manchmal schneller Code, wenn wir eine tmp-Variable verwenden.

Verwendung tmp = a; a = b; b = tmp;

Quelle

2010-03-13 05:24:22

danke @yin ich würde gerne wissen, warum ist mein Trick sehr gefährlich? –

XOR-Swap ('a^= b^= a^= b ') funktioniert nur bei ganzen Zahlen (und Zeigern). Der XOR-Tausch ändert sowohl "a" als auch "b" auf 0, wenn sie gleich sind. – LiraNuna

Angenommen, "a" und "b" sind Zeiger, die auf dasselbe verweisen. Dann wird '(* a)^= (* b)^= (* a)^= (* b)' wird den Wert auf Null setzen. In C++, wenn dies Referenzen sind, können Sie dies ohne die Dereferenzierung tun. Aber der wahre Grund für das, was @Yin Zhu vorschlägt, ist, dass Ihr Code klar sein sollte, und Sie sollten sich keine Gedanken über eine solche Mikrooptimierung machen. – rlbond

-2

Mit dieser Logik für numerische Werte:

int a = 10, b =5 ; 
    a = a-b; 
    b = b+a ;   // b gets the original value of a 
    a = b - a; // a gets the original value of b 
    printf ("value : %d %d \n",a ,b) ;

Quelle

2010-03-13 05:40:41 Pavunkumar

Was passiert, wenn 'a'' INT_MAX' ist und 'b'' INT_MIN' ist? Mit anderen Worten, "a-b" kann überlaufen/unterlaufen. –

@Alok: Trotz des Überlaufs gibt es immer noch die richtige Antwort mit umlaufender Arithmetik. – dan04

@ dan04: Wraparound ist nicht garantiert - in C/C++ Integerüberlauf ist UB. –

http://en.wikipedia.org/wiki/Swap_(computer_science) See.

Die Verwendung einer temporären Variablen generiert mehr Overhead, ist jedoch stabiler als der XOR-Swap-Algorithmus und die parallele Berechnung macht es schneller als XOR-Swap.

Das erste Codebeispiel von http://www.ibm.com/developerworks/linux/library/l-metaprog1.html für eine solide Implementierung der Verwendung einer temporären Variable für das Swapping.

Quelle

2010-03-13 05:45:56 Yktula

Warum generiert mehr Overhead für die temporäre Variablenlösung? Der XOR-Austausch erzeugt auch mehr Rechenaufwand. – phoxis

a^=b^=a^=b; wahrscheinlich stürzt ab, weil es die gefürchtete undefined Verhalten aufruft. Die Regel, die es bricht, ist, dass es a zweimal ohne einen dazwischenliegenden Sequenzpunkt ändert. Es kann durch das Einfügen einiger Sequenzpunkte festgelegt werden - zum Beispiel mit dem Komma-Operator:

a ^= (b ^= a ^= b, b);`

Oder indem sie sie in mehrere Aussagen zu brechen:

b ^= a ^= b; a ^= b;

Es ist nach wie vor, jedoch in der Regel eine schlechte Methode für den Austausch von Variablen - einige der anderen Antworten und Kommentare haben ausreichend erklärt warum.

Quelle

2010-03-13 07:47:18 caf

Schreiben Sie den Code, der vom Menschen schneller gelesen werden kann. Und vertrauen Sie Compiler die Möglichkeit, die meiste Zeit besseren Code zu generieren. Machen Sie ein Profiling, um zu sehen, ob dies der einzige Ort ist, um die Geschwindigkeit zu verbessern. Wenden Sie dann XOR-Lösungen an, die oben mehrfach aufgeführt sind. Es funktioniert möglicherweise nicht überall.

Quelle

2010-03-13 09:52:11 Jayan

bester Algorithmus zum Tauschen?

Antwort

Verwandte Themen