class Tree {
private Map<String,Collection<String>> edges;
// ...
public Stream<String> descendants(String node) {
// To be defined.
}
}
我想启用流节点的后代.这是一个简单的解决方案：
private Stream<String> children(String node) {
return edges.getOrDefault(node,Collections.emptyList()).stream();
}
public Stream<String> descendants(String node) {
return Stream.concat(
Stream.of(node),children(node).flatMap(this::descendants)
);
}
在继续之前,我想对这个解决方案做出以下断言. (我是否正确对这些？)
>从后代返回的Stream的流程相对于树的大小消耗资源(时间和内存),与手写编码的复杂度相同.特别地,表示迭代状态的中间对象(Streams,Spliterators,…)形成堆栈,因此在任何给定时间的存储器需求与树的深度相同的复杂度.
>据了解,this在对从后代返回的Stream执行终止操作后,对flatMap的根级别调用将导致所有包含的Streams(每次(递归)调用后代)都会立即实现.因此,所产生的Stream只是在第一级递归上懒惰,但不能超越. (根据Tagir Valeevs answer.编辑)
如果我正确理解这些要点,我的问题是这样的：我如何定义后代,以便生成的流是懒惰的？
我希望解决方案尽可能优雅,在某种意义上,我更喜欢一种使迭代状态隐含的解决方案. (为了澄清我的意思：我知道我可以编写一个Spliterator,在每个级别上保持一个显式的Spliterator堆栈,我们可以在树上移动,我想避免这一点)
(Java中可能有一种方法可以将其作为生产者 – 消费者工作流程,像在Julia和Go这样的语言中可以使用)
解决方法
但是,如果今天执行的这种有限的懒惰真的是一个问题,那么也可能是一般的解决这个问题的时候了.那么这是关于实现一个Spliterator,但不是你的任务.相反,这是重新实施平面图操作,适用于原始实施有限懒惰的所有情况：
public class FlatMappingSpliterator<E,S> extends Spliterators.AbstractSpliterator<E>
implements Consumer<S> {
static final boolean USE_ORIGINAL_IMPL
= Boolean.getBoolean("stream.flatmap.usestandard");
public static <T,R> Stream<R> flatMap(
Stream<T> in,Function<? super T,? extends Stream<? extends R>> mapper) {
if(USE_ORIGINAL_IMPL)
return in.flatMap(mapper);
Objects.requireNonNull(in);
Objects.requireNonNull(mapper);
return StreamSupport.stream(
new FlatMappingSpliterator<>(sp(in),mapper),in.isParallel()
).onClose(in::close);
}
final Spliterator<S> src;
final Function<? super S,? extends Stream<? extends E>> f;
Stream<? extends E> currStream;
Spliterator<E> curr;
private FlatMappingSpliterator(
Spliterator<S> src,Function<? super S,? extends Stream<? extends E>> f) {
// actually,the mapping function can change the size to anything,// but it seems,with the current stream implementation,we are
// better off with an estimate being wrong by magnitudes than with
// reporting unknown size
super(src.estimateSize(),src.characteristics()&ORDERED);
this.src = src;
this.f = f;
}
private void closeCurr() {
try { currStream.close(); } finally { currStream=null; curr=null; }
}
public void accept(S s) {
curr=sp(currStream=f.apply(s));
}
@Override
public boolean tryAdvance(Consumer<? super E> action) {
do {
if(curr!=null) {
if(curr.tryAdvance(action))
return true;
closeCurr();
}
} while(src.tryAdvance(this));
return false;
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
if(curr!=null) {
curr.forEachRemaining(action);
closeCurr();
}
src.forEachRemaining(s->{
try(Stream<? extends E> str=f.apply(s)) {
if(str!=null) str.spliterator().forEachRemaining(action);
}
});
}
@SuppressWarnings("unchecked")
private static <X> Spliterator<X> sp(Stream<? extends X> str) {
return str!=null? ((Stream<X>)str).spliterator(): null;
}
@Override
public Spliterator<E> trySplit() {
Spliterator<S> split = src.trySplit();
if(split==null) {
Spliterator<E> prefix = curr;
while(prefix==null && src.tryAdvance(s->curr=sp(f.apply(s))))
prefix=curr;
curr=null;
return prefix;
}
FlatMappingSpliterator<E,S> prefix=new FlatMappingSpliterator<>(split,f);
if(curr!=null) {
prefix.curr=curr;
curr=null;
}
return prefix;
}
}
所有您需要使用它,是将flatMap方法的import静态添加到您的代码,并将表单stream.flatmap(function)的表达式更改为flatmap(stream,function).
即在你的代码
public Stream<String> descendants(String node) {
return Stream.concat(
Stream.of(node),flatMap(children(node),this::descendants)
);
}
那么你有完全的懒惰的行为.我测试了,甚至与无限流…
请注意,我添加了一个切换以允许回到原始实现,例如在命令行中指定-Dstream.flatmap.usestandard = true时.
