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视为CollectorImpl构造函数的第三个参数，它在线性时间内合并两个子结果。

这是否意味着，如果通过Stream#collect方法频繁使用该函数，我们可以获得平方计算时间？

考虑这段代码:

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

第二个流的元素恰好是按降序计算的。 Collect 方法可以做的最简单的事情就是将每个数字包装到 List 中，并将所有下一个数字添加到其中，总共具有平方复杂度，多么悲伤。

Answer 1

在这种情况下，输入 desc 列表将根据系统拥有的硬件线程数量分为几个独立的部分。通常在 4 核系统上它是 16 个部分(尽管没有指定并且可能会改变)。每个部分将使用累加器独立处理，然后使用组合器将结果合并在一起。所以它不会下降到二次复杂度，但是，是的，将会完成许多不必要的复制。

实际上使用toArray()方法效率更高。它检查流源特征，在您的情况下，它特别优化，因为源是 SIZED 和 SUBSIZED，因此结果可以写入单个数组，而无需任何额外的复制。如果您需要List，您可以考虑使用Arrays.asList(desc.parallelStream()....toArray(Integer[]::new))