排序时间差异

Question

我为一项学校作业编写了一个程序，该程序打印出使用六种不同的排序算法对整数数组进行排序所需的时间：选择排序、冒泡排序、合并排序、快速排序、堆排序和基数排序。整数数组的范围从 50,000 到 300,000 个元素。

困扰我的是合并排序、堆排序、基数排序和 Collections.sort() 方法的第一个结果。

第一个数组（包含 50,000 个元素的数组）的排序时间比后续更长的数组要长。正如我所料，每个后续的较大数组都需要越来越多的时间来排序。我想知道是什么原因造成的，是我没有考虑的开销还是我的算法或程序有问题。

我已将 link 附加到显示结果的 screenshot

下面是代码示例

    int[] array = generateIntegers(50000);
    long start = System.currentTimeMillis();
    radixSort(array);
    long end = System.currentTimeMillis();
    System.out.println(end - start);

    int[] arrayTwo = generateIntegers(100000);
    start = System.currentTimeMillis();
    radixSort(arrayTwo);
    end = System.currentTimeMillis();
    System.out.println(end - start);

    int[] arrayThree = generateIntegers(150000);
    start = System.currentTimeMillis();
    radixSort(arrayThree);
    end = System.currentTimeMillis();
    System.out.println(end - start);

控制台：

    40
    10
    13

和generateIntegers(n)方法

public static int[] generateIntegers(int size)
{
    int[] arr = new int[size];

    Random rand = new Random();
    for (int i = 0; i < size; i++)
        arr[i] = rand.nextInt(integerRange);
    return arr;
}

感谢任何意见！

Answer 1

正确衡量 java 程序的性能非常复杂且困难，尤其是当您想比较不同的算法时，因为 JVM 在执行期间进行了许多巧妙的优化（例如，请参阅 Wikipedia: Java performance - Adaptive optimization).

一个主要规则是在测量任何东西之前执行 "JVM warm-up"。这使 JVM 有时间 "learn" 了解您的代码以及如何使用它（执行配置文件）来优化它。然后你应该计算多次执行的平均执行时间值。

您的绩效衡量方法可能如下所示：

public long measure(Runnable testCode, int warmupIterations, int testIterations) {
    // warmup
    for(int i = 0; i < warmupIterations; i++) {
        testCode.run();
    }

    // test
    long time = System.currentTimeMillis();
    for(int i = 0; i < testIterations; i++) {
        testCode.run();
    }
    long elapsed = System.currentTimeMillis() - time;

    return elapsed / testIterations;
}

排序时间差异

Sort time discrepancy

java

arrays

sorting

algorithm

analysis