java - 同样的代码，同样的输入，有时跑得快，有时跑得慢，为什么？

Question

我编写了一些 java 类，以评估/演示不同的排序算法。但是，当我运行我的演示类(class)时，我感到很困惑。希望大家给我一个解释。 (这道题不是作业。)

首先我会列出一些与这个问题相关的代码。

抽象演示

public abstract class AbstractDemo {
    protected final int BIG_ARRAY_SIZE = 20000;
    protected final int SMALL_ARRAY_SIZE = 14;
    protected Stopwatch stopwatch = new Stopwatch();

    public final void doDemo() {
        prepareDemo();
        specificDemo();
    }

    protected abstract void prepareDemo();

    protected abstract void specificDemo();

    protected final void printInfo(final String text) {
        System.out.println(text);
    }
}

排序演示

public class SortingDemo extends AbstractDemo {
    private static final String FMT = "%-10s| %-21s| %7s ms.";
    private static final String SPL = AlgUtil.lineSeparator('-', 45);
    private static final String SPLT = AlgUtil.lineSeparator('=', 45);

    private int[] data;

    private final List<Sorting> demoList = new LinkedList<Sorting>();

    @Override
    protected void specificDemo() {
        int[] testData;
        //*** this comment is interesting!!! for (int x = 1; x < 6; x++) {  

            printInfo(String.format("Sorting %7s elements", data.length));
            printInfo(SPLT);
            for (final Sorting sort : demoList) {

                // here I made a copy of the original Array, avoid to sort an already sorted array.
                testData = new int[data.length];
                System.arraycopy(data, 0, testData, 0, data.length);
                stopwatch.start();
                // sort
                sort.sort(testData);
                stopwatch.stop();
                printInfo(String.format(FMT, sort.getBigO(), sort.getClass().getSimpleName(), stopwatch.read()));
                printInfo(SPL);
                testData = null;
                stopwatch.reset();
            }
        //}
    }

    @Override
    protected void prepareDemo() {
        data = AlgUtil.getRandomIntArray(BIG_ARRAY_SIZE, BIG_ARRAY_SIZE * 5, false);
        demoList.add(new InsertionSort());
        demoList.add(new SelectionSort());
        demoList.add(new BubbleSort());
        demoList.add(new MergeSort());  //here is interesting too
        demoList.add(new OptimizedMergeSort());

    }

    public static void main(final String[] args) {
        final AbstractDemo sortingDemo = new SortingDemo();
        sortingDemo.doDemo();
    }
}

秒表

public class Stopwatch {
    private boolean running;
    private long startTime;
    private long elapsedMillisec;

    public void start() {
        if (!running) {
            this.startTime = System.currentTimeMillis();
            running = true;
        } else {
            throw new IllegalStateException("the stopwatch is already running");
        }
    }

    public void stop() {
        if (running) {
            elapsedMillisec = System.currentTimeMillis() - startTime;
            running = false;
        } else {
            throw new IllegalStateException("the stopwatch is not running");
        }
    }

    public void reset() {
        elapsedMillisec = 0;

    }

    public long read() {
        if (running) {
            elapsedMillisec = System.currentTimeMillis() - startTime;
        }
        return this.elapsedMillisec;
    }

}

生成随机数组的方法

public static int[] getRandomIntArray(final int len, final int max, boolean allowNegative) {
        final int[] intArray = new int[len];
        final Random rand = new Random();
        rand.setSeed(20100102);

        if (!allowNegative) {
            if (max <= 0) {
                throw new IllegalArgumentException("max must be possitive if allowNegative false");
            }
            for (int i = 0; i < intArray.length; i++) {
                intArray[i] = rand.nextInt(max);
            }
        } else {
            int n;
            int i = 0;
            while (i < len) {
                n = rand.nextInt();
                if (n < max) {
                    intArray[i] = n;
                    i++;
                }
            }
        }

        return intArray;
    }

你可以看到，我生成了一个int数组，有20000个元素。因为我在 getRandomIntArray 方法中有一个固定的种子，所以每次调用它时我总是有相同的数组。 SortingDemo 类有 main 方法，如果我运行这个类，我得到输出:

Sorting   20000 elements
=============================================
O(n^2)    | InsertionSort        |     101 ms.
---------------------------------------------
O(n^2)    | SelectionSort        |     667 ms.
---------------------------------------------
O(n^2)    | BubbleSort           |    1320 ms.
---------------------------------------------
O(nlog(n))| MergeSort            |      39 ms.
---------------------------------------------
O(?)      | OptimizedMergeSort   |      11 ms.
---------------------------------------------

