有什么更有效的方法：对流进行排序或对列表进行排序？

Question

假设我们在集合中有一些项目，并且我们想使用某些比较器对它们进行排序，并期望结果在列表中：

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

一种方法是对列表中的项目进行排序，例如：

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

Anothe方法正在使用排序流：

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

我想知道哪种方法更有效？排序流是否有任何优势（例如在多核上进行Faste排序）？

在运行时复杂性方面/最快方面是高效的。

我不相信自己要实现一个完美的基准，学习SortedOps并不能真正启发我。

Answer 1

可以肯定地说，两种形式的排序都将具有相同的复杂性……即使不看代码也是如此。（如果他们不这样做，那么一种形式将被严重破坏！）

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

• 当且仅当管道装配代码可以提前推断出流中元素的数量时，才使用数组。

• 否则，将ArrayList使用an 来收集要排序的元素。

如果ArrayList使用，则将产生构建/扩展列表的额外开销。

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

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)复制的开销。这意味着两个版本之间的
相对 差异将变小。

If you really care, you should be able to write a benchmark to test the actual
difference with a specific implementation of Java, and a specific input
dataset. (Or adapt @Eugene’s benchmark!)