Java Complexity, Collectors.toList ()

Question

In java sources, Collectors.toList is defined as

public static <T> Collector<T, ?, List<T>> toList() { return new CollectorImpl<>((Supplier<List<T>>) ArrayList::new, List::add, (left, right) -> { left.addAll(right); return left; }, CH_ID); } 

We see BinaryOperator as the third design parameter of CollectorImpl, which combines two subselects in linear time. Does this mean that in the case of frequent use of this function by the Stream.collect method, we can get the square calculation time?

Consider this code:

 List<Integer> desc = Stream.iterate(n, k -> k - 1).limit(n + 1) .collect(Collectors.toList()); desc.parallelStream() .map(k -> { try { Thread.sleep(k * 500); } catch (InterruptedException ignored) { } return k; }) .collect(Collectors.toList()); 

Elements of the second stream were calculated in descending order. The easiest way a collection method can do is to count the number of each number, which transfers it to the list and adds all subsequent numbers to it with total complexity, how sad it is.

Answer 1

In this case, the desc input list will be divided into several independent parts, depending on the number of hardware threads in your system. Usually this is 16 parts per 4-core system (although it is not specified and may change). Each part will be processed independently using a battery, then the results will be combined together using a combiner. Thus, it will not fall to quadratic complexity, but yes, a lot of unnecessary copying will be performed.

Actually, it is much more efficient to use the toArray() method. It checks the characteristics of the stream source, and in your case it is especially optimized, since the source is SIZED and SUBSIZED, so the result can be written to a single array without any additional copying. If you need a List , you can use Arrays.asList(desc.parallelStream()....toArray(Integer[]::new))