4

在 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并将所有下一个数字添加到其中，总复杂度为平方，多么可悲。

4

1 回答 1

4

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

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

于 2015-11-23T02:03:20.127 回答