为什么Java中的合并排序在同一数组上变得更快 [英] Why is Merge Sort in Java getting faster on same Array

问题描述

我已经用Java实现了合并排序.该类的实例名为ms. rArray是随机整数数组.为了测试，我使用以下代码运行了它:

I have implemented merge sort in Java. Instance of the class is named ms. rArray is a random integer array. For testing i ran it with the following code:

for (int i=0; i<10; i++) {
        System.out.println("Starting Merge Sort");
        testArray = rArray; // Create duplicate for testing
        long startM = System.currentTimeMillis();
        ms.sort(testArray);
        long stopM = System.currentTimeMillis();
        long durationM = stopM-startM;
        System.out.println("Size: " + size + "; Duration: " + durationM + "ms");
        System.out.println("++++++++++++++++++++++++++++++++++++++++++");
    }

输出:

Starting Merge Sort
Size: 1000000; Duration: 5853ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4527ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4082ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3000ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2930ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2904ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3403ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3570ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 2930ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3133ms

每次运行都是相同的模式. 为什么总是一直在加速?我想这与编译器有关，因为Arrays.sort表示相同的行为.我不明白的是，如果我先运行Arrays.sort然后执行我的归类排序，为什么与我自己运行归类排序的实现相比，后者还是更快?

It is the same pattern for every run. Why is it always speeding up? I guess it has to do with the compiler, since Arrays.sort shows the same behaviour. What i don't understand is, if i first run Arrays.sort and then my implementation of merge sort, why is the latter still faster compared to if i run my implementation of merge sort on it's own?

更新

按照 Makoto 的建议使用System.arraycopy(rArray, 0, testArray, 0, rArray.length);之后，输出会越来越好.但是对于合并排序，它保持不变.我的合并排序实现未保存排序结果.那么，加快JIT预热的原因是什么?

After using System.arraycopy(rArray, 0, testArray, 0, rArray.length); as suggested by Makoto (Thanks!), the output is getting better. But as for Merge sort it remains the same. My implementation of merge sort is not saving the sorting result. So is the reason for this speedup the JIT Warmup?

新输出:

Starting Default Sort
Size: 1000000; Duration: 1799ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 1816ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 945ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 944ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 944ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 943ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 957ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 963ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 964ms
++++++++++++++++++++++++++++++++++++++++++
Starting Default Sort
Size: 1000000; Duration: 952ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 5913ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3171ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3093ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 4816ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3685ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3094ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3488ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3660ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3094ms
++++++++++++++++++++++++++++++++++++++++++
Starting Merge Sort
Size: 1000000; Duration: 3604ms

推荐答案

Java中的基准标记通常相当复杂(

Benchmarking in java is in general rather complicated (How do I write a correct micro-benchmark in Java?). Next problem: testArray = rArray; doesn't generate a copy. You're sorting the same array multiple times. After the first run, the array is already sorted.

这篇关于为什么Java中的合并排序在同一数组上变得更快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！