java为什么对随机填充的数组进行排序会越来越快

Question

在编程练习中，我们被告知实现插入、选择和冒泡排序（java）。 我想测试排序的执行速度，所以我写了一个循环来随机填充和排序一个数组10次。前两种排序的时间大约是最后8次迭代的两倍。。为什么?

在这里，我把代码的相关部分放在这里

// class fields
public static final int POPULATE_MAX = 1000000000;
public static final int POPULATE_MIN = -1000000000;

public static void populateRandom(int[] toPopulate)
{
    // populate array with random integers within bounds set by class fields
    for (int i = 0; i < toPopulate.length; i++)
    {
        toPopulate[i] = (int)(Math.random() * (POPULATE_MAX - POPULATE_MIN))
            + POPULATE_MIN;
    }
} // end of method populateRandom(int[] toPopulate)

public static void insertionSort(int[] toSort) throws IllegalArgumentException
{
    if (toSort == null)
    {
        throw new IllegalArgumentException();
    }
    if (toSort.length <= 1) return;

    int temp;

    // Index i points to the next unsorted element; assigned to temp
    for (int i = 1; i < toSort.length; i++)
    {
        temp = toSort[i];

        // This loop searches through the sorted portion of the array and
        // determines where to put the aforementioned unsorted element
        for (int j = i - 1; j >= 0; j--)
        {
            if (temp < toSort[j])
            {
                toSort[j + 1] = toSort[j];
                if(j == 0)
                    toSort[j] = temp;
            }
            else
            {
                toSort[j + 1] = temp;
                break;
            } // end of if (temp < toSort[j])
        } // end of for (int j = i - 1; j >= 0; j--)
    } // end of for (int i = 1; i < toSort.length; i++)
} // end of method insertionSort(int[] toSort) throws IllegalArgumentException

public static void main(String[] args)
{
    long time;
    for (int testRun = 0; testRun < 10; testRun++)
    {
        int[] array = new int[100000];
        System.out.print(testRun + "...");
        populateRandom(array);
        time = System.currentTimeMillis();
        insertionSort(array);
        time = System.currentTimeMillis() - time;
        for (int i = 0; i < array.length - 1; i++)
        {
            if (array[i] > array[i+1]) System.out.println(i + ". Bad");
        }
        System.out.println(time + " Done");
    }
    System.out.println("ABS Done");
}

我猜这与分支预测有关，但我不确定为什么后续排序会明显更快

Answer 1

在最初的几次迭代中，JVM可能是以解释模式运行的，然后它会注意到您正在重复运行同一个方法，并将其编译为本机代码。如果调用同一方法的次数更多，甚至可能会导致进一步的优化“启动”

因为JVM是这样工作的，所以在进行性能测量之前，您应该总是预热JVM。基本上，在循环中多次运行您想要基准测试的代码，然后进行测量。（注意：这应该发生在单个JVM进程运行的空间内，如果JVM退出并再次启动，那么就回到原点。）