为什么在Java中ArrayList的sort方法比Arrays的sort方法更快？

Question

以下代码的目标是对30万个整数进行排序。我发现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毫秒
Arrays排序时间：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

- David.Ren

---

可能是关于sort()的Collections和Arrays的重复问题。 - Kaustubh Khare

你使用的是哪个Java版本？ - OLIVER.KOO

List<Integer> 可以在没有比较器的情况下进行排序（Integer 已经实现了 Comparable）; 因此，integerList.sort(null) 就可以了。那么，是否需要创建 Integer [] integerArray？使用原始 int 数组；并使用 Arrays.sort(intArray)。你可能会看到不同的结果。 - prasad_

你尝试了多少次？我在我的机器上测试了ArrayList<Integer>和Integer[]，它们几乎是相同的时间。 - zhh

如何在Java中编写正确的微基准测试？ - Andy Turner

@prasad，我将我的问题从一个更大的项目中简化了出来。所以你可以考虑我有一种对象，这个对象包含可以排序的int字段。 - David.Ren

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;
}

分别将这两种类型的数组排序，结果如下:

数组排序用时：4209

ArrayList排序用时：4570

ArrayList排序用时：6776

数组排序用时：4684

因此，如果首先对ArrayList进行排序，时间会更长。

所以，@AndyTurner的评论是正确的-请参阅如何编写正确的Java微基准测试？

Java 8 - Windows 10

- OldCurmudgeon

---

如果只是热身，为什么ArrayList的数字在数组后面甚至更差？还有一个有趣的行为——如果你减小数组大小，无论在哪个位置，ArrayList排序都会更快。 - astafev.evgeny

JIT和其他Java优化技术使得正确设置微基准测试非常困难。 - Jerry Chin

Answer 2

他们应该是相同的，我不知道为什么你得到了不同的结果。以下是我的代码，时间几乎相同。对于 T[] 和 ArrayList<T> 都会调用 Arrays.sort(T[], ...)，然后使用归并排序或tim排序。

Random rand = new Random();
Integer[] array = new Integer[300000];
for (int i = 0; i < array.length; i++)
    array[i] = rand.nextInt(array.length);  
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(array));    

long a = System.currentTimeMillis();
Arrays.sort(array, 0 ,array.length);
long b = System.currentTimeMillis();
list.sort(null);
long c = System.currentTimeMillis();

System.out.println(b - a);
System.out.println(c - b);

- zhh

---

我已经运行了你的代码，b-a=446，c-d=91。我的Java版本是8。你的呢？ - David.Ren

@David.Ren 我的电压是220~240，我的Java版本是7。 - zhh

Answer 3

这是我尝试使用Java 8做的事情。请注意，数组包括int类型, Integer类型和List中的数据类型为Integer。此外，Integer数组使用Arrays.parallelSort()排序。

import java.util.*;
import java.util.stream.*;
public class TestingSorts {
    public static void main(String[] args) {
        long t0 = 0L;
        long t1 = 0L;
        // Run this procedure 10 times
        for (int i = 1; i < 11; i++) {
            // Create an int array and Integer List filled with random numbers
            int [] intArray = IntStream.generate(() -> new Random().nextInt())
                        .limit(300_000)
                        .toArray();
            Integer [] integerArray = IntStream.generate(() -> new Random().nextInt())
                        .limit(300_000)
                        .boxed()
                        .toArray(n -> new Integer[n]);
            Integer [] integerArrayP = IntStream.generate(() -> new Random().nextInt())
                        .limit(300_000)
                        .boxed()
                        .toArray(n -> new Integer[n]);
            List<Integer> intList = IntStream.generate(() -> new Random().nextInt())
                        .limit(300_000)
                        .boxed()
                        .collect(Collectors.toCollection(ArrayList::new));
            // Sort the List and the arrays
            t0 = System.currentTimeMillis();
            intList.sort(null);
            t1 = System.currentTimeMillis();
            System.out.println(i + ") ArrayList<Integer> sort duration: " + (t1 - t0));
            t0 = System.currentTimeMillis();
            Arrays.sort(integerArray, Comparator.naturalOrder());
            t1 = System.currentTimeMillis();
            System.out.println(i + ") Integer[ ] sort duration: " + (t1 - t0));
            t0 = System.currentTimeMillis();
            Arrays.parallelSort(integerArrayP, Comparator.naturalOrder());
            t1 = System.currentTimeMillis();
            System.out.println(i + ") Integer[ ] PARALLEL sort duration: " + (t1 - t0));
            t0 = System.currentTimeMillis();
            Arrays.sort(intArray);
            t1 = System.currentTimeMillis();
            System.out.println(i + ") int[ ] sort duration: " + (t1 - t0));
        }
    }
}

结果（在运行在CORE i3处理器上的Windows 7 64位操作系统上）：

1) ArrayList<Integer> sort duration: 200
1) Integer[ ] sort duration: 424
1) Integer[ ] PARALLEL sort duration: 414
1) int[ ] sort duration: 136
2) ArrayList<Integer> sort duration: 143
2) Integer[ ] sort duration: 101
2) Integer[ ] PARALLEL sort duration: 56
2) int[ ] sort duration: 33
3) ArrayList<Integer> sort duration: 124
3) Integer[ ] sort duration: 118
3) Integer[ ] PARALLEL sort duration: 96
3) int[ ] sort duration: 42
4) ArrayList<Integer> sort duration: 108
4) Integer[ ] sort duration: 102
4) Integer[ ] PARALLEL sort duration: 92
4) int[ ] sort duration: 57
5) ArrayList<Integer> sort duration: 142
5) Integer[ ] sort duration: 113
5) Integer[ ] PARALLEL sort duration: 118
5) int[ ] sort duration: 31
6) ArrayList<Integer> sort duration: 113
6) Integer[ ] sort duration: 103
6) Integer[ ] PARALLEL sort duration: 58
6) int[ ] sort duration: 32
7) ArrayList<Integer> sort duration: 115
7) Integer[ ] sort duration: 116
7) Integer[ ] PARALLEL sort duration: 57
7) int[ ] sort duration: 33
8) ArrayList<Integer> sort duration: 115
8) Integer[ ] sort duration: 115
8) Integer[ ] PARALLEL sort duration: 58
8) int[ ] sort duration: 31
9) ArrayList<Integer> sort duration: 114
9) Integer[ ] sort duration: 101
9) Integer[ ] PARALLEL sort duration: 52
9) int[ ] sort duration: 32
10) ArrayList<Integer> sort duration: 113
10) Integer[ ] sort duration: 114
10) Integer[ ] PARALLEL sort duration: 57
10) int[ ] sort duration: 32

编辑：添加了对Integer数组进行排序的功能。
编辑：添加了使用并行排序对Integer数组进行排序的功能。

- prasad_

---

我认为，我们需要确保所有的测量都基于相同的算法/方法。最后，intList.sort(null) 调用 ComparableTimSort.sort()，Arrays.sort(intArray) 调用 DualPivotQuicksort.sort()。 - David.Ren

List 可以使用并行流进行排序。对于数组，没有并行流选项，只有一个并行排序。 - prasad_