Java，Collectors.toList（）复杂性 [英] Java, Collectors.toList() complexity

问题描述

在java源代码中，Collectors.toList定义为

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

我们将BinaryOperator视为CollectorImpl的构造函数的第三个参数，它将两个子结果合并为线性时间。
是否意味着，如果通过Stream.collect方法频繁使用此函数，我们可以获得平方计算时间？

We see BinaryOperator as third parameter of CollectorImpl's contructor, which merges two subresults in linear time. Does it mean, that in case of frequent usage of this function by Stream.collect method, we can gain square computation time?

请考虑以下代码：

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

第二个流的元素恰好按降序计算。收集方法最简单的方法是将每个数字包装到List中并将所有下一个数字添加到它中，总共有方形复杂度，多么悲伤。

Elements of second stream happened to be computed in descend order. The easiest what collect method can do is for each number wrap it into List and add all next numbers to it, with square complexity in total, how sad.

推荐答案

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

In this case the input desc list will be divided to the several independent parts depending on number of hardware threads your system has. Usually it's 16 parts on 4-core system (though it's not specified and may change). Each part will be processed independently using the accumulator, then results will be merged together using the combiner. So it won't drop to quadratic complexity, but yes, many unnecessary copying will be done.

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

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

这篇关于Java，Collectors.toList（）复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！