当前位置: 首页 > 知识库问答 >
问题:

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

冯渝
2023-03-14

我在这里写了这两个方法来查找最小和最大值。#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步

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

共有1个答案

夏知
2023-03-14

好的,根据评论中的建议,我认为我做了一个更好的基准测试。我用的是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。

 类似资料:
  • 主要内容:普通算法,分治算法程序中,我们经常使用数组(列表)存储给定的线性序列(例如 {1,2,3,4}),那么如何查找数组(序列)中的最大值或者最小值呢? 查找数组(序列)中最大值或最小值的算法有很多,接下来我们以 {3,7,2,1} 序列为例讲解两种查找最值的算法,一种是普通算法,另一种是借助 分治算法解决。 普通算法 普通算法的解决思路是:创建两个变量 max 和 min 分别记录数组中的最大值和最小值,它们的初始值都

  • 问题内容: 我正在尝试创建两种方法,一种找到对象数组中的最小值,另一种找到对象数组中第二个最小值。 我已经这样写了两个 我已经找到了如何找到最小的值,我只需要找到第二个最小的值,我不确定怎么做。 有任何想法吗?谢谢! 问题答案: 像这样的东西:

  • 使用while循环,我必须执行以下操作: 使用变量“I”,计算输入的整数数量;使用变量“number”,表示输入的数字;使用变量“min”,表示迄今为止输入的最小数字;使用变量“max”,表示迄今为止输入的最大数字 用户将总共输入5个整数。 这是我的代码: 当我运行这个时,“I”、“number”和“maximum”变量似乎都能正常工作。但是,“minimum”变量要记住,“minimum”的设置

  • 给定一个非负整数数组,设计最简单的算法来找到最大大小的子数组,并将其加到最小的值。 我的想法是,因为它们是非负整数,所以和最小的数组总是单个单元数组,只有原始数组的最小值。如果我理解正确的话,它取决于什么具有更高的优先级,具有更高的长度或更小的值。然而,这个问题从来没有明确说明哪一个优先。 我在这个问题上是正确的,还是我遗漏了什么?

  • 问题内容: 我有一个类似于下面的多维数组。我试图实现的是一种从数组中查找和获取“ Total”值最高的数组的方法,现在我知道有一个称为的函数,但不适用于像这样的多维数组。 我想做的是创建一个foreach循环并仅使用总数构建一个新数组,然后使用它来找到最大值,这将起作用,唯一的问题是检索与此相关的其余数据最大值。我不确定这也是最有效的方法。 有任何想法吗? 问题答案: 从PHP 5.5开始,您可以

  • 问题内容: 我正在寻找一种非常快速,干净且有效的方法来获取以下JSON切片中的最大“ y”值: for-loop是解决此问题的唯一方法吗?我热衷于使用。 问题答案: 要在中找到对象的最大值: