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

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

Collection items = ...; Comparator itemComparator = ...; 

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

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

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

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

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

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

我不相信自己实现了一个完美的基准，并且研究SortedOps并没有真正启发我。

Answer 1

可以肯定地说，即使不查看代码，两种排序forms也会具有相同的复杂性。 （如果他们没有，那么一个表格会被严重破坏！）

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

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

• 否则， ArrayList用于收集要排序的元素。

如果使用ArrayList ，则会产生构建/增长列表的额外开销。

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

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

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

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

在这个版本中，正如我们在上面看到的，与sorted()相关联的代码构建和排序数组（相当于上面发生的事情），或者它以缓慢的方式构建ArrayList 。 但除此之外，还有从items到收集器的数据流的开销。

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

如果您真的在意，您应该能够编写一个基准测试来测试Java的特定实现和特定输入数据集的实际差异。 （或者适应@Eugene的基准！）

Answer 2

说实话，我不太相信自己在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 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 testCollection(StringInput si){ Collections.sort(si.list, Comparator.naturalOrder()); return si.list; } @Fork(1) @Benchmark public List 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 3

以下是我的基准（不确定它是否正确）：

 import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Set; import java.util.TreeSet; import java.util.concurrent.TimeUnit; import java.util.stream.Collectors; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.OperationsPerInvocation; import org.openjdk.jmh.annotations.OutputTimeUnit; @OutputTimeUnit(TimeUnit.NANOSECONDS) @BenchmarkMode(Mode.AverageTime) @OperationsPerInvocation(MyBenchmark.N) public class MyBenchmark { public static final int N = 50; public static final int SIZE = 100000; static List sourceList = new ArrayList<>(); static { System.out.println("Generating the list"); for (int i = 0; i < SIZE; i++) { sourceList.add(i); } System.out.println("Shuffling the list."); Collections.shuffle(sourceList); } @Benchmark public List sortingList() { List sortedList = new ArrayList<>(sourceList); Collections.sort(sortedList); return sortedList; } @Benchmark public List sortedStream() { List sortedList = sourceList.stream().sorted().collect(Collectors.toList()); return sortedList; } @Benchmark public List treeSet() { Set sortedSet = new TreeSet<>(sourceList); List sortedList = new ArrayList<>(sortedSet); return sortedList; } } 

结果：

 Benchmark Mode Cnt Score Error Units MyBenchmark.sortedStream avgt 200 300691.436 ± 15894.717 ns/op MyBenchmark.sortingList avgt 200 262704.939 ± 5073.915 ns/op MyBenchmark.treeSet avgt 200 856577.553 ± 49296.565 ns/op 

与@ Eugene的基准测试一样，排序列表比排序流略快（约20％）。 令我感到treeSet是， treeSet明显变慢了。 我没想到的是。