java - 为什么插入排序在不同的实现中在时间上运行如此不同

Question

我正在对基于数组的不同长度实现的插入排序算法进行计时。

我知道插入排序的平均情况是 O(n^2)，所以我意识到当您尝试对大型数组进行排序时它会花费一些时间，但是为什么下面两个实现之间会有将近 6500 毫秒的差异包含 100,000 个条目的数组？

这是我的数组的设置，其中填充了 1 到 1 百万的随机整数

int[] oneHundredThousand = new int[100000];
Random r = new Random();//RANDOMIZER

for(int i = 0; i < oneHundredThousand.length; i++)
        oneHundredThousand[i] = r.nextInt(1000000) + 1; //1 - 1000000

这些是我运行用于测试的 2 种方法，它们使用插入排序

public static long insertionSort1(int[] intArray) {
    long startTime = System.currentTimeMillis();

    int n = intArray.length;
    for (int k = 1; k < n; k++) {         
        int cur = intArray[k];                
        int j = k;                          
        while (j > 0 && intArray[j-1] > cur) {  
            intArray[j] = intArray[j-1];              
            j--;                              
        }
        intArray[j] = cur;                      
    }

    long endTime = System.currentTimeMillis();
    long elapsedTime = endTime - startTime;
    return elapsedTime;
}

和

public static long insertionSort2(int[] input){
    long startTime = System.currentTimeMillis();
    int temp;
    for (int i = 1; i < input.length; i++) {
        for(int j = i ; j > 0 ; j--){
            if(input[j] < input[j-1]){
                temp = input[j];
                input[j] = input[j-1];
                input[j-1] = temp;
            }
        }
    }
    long endTime = System.currentTimeMillis();
    long elapsedTime = endTime - startTime;
    return elapsedTime;
}

现在像这样在 main 中调用这些方法(复制数组以便通过每个“排序”保留原始顺序)，我得到了注释结果，为什么会有如此大的不同？我不认为同一算法的不同实现效率应该低得多。

int[] copy100_1 = Arrays.copyOf(oneHundredThousand, oneHundredThousand.length);
int[] copy100_2 = Arrays.copyOf(oneHundredThousand, oneHundredThousand.length);

//816ms 
System.out.print(insertionSort1(copy100_1));
//7400ms
System.out.print(insertionSort2(copy100_2));

Answer 1

分析插入排序，发现最好的情况。执行时间是 O(n²)。让我们以您的第一个实现为例来了解原因。

public static long insertionSort1(int[] intArray) {
    long startTime = System.currentTimeMillis();

    int n = intArray.length;
    for (int k = 1; k < n; k++) {         
        int cur = intArray[k];                
        int j = k;

        while (j > 0 && intArray[j-1] > cur) { // This loop can break early due 
                                               // to intArray[j-1] > cur
            intArray[j] = intArray[j-1];              
            j--;                              
        }
        intArray[j] = cur;                      
    }

    long endTime = System.currentTimeMillis();
    long elapsedTime = endTime - startTime;
    return elapsedTime;
}

这意味着对于(部分)排序的数组，(这部分)的执行时间减少到 O(n)。

您的第二个实现缺少这样的提前中断条件。但是您可以非常简单地添加它:

public static void insertionSort2(int[] input) {
    int temp;
    for (int i = 1; i < input.length; i++) {
        for (int j = i; j > 0; j--) {
            if (input[j] < input[j - 1]) {
                temp = input[j];
                input[j] = input[j - 1];
                input[j - 1] = temp;
            } else {
                break; // this is the "early break" missing.
            }
        }
    }
}

我拍了@amanin's answer作为模板并重新实现所有三个版本。

package benchmark;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.TimeUnit;

@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 2, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 2, time = 5, timeUnit = TimeUnit.SECONDS)
@Fork(1)
public class Test {

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

        public static final Random rng = new Random();
        final int[] array;
        final int[] expected;

        public Input() {
            final Random r = new Random();
            this.array = new int[200_000];
            for (int i = 0; i < this.array.length; i++) {
                this.array[i] = i;
            }
            this.expected = Arrays.copyOf(this.array, this.array.length);

            // Fisher-Yates shuffle
            for (int i = this.array.length - 1; i > 0; --i) {
                int swap = Input.rng.nextInt(i);
                int tmp = this.array[swap];
                this.array[swap] = this.array[i];
                this.array[i] = tmp;
            }
        }
    }

    @Benchmark
    public void benchSort1(final Input in) {
        insertionSort1(in.array);
    }

    @Benchmark
    public void benchSort2(final Input in) {
        insertionSort2(in.array);
    }

    @Benchmark
    public void benchSort3(final Input in) {
        insertionSort3(in.array);
    }

    public static void insertionSort1(int[] intArray) {
        int n = intArray.length;
        for (int k = 1; k < n; k++) {
            int cur = intArray[k];
            int j = k;
            while (j > 0 && intArray[j - 1] > cur) {
                intArray[j] = intArray[j - 1];
                j--;
            }
            intArray[j] = cur;
        }
    }

    public static void insertionSort2(int[] input) {
        int temp;
        for (int i = 1; i < input.length; i++) {
            for (int j = i; j > 0; j--) {
                if (input[j] < input[j - 1]) {
                    temp = input[j];
                    input[j] = input[j - 1];
                    input[j - 1] = temp;
                }
            }
        }
    }

    public static void insertionSort3(int[] input) {
        int temp;
        for (int i = 1; i < input.length; i++) {
            for (int j = i; j > 0; j--) {
                if (input[j] < input[j - 1]) {
                    temp = input[j];
                    input[j] = input[j - 1];
                    input[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] arg) throws Exception {
        Options option = new OptionsBuilder().include(Test.class.getSimpleName()).build();
        new Runner(option).run();
    }
}

这些是最终结果，benchSort1 和 benchSort2 是您的原始版本，benchSort3 是“更正的”双 版本:

Benchmark        Mode  Cnt      Score   Error  Units
Test.benchSort1  avgt    2      0.307          ms/op
Test.benchSort2  avgt    2  15145.611          ms/op
Test.benchSort3  avgt    2      0.210          ms/op

如您所见，这两个版本现在在时间上非常接近。