在Java中,如何高效地优化流式传输树节点的后代?

前端之家收集整理的这篇文章主要介绍了在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,…)形成堆栈,因此在任何给定时间的存储器需求与树的深度相同的复杂度.
>据了解,this在对从后代返回的Stream执行终止操作后,对flatMap的根级别调用将导致所有包含的Streams(每次(递归)调用后代)都会立即实现.因此,所产生的Stream只是在第一级递归上懒惰,但不能超越. (根据Tagir Valeevs answer.编辑)

如果我正确理解这些要点,我的问题是这样的:我如何定义后代,以便生成的流是懒惰的?

我希望解决方案尽可能优雅,在某种意义上,我更喜欢一种使迭代状态隐含的解决方案. (为了澄清我的意思:我知道我可以编写一个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时.

猜你在找的Java相关文章