我自己实现了排序算法,并对实现Comparable接口的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阵列进行新的调用！
我的源代码可以作为zip文件下载为eclipse项目,位于以下DropBox链接：
dropbox link to eclipse project.zip
附：我没有使用剖析器的经验 – 如果你能指点我一个教程,那就太好了.
解决方法
但第一次运行的长运行时间可能是由JIT(即时)编译解释的.作为discussed here,您的算法将作为解释的字节码在JVM中运行一段时间.当Hotspot监视器确定您的sort循环成本很高时,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”语句)将基于程序运行时收集的最近历史记录的方式.猜测的成本很高.猜测的好处可能会受到算法和数据细节的影响.
