5

我写了一些 java 类来评估/演示不同的排序算法。但是，当我运行我的演示课时，我感到很困惑。希望大家能给我一个解释。（这个问题不是作业。）

首先，我将列出一些与此问题相关的代码。

抽象演示 

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;
    }

你可以看到，我生成了一个包含 20000 个元素的 int 数组。因为我在 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 中取消注释该行，（使用相同的 Array 运行测试 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。

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

所有测试都是在 Eclipse 下的 linux 下完成的。

4

3 回答 3

4

众所周知，对 Java 代码进行微基准测试非常棘手。

Just-in-Time 编译器很可能会在某个时候开始将您的 Java 字节码编译为本机机器码。每次编译都需要时间，但生成的代码可能会运行得更快。

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

以下 SO 答案非常好读：https ://stackoverflow.com/a/513259/367273

于 2011-12-03T17:28:11.260 回答
1

基本上，有两个可能的原因，都与环境而不是您的程序有关：其他东西占用了大量空间，或者其他东西占用了大量 CPU 时间。

在第一种情况下，您有一些其他程序消耗物理内存，导致您的程序更频繁地进行分页和/或垃圾收集。

其次，其他一些程序（如果你运行的是 Mac，我敢打赌 Time Machine）会间歇性地运行消耗 CPU。

无论如何，您能找到的方法是开始使用 Java 附带的工具。jconsole 和 VirtualVM 是很好的选择。

一般来说，当您遇到性能问题时，需要采取三个关键步骤：measure、measure和 MEASURE。

更新

我同意 JIT 可以有所作为，但我得到的印象是这些是单独的运行；您每次都在调用一个新的 JVM。这最大限度地减少了 JIT 的影响。

于 2011-12-03T17:24:34.747 回答
0

为了减少 JIT 的影响，您可以放弃每次测试的最初几次运行。此外，为了获得更准确的结果，平均运行 100 或 1000 次以上。

您还可以在开始测量之前执行 System.gc() 和 Thread.yeild()。如果您只想测试少数迭代，则更喜欢 system.nanoTime() 并且不要使用 system.currentTimeMillis （它不够准确）。

于 2011-12-03T17:52:23.963 回答