在Java中,如何高效地优化流式传输树节点的后代？
|
假设我们有一个由唯一的字符串标识的对象的集合,以及定义它们上的层次结构的类树.该类使用从节点(由其ID表示)到其各自的子ID的集合的映射来实现.
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,…)形成堆栈,因此在任何给定时间的存储器需求与树的深度相同的复杂度. 如果我正确理解这些要点,我的问题是这样的：我如何定义后代,以便生成的流是懒惰的？ 我希望解决方案尽可能优雅,在某种意义上,我更喜欢一种使迭代状态隐含的解决方案. (为了澄清我的意思：我知道我可以编写一个Spliterator,在每个级别上保持一个显式的Spliterator堆栈,我们可以在树上移动,我想避免这一点) (Java中可能有一种方法可以将其作为生产者 – 消费者工作流程,像在Julia和Go这样的语言中可以使用) 解决方法
对我来说,您的解决方案已经尽可能优雅,而且它的有限懒惰不是你的错.最简单的解决方案是等待JRE开发人员修复.
但是,如果今天执行的这种有限的懒惰真的是一个问题,那么也可能是一般的解决这个问题的时候了.那么这是关于实现一个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时. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |