Sortowanie za drugim razem jest szybsze.

Question

W ramach szkolnego ćwiczenia chciałbym porównać i porównać algorytmy sortowania jako ćwiczenie Java.

Ja sam zaimplementowałem algorytmy sortowania i sortujemy obiekty klasy Person, które implementują interfejs Comparable.

Jak dotąd tak dobrze, ale nie mogę wytłumaczyć, dlaczego podczas pierwszego połączenia z metodami sortowania sortowanie trwa dłużej niż przy kolejnych połączeniach?
Dane wyjściowe poniżej przedstawiają moje wyniki.
Best, najgorsze i Średnia odnoszą się do niesegregowanych tablicy, która jest przekazywana do metody Sortowanie:

• Najlepszy: tablica jest już posortowane
• Najgorszy: tablica jest posortowana w kolejności odwrotnej
• Średnia: obiekty w tablicy są w przypadkowej kolejności

to moje wyjście:

1-call of the sorting methods 
InsertionSort Best:1799ms Worst:78ms Avg:789ms 
MergeSort  Best:10ms  Worst:3ms Avg:5ms  

2-call of the sorting methods 
InsertionSort Best:1065ms Worst:39ms Avg:691ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

3-call of the sorting methods 
InsertionSort Best:1066ms Worst:39ms Avg:692ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

4-call of the sorting methods 
InsertionSort Best:1065ms Worst:39ms Avg:691ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

Czy JVM wykonuje optymalizacje w następnych połączeniach?
Jestem zdziwiony i bardzo doceniam każdą pomoc!

Edycja: Dziękujemy za sugestie i odpowiedzi do tej pory! Aby usunąć kilka punktów - każde z wywołań w moim wyjściu odnosi się do czasu potrzebnego na pełne sortowanie!
Po każdym sortowaniu ponownie wykonuję nowe połączenie z niezarządzanymi tablicami!

Mój kod źródłowy można pobrać jako projekt Zaćmienie jako plik zip, pod następującym linkiem: Dropbox dropbox link to eclipse project.zip

PS: Nie mam doświadczenia z profilerami - gdybyś mógł wskazać mi na samouczek lub coś takiego, byłoby wspaniale.

Answer 1

Przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie niesortowanego z powodu wartości Branch Prediction.
Zostało to objęte szeroko w the most famous Stack Overflow question.

Answer 2

Jest tu wiele rzeczy, o czym świadczy różnorodność odpowiedzi.

Jednak długi czas działania pierwszego uruchomienia prawdopodobnie wyjaśnia kompilacja JIT (just-in-time). Jako discussed here, twój algorytm będzie działał w JVM przez jakiś czas jako interpretowany kod bajtowy. Kiedy monitor Hotspot ustali, że pętle sortowania są kosztowne, JVM skompiluje je do natywnego kodu. Potem będą działać znacznie szybciej. Pierwsze uruchomienie ma tę wadę, że przez jakiś czas działa w tłumaczu plus dodatkowe koszty kompilacji. Właśnie dlatego "warming up" is a common term in Java benchmarks.

Różnice w wydajności na różnych wejściach są powiązane z algorytmem sortowania. Wiele algorytmów zachowuje się w różny sposób w oparciu o początkową organizację danych, a wiele z nich jest celowo zorganizowanych, by radzić sobie dobrze z początkowo posortowanymi lub prawie posortowanymi danymi. Here is a brilliant demonstration for the case of nearly sorted input. Na przykład. sortowanie wsadowe jest ogólnie rzecz biorąc czasem kwadratowym, ale czas liniowy na prawie posortowanym wejściu (właściwie O ((k + 1) n) dla wejścia o rozmiarze n, gdzie elementy są nie więcej niż k pozycji od poprawnie posortowanego).

Następnie istnieje problem z prognozą rozgałęzień, do którego już odwołuje się link. Współcześni procesorzy mają różne mechanizmy, które próbują "odgadnąć", w jaki sposób gałąź (zasadniczo "jeśli" na poziomie maszyny) będzie działać w oparciu o najnowszą historię zebraną podczas działania programu. Koszt złej domysły jest wysoki. Na dobroć tego przypuszczenia mogą mieć wpływ zarówno szczegóły algorytmu, jak i dane.