为什么 flatMap() 之后的 filter() 是“不完全"的?在 Java 流中懒惰?
我有以下示例代码:
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 就不会被调用.然而,在使用 flatMap
s 的第二种情况下,我们看到尽管找到了满足过滤条件的第一个元素(它只是任何第一个元素,因为 lambda 总是返回 true)流的其他内容仍在被提供通过过滤功能.
From here I see that in first case stream
really behaves lazily - we use findFirst()
so once we have first element our filtering lambda is not invoked.
However, in second case which uses flatMap
s we see that despite first element which fulfils the filter condition is found (it's just any first element as lambda always returns true) further contents of the stream are still being fed through filtering function.
我试图理解为什么它会这样,而不是像第一种情况那样在计算第一个元素后放弃.任何有用的信息将不胜感激.
I am trying to understand why it behaves like this rather than giving up after first element is calculated as in the first case. Any helpful information would be appreciated.
推荐答案
TL;DR,这已在 JDK-8075939 并在 Java 10 中修复(并在 Java 8JDK-8225328" rel="noreferrer">JDK-8225328).
TL;DR, this has been addressed in JDK-8075939 and fixed in Java 10 (and backported to Java 8 in JDK-8225328).
查看实现时(ReferencePipeline.java
),我们看到方法 [链接]
When looking into the implementation (ReferencePipeline.java
) we see the method [link]
@Override
final void forEachWithCancel(Spliterator<P_OUT> spliterator, Sink<P_OUT> sink) {
do { } while (!sink.cancellationRequested() && spliterator.tryAdvance(sink));
}
将为 findFirst
操作调用.特别需要注意的是 sink.cancellationRequested()
允许在第一次匹配时结束循环.比较 [链接]
which will be invoke for findFirst
operation. The special thing to take care about is the sink.cancellationRequested()
which allows to end the loop on the first match. Compare to [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
方法开头的注释甚至告诉关于这个缺失的功能.
The method for advancing one item ends up calling forEach
on the sub-stream without any possibility for earlier termination and the comment at the beginning of the flatMap
method even tells about this absent feature.
由于这不仅仅是优化的事情,因为它意味着当子流无限时代码会简单地中断,我希望开发人员尽快证明他们可以做得比这更好"......
Since this is more than just an optimization thing as it implies that the code simply breaks when the sub-stream is infinite, I hope that the developers soon prove that they "can do better than this"…
为了说明含义,虽然 Stream.iterate(0, i->i+1).findFirst()
按预期工作,但 Stream.of("").flatMap(x->Stream.iterate(0, i->i+1)).findFirst()
会陷入无限循环.
To illustrate the implications, while Stream.iterate(0, i->i+1).findFirst()
works as expected, Stream.of("").flatMap(x->Stream.iterate(0, i->i+1)).findFirst()
will end up in an infinite loop.
关于规范,大部分都可以在
Regarding the specification, most of it can be found in the
章节流操作和管道"的包规范:
…
中间操作返回一个新流.他们总是懒惰;
Intermediate operations return a new stream. They are always lazy;
…
... 懒惰还允许在不必要的时候避免检查所有数据;对于诸如查找第一个超过 1000 个字符的字符串"之类的操作,只需检查足够多的字符串即可找到具有所需特征的字符串,而无需检查源中可用的所有字符串.(当输入流是无限的而不仅仅是大时,这种行为变得更加重要.)
… Laziness also allows avoiding examining all the data when it is not necessary; for operations such as "find the first string longer than 1000 characters", it is only necessary to examine just enough strings to find one that has the desired characteristics without examining all of the strings available from the source. (This behavior becomes even more important when the input stream is infinite and not merely large.)
…
此外,一些操作被视为短路操作.如果在呈现无限输入时,中间操作可能会产生有限流,则它是短路的.如果一个终端操作在有无限输入时可能会在有限时间内终止,那么它就是短路的.在管道中进行短路操作是无限流处理在有限时间内正常终止的必要条件,但不是充分条件.
Further, some operations are deemed short-circuiting operations. An intermediate operation is short-circuiting if, when presented with infinite input, it may produce a finite stream as a result. A terminal operation is short-circuiting if, when presented with infinite input, it may terminate in finite time. Having a short-circuiting operation in the pipeline is a necessary, but not sufficient, condition for the processing of an infinite stream to terminate normally in finite time.
很明显,短路操作并不能保证有限时间终止,例如当过滤器不匹配任何项目时,处理无法完成,但是通过简单地忽略操作的短路性质而在有限时间内不支持任何终止的实现与规范相差甚远.
It’s clear that a short-circuiting operation doesn’t guaranty a finite time termination, e.g. when a filter doesn’t match any item the processing can’t complete, but an implementation which doesn’t support any termination in finite time by simply ignoring the short-circuiting nature of an operation is far off the specification.
相关文章