什么更有效:排序流或排序列表？

Question

假设我们在集合中有一些项目,我们想要使用某个比较器对它们进行排序,期望列表中的结果:

Collection<Item> items = ...;
Comparator<Item> itemComparator = ...;

其中一种方法是对列表中的项进行排序,例如:

List<Item> sortedItems = new ArrayList<>(items);
Collections.sort(sortedItems, itemComparator);

另一种方法是使用排序流:

List<Item> sortedItems = items
    .stream()
    .sorted(itemComparator)
    .collect(Collectors.toList());

我想知道,哪种方法更有效率？排序流是否有任何优点(如多核上的紧固排序)？

从运行时复杂性/速度的角度来看,效率很高.

我不相信自己能够实现一个完美的基准,学习SortedOps并没有真正启发我.

Answer 1

说实话,我不相信自己太多无论是在JMH(除非我理解的组装,这需要大量的时间在我的情况),尤其是因为我曾经使用过@Setup(Level.Invocation),但这里是一个小的测试(我把StringInput代一些我做的其他测试,但它应该没关系,它只是一些数据要排序)

@State(Scope.Thread)
public static class StringInput {

    private String[] letters = { "q", "a", "z", "w", "s", "x", "e", "d", "c", "r", "f", "v", "t", "g", "b",
            "y", "h", "n", "u", "j", "m", "i", "k", "o", "l", "p" };

    public String s = "";

    public List<String> list;

    @Param(value = { "1000", "10000", "100000" })
    int next;

    @TearDown(Level.Invocation)
    public void tearDown() {
        s = null;
    }

    @Setup(Level.Invocation)
    public void setUp() {

         list = ThreadLocalRandom.current()
                .ints(next, 0, letters.length)
                .mapToObj(x -> letters[x])
                .map(x -> Character.toString((char) x.intValue()))
                .collect(Collectors.toList());

    }
}


@Fork(1)
@Benchmark
public List<String> testCollection(StringInput si){
    Collections.sort(si.list, Comparator.naturalOrder());
    return si.list;
}

@Fork(1)
@Benchmark
public List<String> testStream(StringInput si){
    return si.list.stream()
            .sorted(Comparator.naturalOrder())
            .collect(Collectors.toList());
}

结果显示Collections.sort速度更快,但幅度不大:

Benchmark                                 (next)  Mode  Cnt   Score   Error  Units
streamvsLoop.StreamVsLoop.testCollection    1000  avgt    2   0.038          ms/op
streamvsLoop.StreamVsLoop.testCollection   10000  avgt    2   0.599          ms/op
streamvsLoop.StreamVsLoop.testCollection  100000  avgt    2  12.488          ms/op
streamvsLoop.StreamVsLoop.testStream        1000  avgt    2   0.048          ms/op
streamvsLoop.StreamVsLoop.testStream       10000  avgt    2   0.808          ms/op
streamvsLoop.StreamVsLoop.testStream      100000  avgt    2  15.652          ms/op

Answer 2

可以肯定地说,即使不查看代码,两种排序形式也会具有相同的复杂性.(如果他们没有,那么一个表格会被严重破坏!)

查看流的Java 8源代码(特别是内部类java.util.stream.SortedOps),该sorted()方法将一个组件添加到流管道中,该流管道将所有流元素捕获到一个数组或一个数组中ArrayList.

• 当且仅当管道汇编代码可以提前推断出流中的元素数量时,才使用数组.

• 否则,a ArrayList用于收集要排序的元素.

如果ArrayList使用了a,则会产生构建/增长列表的额外开销.

然后我们返回两个版本的代码:

List<Item> sortedItems = new ArrayList<>(items);
Collections.sort(sortedItems, itemComparator);

在此版本中,ArrayList构造函数将元素复制items到适当大小的数组,然后Collections.sort执行该数组的就地排序.(这发生在封面下).

List<Item> sortedItems = items
    .stream()
    .sorted(itemComparator)
    .collect(Collectors.toList());

在这个版本中,正如我们在上面看到的那样,与sorted()构建和排序数组相关联的代码(相当于上面发生的情况)或者构建ArrayList缓慢的方式.但最重要的是,有来自items收集器的数据流的开销.

总体而言(至少使用Java 8实现)代码检查告诉我,第一个版本的代码不能慢于第二个版本,并且在大多数(如果不是全部)情况下它会更快.但随着列表变大,O(NlogN)排序将主导O(N)复制的开销.这意味着两个版本之间的相对差异会变小.

如果您真的在意,您应该能够编写一个基准测试来测试Java的特定实现和特定输入数据集的实际差异.(或者适应@Eugene的基准!)