在Java中，如何高效，优雅地传输树节点的后代？

小编典典

在Java中，如何高效，优雅地传输树节点的后代？

algorithm

假设我们有一个由唯一的Strings
标识的对象的集合，以及Tree一个在其上定义层次结构的类。使用Map从节点（由其ID表示）到Collection其各自子ID的s 实现该类。

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返回的descendants资源会消耗资源（时间和内存），其复杂程度与递归编码的顺序相同。特别是，代表迭代状态（Streams，Spliterators，…）的中间对象形成一个堆栈，因此在任何给定时间的存储需求的复杂度与树的深度相同。
据我所知此，只要我在执行终止操作Stream从返回descendants，根级别调用flatMap将导致所有包含Stream秒-一个用于每个（递归）呼叫descendants-被立即实现。因此，结果Stream仅在第一递归级别上是懒惰的，但没有超出。 （根据 Tagir Valeevs的答案编辑。）

如果我正确理解了这些要点，那么我的问题是： 如何定义结果，descendants使它们Stream变得懒惰？

从某种意义上说，我希望该解决方案尽可能优雅，因为我更喜欢一种使迭代状态保持隐式的解决方案。（以澄清我的意思：我知道我可以编写一个Spliterator在树上遍历的树，同时Spliterator在每个级别上都保留一个显式的s。我想避免这种情况。）

（Java中是否可能有一种方法可以将其表述为生产者-消费者工作流程，就像可以在Julia和Go这样的语言中使用的方式？）

阅读 276

2020-07-28

共1个答案

小编典典

对我来说，您的解决方案已经尽可能地优雅，并且它的有限懒惰不是您的错。最简单的解决方案是等待JRE开发人员对其进行修复。它已使用Java
10完成。

但是，如果今天实施的这种有限的延迟确实令人担忧，那么也许是时候以一般的方式解决此问题了。嗯，这是
关于实现Spliterator，但不是特定于您的任务的。相反，它是flatmap对在原始实现的有限懒惰很重要的所有情况下使用的操作的重新实现：

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()+100, 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;
    }
}

所有你需要使用它，是一个新增importstatic的的flatMap方法形式的代码，并改变表情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命令行上指定时。

2020-07-28