代码之家 › 专栏 › 技术社区 › Alexander

Stream.sorted()然后collect,还是collect然后List.sort()[[副本]

collectors java-stream sorting list java

7

Alexander · 技术社区 · 7 年前

一般来说,这两段代码之间是否存在性能差异?

List<Integer> list1 = someStream1.sorted().collect(toList());
// vs.
List<Integer> list2 = someStream2.collect(toList());
list2.sort(Comparator.naturalOrder())

变体2显然很恶心,应该避免使用,但我很好奇是否有任何性能优化内置到主流(heh,main)中流动 )流的实现,这将导致这两者之间的性能差异。

我想,因为流有更多关于情况的信息,所以它将有更好的机会进行优化。我想如果这有一个 findFirst() 打电话的时候,会省掉那种人,有利于 min 操作。

5 回复 | 直到 7 年前

1

4

GhostCat 7 年前

两个选项的最终结果应该相同。但是运行时特性能够与众不同。如果初始流是

我肯定更喜欢选项1而不是2:为什么要先创建一个列表,然后呢后来整理一下?!

想象一下,例如,您以后想要收集到 不变的

当然,在这里的示例中,这不应该导致问题,但是如果sort()发生在稍微不同的地方呢?!

2

3

Mureinik 7 年前

虽然第二个片段应该有用,但第一个片段将是更惯用的做事方式。

3

Max Vollmer 7 年前

在第一种情况下,排序发生在对 collect . 如果流已经被排序,这将是一个不操作(数据只会按原样通过)。可能没什么区别,但打电话 Collections.sort 在已经排序的集合上仍然是O(n)。

第一种情况也得益于并行执行,至少 OpenJDK 使用 Arrays.parallelSort .

4

1

Roland Illig 7 年前

你得到的名单 Collectors.toList() 不保证可编辑。它可以是一个数组列表,还是一个不可变的列表,你不可能知道。因此,您不能试图修改该列表。

5

1

Amin Heydari Alashti 7 年前

根据文档,对于无序流,第一种排序似乎不是一种稳定的排序实现:

但第二个是稳定的排序实现:

这种实现是一种稳定的、自适应的、迭代的mergesort,当输入数组部分排序时,它需要的比较远远少于n lg(n),而当输入数组随机排序时,它提供了传统mergesort的性能。如果输入数组几乎已排序,则实现需要大约n个比较。

因此,排序算法的稳定性是这两种列表排序方法的区别之一。