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

Question

我在这里写了这两个方法来查找最小和最大值。#2是基于这篇文章的这个答案。

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步，80万经典是8步，征服是20步，90万经典是8步，征服是24步

我把算法弄错了吗？我本以为至少会有类似的结果。

Answer 1

好的，根据评论中的建议，我认为我做了一个更好的基准测试。我用的是Java微基准线束。我以前从未使用过它，所以我基于这个方便的教程进行测试。

我做的是创建一个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);
    }

}

我特别注意在基准之外创建数组（输入数据），创建一个带有初始化方法的@Setup@State。比我写的@Benchmark方法。我在返回结果时非常小心，这样可以避免死代码（都在教程中）。

通过这种设置，我进行了几次试验。这是最后一次尝试：

基准模式Cnt评分错误单位MinMaxBenchmark。经典样本994028 0.202±0.001 ms/op MinMaxBenchmark。经典：经典·p0。00样本0.153 ms/op MinMaxBenchmark。经典：经典·p0。50个样本0.180 ms/op MinMaxBenchmark。经典：经典·p0。90个样本0.259 ms/op MinMaxBenchmark。经典：经典·p0。95样本0.311 ms/op MinMaxBenchmark。经典：经典·p0。99个样本0.409 ms/op MinMaxBenchmark。经典：经典·p0。999样本0.567 ms/op MinMaxBenchmark。经典：经典·p0。9999样本0.942 ms/op MinMaxBenchmark。经典：经典·p1。00样本2.617 ms/op MinMaxBenchmark。将样本1226029除以0.164±0.001 ms/op MinMaxBenchmark。除法：除法·p0。00样本0.126 ms/op MinMaxBenchmark。除法：除法·p0。50个样本0.149 ms/op MinMaxBenchmark。除法：除法·p0。90样本0.201 ms/op MinMaxBenchmark。除法：除法·p0。95样本0.230 ms/op MinMaxBenchmark。除法：除法·p0。99个样本0.327 ms/op MinMaxBenchmark。除法：除法·p0。999样本0.522 ms/op MinMaxBenchmark。除法：除法·p0。9999样本0.945 ms/op MinMaxBenchmark。除法：除法·p1。00样本3.199 ms/op

实际上，在p1.00上，分歧只消失了（我需要找到意义）。

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

谢谢你在评论中的帮助，尤其是@alFasin。