java - 在整数数组中查找最小最大值，性能问题

Question

我在这里写了这两个方法来求最小值和最大值。 #2 基于这篇文章的回答 here .

private static Pair classicMinMax(int[] elements) {
    int min = MAX_VALUE;
    int max = MIN_VALUE;

    for (int i = 0; i < elements.length; i++) {
        int e = elements[i];
        if (e < min) min = e;
        if (e > max) max = e;
    }
    return new Pair(min, max);

}

private static Pair divideAndConquer(int[] elements) {
    int min = MAX_VALUE;
    int max = MIN_VALUE;

    for (int i = 0; i < elements.length - 1; i += 2) {
        int a = elements[i];
        int b = elements[i + 1];

        if (a > b) {
            if (b < min) min = b;
            if (a > max) max = a;
        } else {
            if (a < min) min = a;
            if (b > max) max = b;
        }
    }

    if (elements.length % 2 != 0) {
        int lastElement = elements[elements.length - 1];
        if (lastElement < min) min = lastElement;
        if (lastElement > max) max = lastElement;
    }
    return new Pair(min, max);
}

如果我像这样运行简单的基准测试:

@Test
public void timingsBoth() throws Exception {

    int size = 1000;

    for (int i = 1000; i < 10_000; i += 1000) {
        int arraySize = size * i;
        System.out.println("step is " + arraySize);

        List<Integer> list = new ArrayList<>(arraySize);
        int[] elements = new int[arraySize];
        for (int k = 0; k < arraySize; k++) {
            list.add(k);
        }

        Collections.shuffle(list);
        Integer[] integers = list.toArray(new Integer[0]);
        for (int k = 0; k < arraySize; k++) {
            elements[k] = integers[k];
        }

        long start = currentTimeMillis();
        classicMinMax(elements);
        long stop = currentTimeMillis();
        long result = stop - start;
        System.out.println("classic is " + result);

        start = currentTimeMillis();
        divideAndConquer(elements);
        stop = currentTimeMillis();
        result = stop - start;
        System.out.println("divideAndConquer is " + result);
    }
}

我通常会得到这样的结果:

步骤是 1000000 经典是8 分而治之是 11 步骤是 2000000 经典是2 分而治之是5 步骤是 3000000 经典是11 分而治之是 17 步骤是 4000000 经典是5 分而治之是 10 步骤是 5000000 经典是4 分而治之是 16 步骤是 6000000 经典是6 分而治之是14 步骤是 7000000 经典是6 分而治之是18 步骤是 8000000 经典是8 分而治之是 20 步骤是 9000000 经典是8 分而治之是24

我的算法有误吗？我期待至少类似的结果。

Answer 1

好的，根据评论中的建议，我认为我做了一个更好的基准测试。 我用的是Java Microbenchmark Harness .我以前从未使用过它，所以我的测试基于这个方便的 tutorial .

我所做的是创建一个 JMH 测试，如下所示:

public class MinMaxBenchmark {

    @State(Scope.Benchmark)
    public static class MyState {

        int arraySize = 50_0000;
        int[] elements = new int[arraySize];

        @Setup(Level.Trial)
        public void doSetup() {
            List<Integer> list = new ArrayList<>(arraySize);
            for (int k = 0; k < arraySize; k++) {
                list.add(k);
            }
            Collections.sort(list);
            Integer[] integers = list.toArray(new Integer[0]);
            for (int k = 0; k < arraySize; k++) {
                elements[k] = integers[k];
            }

        }
    }


    @Benchmark @BenchmarkMode(Mode.SampleTime   ) @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Pair classic(MyState state) {
        return classicMinMax(state.elements);
    }
    @Benchmark @BenchmarkMode(Mode.SampleTime) @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Pair divide(MyState state) {
        return divideAndConquer(state.elements);
    }

}

我特别注意在基准测试之外创建数组(输入数据)，创建一个 @State 和一个用于初始化的 @Setup 方法。比我写到 @Benchmark 方法。我在返回结果时非常小心，因此可以避免死代码(都在教程中)。

使用此设置，我进行了多次试验。这是最后一次尝试:

基准模式 Cnt 分数误差单位 MinMaxBenchmark.classic 样本 994028 0.202 ± 0.001 ms/op MinMaxBenchmark.classic:经典·p0.00 样本 0.153 ms/op MinMaxBenchmark.classic:经典·p0.50 样本 0.180 ms/op MinMaxBenchmark.classic:经典·p0.90 样本 0.259 ms/op MinMaxBenchmark.classic:经典·p0.95 样本 0.311 毫秒/操作 MinMaxBenchmark.classic:经典·p0.99 样本 0.409 毫秒/操作 MinMaxBenchmark.classic:经典·p0.999 样本 0.567 毫秒/操作 MinMaxBenchmark.classic:经典·p0.9999 样本 0.942 ms/op MinMaxBenchmark.classic:classic·p1.00 样本 2.617 毫秒/操作 MinMaxBenchmark.divide 样本 1226029 0.164 ± 0.001 ms/op MinMaxBenchmark.divide:divide·p0.00 样本 0.126 ms/op MinMaxBenchmark.divide:divide·p0.50 样本 0.149 ms/op MinMaxBenchmark.divide:divide·p0.90 样本 0.201 ms/op MinMaxBenchmark.divide:divide·p0.95 样本 0.230 ms/op MinMaxBenchmark.divide:divide·p0.99 样本 0.327 ms/op MinMaxBenchmark.divide:divide·p0.999 样本 0.522 ms/op MinMaxBenchmark.divide:divide·p0.9999 样本 0.945 ms/op MinMaxBenchmark.divide:divide·p1.00 样本 3.199 ms/op

实际上 divide 只在 p1.00 上失败(我需要找到含义)。

所以我猜这是我处理基准测试的方式的问题。

感谢您在评论中的帮助，尤其是@alfasin。