ich versuche die Laufzeiten des Blasensortieralgorithmus in drei verschiedenen Arten von Eingang bestimmen:TIMING Blase in verschiedenen Szenarien Sortier
1) zufällig ausgewählte Zahlen
2) bereits sortierte Zahlen
3 in umgekehrter Reihenfolge sortierte) Bestellnummern
Meine Erwartung über ihre Laufzeit war:
Reverse-Nummern bestellt würde länger dauern als andere zwei.
Bereits sortierte Nummern hätten die schnellste Laufzeit.
Nach dem Zufallsprinzip ausgewählte Zahlen würden zwischen diesen beiden liegen.
Ich habe den Algorithmus mit Eingaben getestet, die mehr als 100.000 Zahlen enthalten. Die Ergebnisse waren nicht wie ich erwartet hatte. Bereits sortierte Nummern hatten die schnellste Laufzeit, aber zufällig ausgewählte Nummern benötigten fast doppelt so viel Zeit für die Ausführung als umgekehrt geordnete Zahlen. Ich habe mich gefragt, warum das passiert?
Hier ist, wie ich die Eingänge testen
int[] random = fillRandom();
int[] sorted = fillSorted();
int[] reverse = fillReverse();
int[] temp;
long time, totalTime = 0;
for (int i = 0; i < 100; i++) {
temp = random.clone();
time = System.currentTimeMillis();
BubbleSort.sort(temp);
time = System.currentTimeMillis() - time;
totalTime += time;
}
System.out.println("random - average time: " + totalTime/100.0 + " ms");
totalTime = 0;
for (int i = 0; i < 100; i++) {
temp = sorted.clone();
time = System.currentTimeMillis();
BubbleSort.sort(temp);
time = System.currentTimeMillis() - time;
totalTime += time;
}
System.out.println("sorted - average time: " + totalTime/100.0 + " ms");
totalTime = 0;
for (int i = 0; i < 100; i++) {
temp = reverse.clone();
time = System.currentTimeMillis();
BubbleSort.sort(temp);
time = System.currentTimeMillis() - time;
totalTime += time;
}
System.out.println("reverse - average time: " + totalTime/100.0 + " ms");
Der Versuch, den Java-Code auf diese Weise zu synchronisieren, wird effektiv nutzlose Ergebnisse liefern. Siehe [diese Frage] (http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) für einige Informationen, wie es richtig gemacht wird. – resueman
Verwenden Sie ein Warm-up, d. H. Führen Sie die Sortierung, sagen wir, 100 mal ohne es zu timing, dann nehmen Sie sich Zeit. Tun Sie dies für jede Variante unabhängig, d. H. Nicht nacheinander. Deaktivieren Sie GC. Auch dann können die Ergebnisse kontraintuitiv sein. Eine Sache, die helfen könnte, den umgekehrten Fall zu erklären, ist [Verzweigungsvorhersage] (http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an- unsortiertes-Array/11227902 # 11227902). –