java - 查找数组中的最小值和最大值

Question

这是一个非常基本的算法(再简单不过了)，但我被难住了。我们有一个元素数组，我们必须确定最小值和最大值。

通常的方法是遍历数组并找到 min 和 max，这是 2n 比较。

稍微更有效的方法是首先成对比较数组的连续元素以确定任意两个元素的最大值和最小值(n/2 比较)。我们现在有 n/2 min 和 n/2 max 元素。现在我们可以在 n/2 + n/2 + n/2(上一步)= 3/2* n 或 1.5n 比较中得到最终的最大值和最小值

没关系。从理论上讲，代码在第二种情况下运行的时间应该更少，因为我们进行的比较更少。但是当我运行代码时，结果却不同。

我的代码片段如下:

public class MinMax {
public static void nonEfficient(int [] array){
    int min=array[0],max=array[0];
    for (int anArray : array) {
        if (anArray < min)
            min = anArray;
        else {
            if (anArray > max)
                max = anArray;
        }
    }
    System.out.println("Max is :" + max);
    System.out.println("Min is :" + min);
}
public static void efficient(int [] arr,int length){
    int max,min;
    max = min = arr[0];
    int i = 0;
    for (; i < length / 2; i++)
    {
        int number1 = arr[i * 2];
        int number2 = arr[i * 2 + 1];
        if (arr[i * 2] >= arr[i * 2 + 1])
        {
            if (number1 > max)
                max = number1;
            if (number2 < min)
                min = number2;
        }
        else
        {
            if (number2 > max)
                max = number2;
            if (number1 < min)
                min = number1;
        }
    }
    if (i * 2 < length)
    {
        int num = arr[i * 2];
        if (num > max)
            max = num;
        if (num < min)
            min = num;
    }
    System.out.println("***********************");
    System.out.println("Max is :" + max);
    System.out.println("Min is :" + min);
}
public static void main(String[] args) {
    int [] array =  new int[10000000];
    Random rand = new Random();
    for(int i=0;i<array.length;i++)
        array[i] = rand.nextInt(100000)-144;
    long startTime = System.currentTimeMillis();
    nonEfficient(array); //theoretically non efficient 2n compares
    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println(elapsedTime);// just 11ms

    startTime = System.currentTimeMillis();
    efficient(array, 10000000);///theoretically more efficient 1.5n compares
    stopTime = System.currentTimeMillis();
    elapsedTime = stopTime - startTime;
    System.out.println(elapsedTime);//whooping 37 ms..what happpened ????
}
}

谁能帮我弄清楚我做错了什么。有什么非常明显的东西是我想念的吗。

感谢您的帮助。

Answer 1

首先:基准测试完全有缺陷。您测量的时间跨度太短，没有任何 JIT 预热，您在测量中包括了 System.out.println 的时间。通过应用“通常的”微基准测试模式，它可以稍微更有意义(参见本答案的末尾)

但即使使用这个“基准”，也存在显着差异。这有很多可能的原因:

可以假设现代 CPU 上的单次比较需要(摊销)一个 CPU 周期。单个 CPU 周期是光束传播 10 厘米 所需的持续时间。现在，衡量一下 ;-) 基本上，您的算法中的每个 其他操作将至少花费相同的时间，或更长的时间:每个 i++ 将花费相同的时间，每个 min=x 将花费相同的时间或更长的时间，每个 i*2 很可能需要更长的时间...

此外，我认为这里最重要的一点是:CPU 很快，但内存很慢。在(不)“效率不高”的情况下，您正在按顺序运行数组。这非常适合缓存。每次读取一个缓存行都会被充分利用。与此相反，在(不)“高效”的情况下，您的内存访问基本上分散在整个数组中。它将不得不从主内存中读取数据 block 到缓存中，并且大部分数据将不得不被丢弃，因为它不会立即使用，但会在下一次读取时再次读取。

---

关于基准测试:通过多次重复相应的方法并取平均时间，并随着数组大小的增加重复执行此操作，可以使它稍微更有意义 - 大致 像这样:

public static void main(String[] args)
{
    Random rand = new Random();
    long beforeNS = 0;
    long afterNS = 0;
    int results[] = { 0, 0 };
    int runs = 100;
    for (int size=10000; size<=10000000; size*=2)
    {
        int[] array = new int[size];
        for (int i = 0; i < array.length; i++)
            array[i] = rand.nextInt(size) - 144;

        beforeNS = System.nanoTime();
        for (int i=0; i<runs; i++)
        {
            nonEfficient(array, results);
        }
        afterNS = System.nanoTime();
        System.out.println(
            "Not efficient, size "+size+
            " duration "+(afterNS-beforeNS)/1e6+
            ", results "+Arrays.toString(results));

        beforeNS = System.nanoTime();
        for (int i=0; i<runs; i++)
        {
            efficient(array, array.length, results);
        }
        afterNS = System.nanoTime();
        System.out.println(
            "Efficient    , size "+size+
            " duration "+(afterNS-beforeNS)/1e6+
            ", results "+Arrays.toString(results));
    }
}

尽管如此，结果可能会受到质疑，只要 VM 选项未知等等。但它至少给出了一个略微更可靠的指示，表明两者之间是否存在“显着”差异方法。