收集器的运行时复杂度#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))

收集器的运行时复杂度#toList

Runtime complexity of Collectors#toList

java

time-complexity

java-stream

collectors