第二轮排序更快

Question

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

我自己实现了排序算法,并对Person实现Comparable接口的类的对象进行排序.

到目前为止这么好,但我无法解释的是为什么在第一次调用我的排序方法时,排序比后续调用需要更长的时间？
下面的输出代表我的结果.
Best,Worst和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阵列进行新的调用!

我的源代码可以作为zip文件下载为eclipse项目,位于以下Dropbox链接: dropbox链接到eclipse project.zip

PS我没有使用剖析器的经验 - 如果你能指点我一个教程,那就太好了.

Answer 1

各种各样的反应表明,这里有很多工作要做.

但第一次运行的长运行时间可能是由JIT(即时)编译解释的.如此处所述,您的算法将作为解释的字节码在JVM中运行一段时间.当Hotspot监视器确定您的sort循环成本很高时,JVM会将它们编译为本机代码.在那之后,他们会跑得快得多.第一次运行的缺点是在解释器中运行一段时间加上编译的额外成本.这就是为什么"预热"是Java基准测试中的常用术语.

不同输入的性能差异与排序算法有关.许多算法基于初始数据组织表现不同,并且许多算法被有意组织以在最初排序或接近排序的数据上表现良好.这是几乎排序输入情况的精彩演示.例如,插入排序通常是二次时间,但是对于近似排序的输入的线性时间(实际上是O((k + 1)n),对于大小为n的输入,其中元素不超过正确排序的k个位置).

然后是链接已经引用的分支预测问题.现代处理器具有各种机制,这些机制试图"猜测"分支(在机器级别基本上是"if"语句)将基于程序运行时收集的最近历史记录的方式.猜测的成本很高.猜测的好处可能会受到算法和数据细节的影响.

Answer 2

由于分支预测,处理排序的数组比处理未排序的数组更快.
这已在最着名的Stack Overflow问题中得到广泛报道.