排序第二次更快

作爲學校練習的一部分，我想比較排序算法並將其與Java練習對比。排序第二次更快

我自己實現了排序算法，我們對實現Comparable接口的類Person的對象進行排序。

到目前爲止很好，但我無法解釋的是，爲什麼在第一次調用我的排序方法時，排序需要比後續調用更長的時間？
輸出波紋管表示我的結果。
最佳，最壞和平均指被傳遞到分選方法的排序的數組：

最佳：陣列已經排序
最壞：該陣列被以相反的順序
平均排序方法：陣列中的對象是在隨機的順序

這是我的輸出：

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

JVM是否對後續調用進行優化？
我很困惑，將不勝感激任何幫助！

編輯：感謝您的建議和答案，到目前爲止！爲了清楚幾點 - 我輸出中的每個呼叫都指的是完成整理所需的時間！
每次排序後，我再次使用UNSORTED數組進行新的調用！

我的源代碼可以下載作爲一個Eclipse項目作爲一個zip文件，在下面的Dropbox的鏈接： dropbox link to eclipse project.zip

附：我沒有使用Profiler的經驗 - 如果你能指點我的教程，那麼這很棒。

來源

2016-03-12 erik.eilif

你可以發佈代碼嗎？ –

您是否在運行之間重新洗牌數據？ – user1676075

這很難說沒有任何代碼;並且例如;這可能取決於你如何測量。有關性能測量方面可能遇到的一些缺陷。有時候，例如，Java即時編譯器會做有趣的事情。 – GhostCat

由於Branch Prediction，處理排序的數組比處理未排序的數組要快。
這已被廣泛覆蓋在the most famous Stack Overflow question。

來源

2016-03-12 17:39:32 Idos

嗨，我知道這一點，但這不是我的問題！我認爲你閱讀我的文章太快了。 –

嗨，Erik，我認爲情況正是如此。如果我（有點）錯了，我表示歉意，但從這個問題的表達方式來看，這似乎是答案。分支預測是原因*排序第二輪更快*（問題標題逐字）:) – Idos

嗨Idos，不需要道歉！也許我的問題有點不清楚 - 英語不是我的母語！我明白你的答案，如果我嘗試對未排序或已排序的數組進行排序，那麼答案是不一樣的 - 而且我明白了！但是 - 你是說如果我發送一個未排序的數組到一個方法來排序它，並且在結束之後，我再次發送相同的原始UNSORTED數組到該方法，那麼由於分支預測它會更快？我不太瞭解分支預測:( –

在這裏工作有很多事情，因爲各種反應表明。

但是第一次運行的長運行時間可能是由JIT（即時編譯）編譯解釋的。由於discussed here，您的算法將在JVM中運行一段時間作爲解釋字節碼。當Hotspot監視器確定你的排序循環代價高昂時，JVM會將它們編譯爲本機代碼。之後，他們跑得快得多。第一次運行在解釋器中運行一段時間，加上編譯的額外成本。這是爲什麼"warming up" is a common term in Java benchmarks。

不同輸入的性能差異與排序算法有關。許多算法在初始數據組織的基礎上行爲不同，許多算法有意組織起來對最初排序或近似排序的數據做得很好。 Here is a brilliant demonstration for the case of nearly sorted input。例如。插入排序通常是二次時間，但對於幾乎排序的輸入（實際上O（（k + 1）n）的線性時間，對於大小爲n的輸入，其中元素不超過正確排序的k個位置。

然後有鏈接引用的分支預測問題。現代處理器有各種機制，試圖根據程序運行時收集的最近歷史記錄來「猜測」分支（本質上是機器級別的「if」語句）的方式。猜測成本很高。猜測的好處很可能受到算法和數據細節的影響。

來源

2016-03-12 18:11:01 Gene

哇 - 謝謝！我不明白你的答案，但我會閱讀JIT。謝謝基因！ –

排序第二次更快

回答

相關問題