Stream.sorted() then collect, or collect then List.sort()?

user_3141234 0
Viewed 1979

In general, is there a performance difference between these two pieces of code? 

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

Variant 2 is obviously yucky and should be avoided, but I'm curious if there are any performance optimizations built into the mainstream (heh, mainstream) implementations of Stream that would result in a performance difference between these two.

I imagine that because the stream has strictly more information about the situation, it would have a better opportunity to optimize. E.g. I imagine if this had a findFirst() call tacked on, it would elide the sort, in favor of a min operation.

collectors java-stream list sorting java
5 Answers

Both options should result in the same final result. But runtime characteristics could be different. What if the initial stream is a parallel one? Then option 1 would do a sort in parallel, whereas option 2 wouldn't do a "sequential" sort. The result should be the same, but the overall runtime resp. CPU load could be very much different then.

I would definitely prefer option 1 over 2: why create a list first, to then later sort it?!

Imagine for example you later want to collect into an immutable list. Then all code that follows your second pattern would break. Whereas code written using pattern 1 wouldn't be affected at all!

Of course, in the example here that shouldn't lead to issues, but what if the sort() happens in a slightly different place?!

user_15311240

Conceptually, streams are usually looked at as "transient" data that's being processed/manipulated, and collecting the stream conveys the notion you're done manipulating it.

While the second snippet should work, the first one would be the more idiomatic way of doing things.

user_24227760

In the first case the sorting happens in the call to collect. If the stream is already sorted this will be a no-op (the data will just pass through as-is). Might not make a big difference, but calling Collections.sort on an already sorted collection is still O(n).

Also the first case benefits from parallel execution, as at least OpenJDK uses Arrays.parallelSort.

Apart from that the first line is cleaner, better to understand and less error prone when refactoring.

user_91991670

According to documentation, it seems that the first sort is not a stable sort implementation for the unordered streams:

For ordered streams, the sort is stable. For unordered streams, no stability guarantees are made.

but the second one is a stable sort implementation:

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons.

So, the stability of the sort algorithm is one of the differences between these two lists sort methods.

user_21373780

The list you get back from Collectors.toList() is not guaranteed to be editable. It might be an ArrayList, or an ImmutableList, you cannot know. Therefore you must not try to modify that list.

user_2257570
Related