为什么在flatMap()之后的filter()在Java流中“not completely”是懒惰的?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (21)

我有以下示例代码:

System.out.println(
       "Result: " +
        Stream.of(1, 2, 3)
                .filter(i -> {
                    System.out.println(i);
                    return true;
                })
                .findFirst()
                .get()
);
System.out.println("-----------");
System.out.println(
       "Result: " +
        Stream.of(1, 2, 3)
                .flatMap(i -> Stream.of(i - 1, i, i + 1))
                .flatMap(i -> Stream.of(i - 1, i, i + 1))
                .filter(i -> {
                    System.out.println(i);
                    return true;
                })
                .findFirst()
                .get()
);

输出如下:

1
Result: 1
-----------
-1
0
1
0
1
2
1
2
3
Result: -1

从这里我可以看出,在第一种情况下,stream实际上表现得很懒 - 我们使用findFirst()这样一旦我们有第一个元素,我们的过滤lambda没有被调用。然而,在使用flatMaps的第二种情况下,我们看到,尽管找到了满足过滤条件的第一个元素(它只是任何第一个元素,因为lambda总是返回true),但流的更多内容仍然通过过滤函数馈送。

我试图理解为什么它表现得像这样,而不是像第一种情况那样计算第一个元素后放弃。任何有用的信息将不胜感激。

提问于
用户回答回答于

当查看实现(ReferencePipeline.java)时,我们看到方法[ link ]

@Override
final void forEachWithCancel(Spliterator<P_OUT> spliterator, Sink<P_OUT> sink) {
    do { } while (!sink.cancellationRequested() && spliterator.tryAdvance(sink));
}

这将被调用进行findFirst操作。要特别注意的是,sink.cancellationRequested()它允许在第一场比赛结束循环。与[ link ] 比较

@Override
public final <R> Stream<R> flatMap(Function<? super P_OUT, ? extends Stream<? extends R>> mapper) {
    Objects.requireNonNull(mapper);
    // We can do better than this, by polling cancellationRequested when stream is infinite
    return new StatelessOp<P_OUT, R>(this, StreamShape.REFERENCE,
                                 StreamOpFlag.NOT_SORTED | StreamOpFlag.NOT_DISTINCT | StreamOpFlag.NOT_SIZED) {
        @Override
        Sink<P_OUT> opWrapSink(int flags, Sink<R> sink) {
            return new Sink.ChainedReference<P_OUT, R>(sink) {
                @Override
                public void begin(long size) {
                    downstream.begin(-1);
                }

                @Override
                public void accept(P_OUT u) {
                    try (Stream<? extends R> result = mapper.apply(u)) {
                        // We can do better that this too; optimize for depth=0 case and just grab spliterator and forEach it
                        if (result != null)
                            result.sequential().forEach(downstream);
                    }
                }
            };
        }
    };
}

用于推进一个项目的方法最终调用forEach子流而没有任何可能的提前终止,并且flatMap方法开始处的评论甚至会告诉这个缺少的特征。

由于这不仅仅是一个优化的事情,因为它暗示当子流是无限的时候代码就会中断,我希望开发人员很快证明他们“可以做得比这更好”...

为了说明这些影响,尽管Stream.iterate(0, i->i+1).findFirst()按预期工作,Stream.of("").flatMap(x->Stream.iterate(0, i->i+1)).findFirst()最终将会无限循环。

关于规范,其中大部分可以在中找到

包规范的“流操作和流水线”一章

… 中间操作返回一个新的流。他们总是懒惰 ; … 懒惰还可以避免在没有必要时检查所有数据; 对于诸如“查找长度超过1000个字符的第一个字符串”等操作,只需检查足够的字符串即可找到具有所需特性的字符串,而无需检查源中可用的所有字符串。(当输入流是无限的,而不仅仅是大的时候,这种行为变得更加重要。) … 此外,有些操作被认为是短路操作。如果在呈现无限输入时,中间操作是短路的,则其可能产生有限的流。终端操作是短路的,如果出现无限输入时,它可能会在有限的时间内终止。在流水线中进行短路操作是处理无限流在有限时间内正常终止的必要但不充分的条件。

显而易见的是,短路操作不能保证有限的时间终止,例如,当过滤器与处理无法完成的任何项目不匹配时,而是通过简单地忽略不支持在有限时间内终止的实现操作的短路性质远不符合规范。

用户回答回答于

输入流的元素被逐个消耗掉。第一个元素,1被两个flatMaps转换成流-1, 0, 1, 0, 1, 2, 1, 2, 3,因此整个流只对应于第一个输入元素。嵌套流被管道急切地物化,然后变平,然后馈送到filter舞台。这解释了你的输出。

以上内容并不是源于一个根本性的限制,但它可能会让事情变得复杂得多,以致于对嵌套流进行全面的懒惰。我怀疑它的表现会是一个更大的挑战。为了比较,Clojure的懒惰seqs为每个这样的嵌套层次获得了另一层包装。由于这种设计,操作甚至可能StackOverflowError在嵌套行使到极限时失败。

扫码关注云+社区