java - 第二次排序更快

Question

作为学校练习的一部分，我想将排序算法作为 Java 练习进行比较和对比。

我自己实现了排序算法，我们对实现了 Comparable 接口(interface)的类 Person 的对象进行排序。

到目前为止一切顺利，但我无法解释的是，为什么在第一次调用我的排序方法时，排序比后续调用花费的时间更长？
下面的输出代表我的结果。
Best、Worst 和 Avg 指的是传递给排序方法的未排序数组:

• 最佳:数组已经排序
• 最差:数组倒序排列
• Avg:数组中的对象是随机排列的

这是我的输出:

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

附言我没有使用分析器的经验 - 如果你能给我指一个教程，那就太好了。

Answer 1

正如各种回复所表明的那样，这里有很多因素在起作用。

但第一次运行的运行时间较长可能是由于 JIT(即时)编译造成的。作为discussed here ，您的算法将作为解释的字节码在 JVM 中运行一段时间。当 Hotspot 监视器确定您的排序循环开销很大时，JVM 会将它们编译为 native 代码。在那之后，他们会跑得更快。第一次运行的缺点是在解释器中运行一段时间加上编译的额外成本。这就是为什么 "warming up" is a common term in Java benchmarks .

不同输入的性能差异与排序算法有关。许多算法的行为基于初始数据组织而有所不同，并且许多算法是有意组织的，以便在最初排序或接近排序的数据上表现良好。 Here is a brilliant demonstration for the case of nearly sorted input .例如。插入排序通常是二次时间，但在几乎已排序的输入上是线性时间(对于大小为 n 的输入，实际上是 O((k+1)n)，其中元素距离正确排序不超过 k 个位置。

然后是链接已经引用的分支预测问题。现代处理器具有多种机制，可以根据程序运行时收集的最新历史记录来“猜测”分支(本质上是机器级别的“if”语句)将采用哪种方式。错误猜测的代价很高。猜测的好坏很可能受到算法和数据细节的影响。