标准集合返回的 Stream 实现有多专业？

Question

Stream 是一个接口，所以每当有人获得一个 Stream 对象时，就会隐藏很多实现特定的细节。

例如取下面的代码：

List<String> list = new ArrayList<>();
...
int size = list.stream()
               .count();

运行是常数时间还是线性时间？或者这个：

Set<String> set = new TreeSet<>();
...
set.stream()
   .sorted()
   .forEach(System.out::println);

是 O(n) 还是 O(n log n)？

一般来说，标准集合返回的流实现有多专业？

Answer 1

Does it run in constant or linear time?

当前实现运行线性时间：

public final long count() {
    return mapToLong(e -> 1L).sum();
}

但是，在某些情况下，这可以改进（某处有一个 RFE）到运行。

怎么样？流由流源、零个或多个中间操作和终端操作描述（这里，count()是终端操作）。流实现维护一组关于源的特征，并且知道这些特征是如何被操作修改的。例如，由 Collection 支持的流具有 SIZED 特征，而由 Iterator 支持的流没有大小限制。类似地，操作 map() 是保持大小的，但是操作 filter() 破坏了任何关于大小的先验知识。流实现在开始终端操作之前知道管道的组成特征，因此它知道源是否有大小以及所有阶段是否都保持大小，在这种情况下，可以简单地向源询问大小并绕过所有实际的流计算。（但是 Java 8 中的实现并没有这样做。）

请注意，流不需要专门支持这一点； Collection 类使用知道其特性的 Spliterator 创建流，因此不需要 Collections 的专门实现，只需更新共享实现以利用这一特定信息。

Answer 2

sorted() 方法不会改变大小，因此从理论上讲，未来的实施可能会在 O(1) 时间内完成一系列 stream().sorted().count()。

在 https://github.com/speedment/speedment 查看 Stream 接口的 [speedment] 开源实现。这些流可以自省它们自己的管道并优化掉流中的一个或多个步骤。

标准集合返回的 Stream 实现有多专业？

How specialized are the Stream implementations returned by the standard collections?

java

java-8

java-stream