java - 为什么 ArrayList 的排序方法比 Java 中的 Arrays 快？

Question

以下代码的目标是对 300,000 个 int 数字进行排序。我发现 ArrayList 的 sort() 的持续时间小于 Arrays 的 sort()。在内部，他们使用相同的算法进行排序。 ArrayList 使用 Arrays 的 sort() 对其元素数据进行排序。

public class EasySort {
    public static void main(String args[]) {
        // Read data from file, number split by ","
        FileReader fr = null;
        try {
            fr = new FileReader("testdata2.txt");
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        BufferedReader  bufferedReader=new BufferedReader(fr);
        String line=null;
        try {
            line=bufferedReader.readLine();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        // use split method to generate a String array to save numbers
        String[] strArray=line.split(",");

        //Convert string array to ArrayList<Integer>
        ArrayList<Integer> integerList=new ArrayList<>();
        for(String str:strArray){
            integerList.add(Integer.parseInt(str));
        }

        //Sort by ArrayList
        long t0=System.currentTimeMillis();
        integerList.sort(((p1,p2)->(p1.intValue()<p2.intValue()?-1:p1.intValue()>p2.intValue()?1:0)));
        long t1=System.currentTimeMillis();
        System.out.println("ArrayList Sort duration:"+(t1-t0));

        //Convert string array to Integer array
        Integer[] integerArray=new Integer[strArray.length];
        int i=0;
        for(String str:strArray){
            integerArray[i++]=Integer.parseInt(str);
        }

        //Sort by Arrays
        t0=System.currentTimeMillis();
        Arrays.sort(integerArray, ((p1,p2)->(p1.intValue()<p2.intValue()?-1:p1.intValue()>p2.intValue()?1:0)));
        t1=System.currentTimeMillis();
        System.out.println("Arrays duration:"+(t1-t0));
    }
}

结果如下:
ArrayList 排序时长:211
阵列持续时间:435

我查看了ArrayList的源代码。它在自己的排序方法中使用 Arrays.sort() 。

 @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

因此，在我看来，我的代码应该显示相同的持续时间。但是我试了很多次，结果都差不多。发生了什么事？

Java 版本:8
操作系统:Windows 7

Answer 1

这是一个热身问题 - 但具体原因我不知道。

使用这段代码:

public void test() {
    Integer[] a = randomData(10000000);

    ArrayList<Integer> integerList = new ArrayList<>();
    for (Integer i : a) {
        integerList.add(i);
    }

    long t0, t1;
    //Sort by ArrayList
    t0 = System.currentTimeMillis();
    integerList.sort(((p1, p2) -> (p1.intValue() < p2.intValue() ? -1 : p1.intValue() > p2.intValue() ? 1 : 0)));
    t1 = System.currentTimeMillis();
    System.out.println("ArrayList duration:" + (t1 - t0));


    //Sort by Arrays
    Integer[] integerArray = Arrays.copyOf(a, a.length);
    t0 = System.currentTimeMillis();
    Arrays.sort(integerArray, ((p1, p2) -> (p1.intValue() < p2.intValue() ? -1 : p1.intValue() > p2.intValue() ? 1 : 0)));
    t1 = System.currentTimeMillis();
    System.out.println("Arrays duration:" + (t1 - t0));

}

Random r = new Random(System.currentTimeMillis());

private Integer[] randomData(int n) {
    Integer[] a = new Integer[n];
    for (int i = 0; i < n; i++) {
        a[i] = r.nextInt();
    }
    return a;
}

然后将这两种排序移动到不同的顺序，我得到:

Arrays duration:4209

ArrayList duration:4570

ArrayList duration:6776

Arrays duration:4684

因此，如果 ArrayList 先排序，则需要更长的时间。

所以@AndyTurner 的评论是正确的 - 请参阅 How do I write a correct micro-benchmark in Java?

Java 8 - Windows 10