2

对于编程练习，我们被告知要实现插入、选择和冒泡排序（在 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");
}

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

4

1 回答 1

4

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

因为 JVM 以这种方式工作，所以在进行性能测量之前，您应该始终预热 JVM。基本上，在循环中多次运行您想要进行基准测试的代码，然后进行测量。（注意：这应该发生在单个 JVM 进程运行的空间内——如果 JVM 退出并重新启动，你又回到了原点。）

于 2013-11-09T17:01:11.910 回答