看起来不错。现在出现了让我困惑的事情。如果我更改 SortingDemo 中的 demoList.add() 序列，请说:

demoList.add(new InsertionSort());
    demoList.add(new SelectionSort());
    demoList.add(new BubbleSort());
    // OptimizedMergeSort before Mergesort
    demoList.add(new OptimizedMergeSort()); 
    demoList.add(new MergeSort());

我得到了:

Sorting   20000 elements
=============================================
O(n^2)    | InsertionSort        |     103 ms.
---------------------------------------------
O(n^2)    | SelectionSort        |     676 ms.
---------------------------------------------
O(n^2)    | BubbleSort           |    1313 ms.
---------------------------------------------
O(?)      | OptimizedMergeSort   |      41 ms.
---------------------------------------------
O(nlog(n))| MergeSort            |      14 ms.
---------------------------------------------

为什么输出与第一次运行不同？ OptimizedMergeSort 比普通 MergeSort 花费的时间更长...

如果我取消注释 for (int x=1; x<6; x++) SortingDemo 中的行，(使用相同的数组运行测试 5 次)我得到:

Sorting   20000 elements
=============================================
O(n^2)    | InsertionSort        |     101 ms.
---------------------------------------------
O(n^2)    | SelectionSort        |     668 ms.
---------------------------------------------
O(n^2)    | BubbleSort           |    1311 ms.
---------------------------------------------
O(?)      | OptimizedMergeSort   |      37 ms.
---------------------------------------------
O(nlog(n))| MergeSort            |      10 ms.
---------------------------------------------

Sorting   20000 elements
=============================================
O(n^2)    | InsertionSort        |      94 ms.
---------------------------------------------
O(n^2)    | SelectionSort        |     665 ms.
---------------------------------------------
O(n^2)    | BubbleSort           |    1308 ms.
---------------------------------------------
O(?)      | OptimizedMergeSort   |       5 ms.
---------------------------------------------
O(nlog(n))| MergeSort            |       7 ms.
---------------------------------------------

Sorting   20000 elements
=============================================
O(n^2)    | InsertionSort        |     116 ms.
---------------------------------------------
O(n^2)    | SelectionSort        |     318 ms.
---------------------------------------------
O(n^2)    | BubbleSort           |     969 ms.
---------------------------------------------
O(?)      | OptimizedMergeSort   |       5 ms.
---------------------------------------------
O(nlog(n))| MergeSort            |      10 ms.
---------------------------------------------

Sorting   20000 elements
=============================================
O(n^2)    | InsertionSort        |     116 ms.
---------------------------------------------
O(n^2)    | SelectionSort        |     319 ms.
---------------------------------------------
O(n^2)    | BubbleSort           |     964 ms.
---------------------------------------------
O(?)      | OptimizedMergeSort   |       5 ms.
---------------------------------------------
O(nlog(n))| MergeSort            |       5 ms.
---------------------------------------------

Sorting   20000 elements
=============================================
O(n^2)    | InsertionSort        |     116 ms.
---------------------------------------------
O(n^2)    | SelectionSort        |     320 ms.
---------------------------------------------
O(n^2)    | BubbleSort           |     963 ms.
---------------------------------------------
O(?)      | OptimizedMergeSort   |       4 ms.
---------------------------------------------
O(nlog(n))| MergeSort            |       6 ms.
---------------------------------------------

对于其他排序，结果看起来合理。但是对于 mergeSort，为什么第一次运行比后来运行的时间长得多？ OptimizedMergeSort 为 37 毫秒:4 毫秒。

我认为即使 Optimized/MergeSort 的实现是错误的，输出应该保持不变，为什么有时相同的方法调用花费的时间更长，有时时间更短？

作为信息，所有这些 *Sort 类都扩展了一个超抽象类 Sorting。它有一个抽象方法 void sort(int[] data)

MergeSort 有 mergeSorting方法和 merge() 方法。OptimizedMergeSort 扩展了 MergeSort，并覆盖了 mergeSorting()方法，(因为当数组大小 <= 7 时，它将执行插入排序)并重用 merge()方法来自 MergeSort类。

感谢您阅读这么长的文本和代码。如果你们能给我一些解释，我将不胜感激。

所有测试均在 linux 下的 Eclipse 中完成。

Answer 1

微基准测试 Java 代码是出了名的棘手。

即时编译器很可能会在某个时候启动，将您的 Java 字节码编译成 native 机器码。每次编译都需要时间，但生成的代码可能运行得更快。

还有其他陷阱，但我认为上述情况最有可能发生。

以下 SO 答案非常适合阅读:https://stackoverflow.com/a/513259/367273