Hallo,
es geht um Performance bei der Sortierung/Vertauschen von Zahlen in Java.
Wer kennt das Beispiel nicht: "Vertauschen Sie den Inhalt der Variablen a und b"?
Dazu gibt es in Java verschiedene Ansätze:
Ansatz 1: "Dritte Variable"
Das ist eig. der Standard Ansatz fast aller Programmierer die zuvor noch nicht viel mit Bit-Operatoren gearbeitet haben.
P.S. es ist zudem auch die bessere Lösung
Ansatz 2: "XOR"
Diese Variante wird meist von leuten Benutzt die zuvor andere Sprachen die Hardware näher sind benutzt haben und von leuten die sich mit Mathematik auseinandersetzen. So gesehen sollte diese Variante auch besser als Ansatz 1 sein, da logisch gesehn beide 3 Maschinenschritte benötigen, jedoch Ansatz 2 keine 3te Variable benötigt.
ABER in Java ist dies nicht der Fall, da hier der Ansatz 2 langsamer ist als Ansatz 1!
Ansatz 3: "Eigener Ansatz"
Es gibt noch einen dritten Ansatz, welcher ein bisschen komplexer ist. Dieser ist auf eine einzige Zeile komprimiert und benutzt die Mehrfachzuweisung von Java. Diesen kleinen Algorithmus habe ich vor einigen Monaten "entwickelt" und wurde dank @Brotcrunsher auch noch leicht Optimiert.
Ich haben dazu ein kleines Programm geschrieben, welches ein großes zahlen Array mit allen drei Ansätzen sortiert und dabei die Zeiten mit protokolliert. Bei meinen Tests war Ansatz 3 immer ein bisschen schneller als Ansatz 1, welcher wiederum schneller als Ansatz 2 ist.
Aber wieso ist Ansatz 3 schneller?
Anscheinend kann Java die Multiplikation mit 0 intern noch Optimieren sowie das OR mit 0, somit würde nur die Mehrfachzuweisung übrig bleiben. Dies ist jedoch mehr eine Behauptung als eine Tatsache, mit dem Thema "Warum" habe ich mich eher weniger befasst.
Ich werde zudem noch das Programm/die Klasse zum Testen in den Anhang packen.
Falls Ihr noch andere wege kennt oder evtl ein anderer Ansatz schneller sein sollte wie von mit erzählt könnt Ihr mir gerne Antworten, es würde mich persönlich Interessieren.
Mit freundlichen Grüßen,
euer AntiMuffin
Die Datei im Anhang ist ein bisschen veraltet, es muss heißen "a=b| ( 0 * ( b=a) ); " statt " a=b| ( 0 & ( b=a) ); "
es geht um Performance bei der Sortierung/Vertauschen von Zahlen in Java.
Wer kennt das Beispiel nicht: "Vertauschen Sie den Inhalt der Variablen a und b"?
Dazu gibt es in Java verschiedene Ansätze:
Ansatz 1: "Dritte Variable"
Das ist eig. der Standard Ansatz fast aller Programmierer die zuvor noch nicht viel mit Bit-Operatoren gearbeitet haben.
P.S. es ist zudem auch die bessere Lösung
Java:
public class Ansatz1{
public static void main(String[] args){
int a = 10;
int b = 20;
// vertauschen mit dritter variable.
int c = a;
a = b;
b = c;
}
}
Ansatz 2: "XOR"
Diese Variante wird meist von leuten Benutzt die zuvor andere Sprachen die Hardware näher sind benutzt haben und von leuten die sich mit Mathematik auseinandersetzen. So gesehen sollte diese Variante auch besser als Ansatz 1 sein, da logisch gesehn beide 3 Maschinenschritte benötigen, jedoch Ansatz 2 keine 3te Variable benötigt.
ABER in Java ist dies nicht der Fall, da hier der Ansatz 2 langsamer ist als Ansatz 1!
Java:
public class Ansatz2{
public static void main(String[] args){
int a = 10; // 0000 1010
int b = 20; // 0001 0100
// vertauschen mit XOR.
a = a ^ b; // 0001 1110 = 0000 0010 ^ 0001 0100
b = b ^ a; // 0000 1010 = 0001 0100 ^ 0001 1110
a = a ^ b; // 0001 0100 = 0001 1110 ^ 0000 1010
// Dies könnte sogar auf eine Zeile reduziert werden.
}
}
Ansatz 3: "Eigener Ansatz"
Es gibt noch einen dritten Ansatz, welcher ein bisschen komplexer ist. Dieser ist auf eine einzige Zeile komprimiert und benutzt die Mehrfachzuweisung von Java. Diesen kleinen Algorithmus habe ich vor einigen Monaten "entwickelt" und wurde dank @Brotcrunsher auch noch leicht Optimiert.
Java:
public class Ansatz3 {
public static void main(String[] args){
int a = 10;
int b = 20;
// vertauschen mit eigenem Algorithmus
/*Zunächst wird das rechte b zu a und mal 0 genommen, somit ist b = a und alles hinter | ist 0
Anschließend ist das linke b (hier steht noch die 20 drinnen) und mit OR 0 ist es immer noch 20, dies wird danach a zugewiesen. */
a=b| ( 0 * ( b=a) );
}
}
Ich haben dazu ein kleines Programm geschrieben, welches ein großes zahlen Array mit allen drei Ansätzen sortiert und dabei die Zeiten mit protokolliert. Bei meinen Tests war Ansatz 3 immer ein bisschen schneller als Ansatz 1, welcher wiederum schneller als Ansatz 2 ist.
Aber wieso ist Ansatz 3 schneller?
Anscheinend kann Java die Multiplikation mit 0 intern noch Optimieren sowie das OR mit 0, somit würde nur die Mehrfachzuweisung übrig bleiben. Dies ist jedoch mehr eine Behauptung als eine Tatsache, mit dem Thema "Warum" habe ich mich eher weniger befasst.
Ich werde zudem noch das Programm/die Klasse zum Testen in den Anhang packen.
Falls Ihr noch andere wege kennt oder evtl ein anderer Ansatz schneller sein sollte wie von mit erzählt könnt Ihr mir gerne Antworten, es würde mich persönlich Interessieren.
Mit freundlichen Grüßen,
euer AntiMuffin
Die Datei im Anhang ist ein bisschen veraltet, es muss heißen "a=b| ( 0 * ( b=a) ); " statt " a=b| ( 0 & ( b=a) ); "
Anhänge
Zuletzt bearbeitet: