java - Collectors#toList のランタイムの複雑さ

Question

Java ライブラリのソース コードでは、Collectors#toListメソッドは次のように定義されています。

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);
}

BinaryOperatorのコンストラクターの3 番目のパラメーターとしてCollectorImpl、線形時間で 2 つのサブ結果をマージします。

この関数をメソッドで頻繁に使用する場合、Stream#collect2 乗の計算時間を得ることができるということですか?

次のコードを検討してください。

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());

2 番目のストリームの要素はたまたま降順で計算されました。collect メソッドでできる最も簡単な方法は、各数値をラップしてList次のすべての数値を追加することです。合計で 2 乗の複雑さがあります。悲しいことです。