在Java中，如何高效、优雅地流式处理树节点的子代？

Question

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

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，...）形成了一个堆栈，因此在任何给定时间的内存需求与树的深度处于相同的复杂度顺序。

据我所知，只要我对从子体返回的流执行终止操作，对flatMap的根级调用将导致所有包含的流立即实现，对子体的每个（递归）调用一个。因此，产生的流仅在递归的第一级上是惰性的，而不是更高级别。（根据Tagir Valeevs的回答进行编辑。）

如果我正确理解了这些要点，我的问题是：如何定义子体，从而使生成的流是惰性的？

我希望这个解决方案尽可能优雅，因为我更喜欢隐式保留迭代状态的解决方案。（为了澄清我的意思：我知道我可以编写一个Spliterator，在树上运行，同时在每个级别上维护一个显式的Spliterators堆栈。我希望避免这种情况。）

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

Answer 1

不是真正的答案，只是一个想法：

如果你窥视值集合，并在下一步“解析”最后看到的值到一个新的值集合，以同样的方式递归返回下一个值，那么不管实现了什么，它总是会以某种“指针”结束当前元素集合中的值在树的当前"级别"上的深度，并且还用某种堆栈保持所有那些"指针"。

这是因为您既需要有关树（堆栈）中更高级别的信息，也需要指向当前级别的当前元素的“指针”。在这种情况下，一个导致另一个。

当然，您可以将其实现为一个包含迭代器堆栈（指向相应的值集合）的Spliterator，但是我想在每个深度级别上总是有一个“指针”状态，即使它隐藏在Java的平面地图中（或者相关的）临时对象。

另一种选择是：如何使用一个“真实”树，其中的节点包含对其父节点的引用？另外，向树的根添加一个映射，该映射包含对所有单个节点的引用，以简化对子节点的访问。我猜Spliterator实现将非常简单，因为它只需要引用当前节点进行遍历，并需要一个停止条件（初始节点值）来停止在树中走得太高。

Answer 2

你说flatMap流不是懒惰的有点错误。它有点懒，虽然它的懒真的很有限。让我们使用一些自定义的Collection来跟踪您的Tree类中请求的元素：

private final Set<String> requested = new LinkedHashSet<>();

private class MyList extends AbstractList<String> implements RandomAccess
{
    private final String[] data;

    public MyList(String... data) {
        this.data = data;
    }

    @Override
    public String get(int index) {
        requested.add(data[index]);
        return data[index];
    }

    @Override
    public int size() {
        return data.length;
    }
}

现在，让我们使用一些树数据预初始化您的类：

public Tree() {
    // "1" is the root note, contains three immediate descendants
    edges.put("1", new MyList("2", "3", "4"));
    edges.put("2", new MyList("5", "6", "7"));
    edges.put("3", new MyList("8", "9", "10"));
    edges.put("8", new MyList("11", "12"));
    edges.put("5", new MyList("13", "14", "15"));
    edges.put("7", new MyList("16", "17", "18"));
    edges.put("6", new MyList("19", "20"));
}

最后，让我们检查在不同的限制值下，从列表中实际请求了多少元素：

public static void main(String[] args) {
    for(int i=1; i<=20; i++) {
        Tree tree = new Tree();
        tree.descendants("1").limit(i).toArray();
        System.out.println("Limit = " + i + "; requested = (" + tree.requested.size()
                + ") " + tree.requested);
    }
}

输出如下：

Limit = 1; requested = (0) []
Limit = 2; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 3; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 4; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 5; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 6; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 7; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 8; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 9; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 10; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 11; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 12; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 13; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 14; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 15; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 16; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 17; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 18; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 19; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 20; requested = (19) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10, 4]

因此，当只请求根注释时，不执行对子级的访问（因为Stream.concat是智能的）。当请求第一个直接子级时，即使不必要，也会处理该子级的整个子树。然而，在第一个子节点完成之前，第二个直接子节点不会被处理。这对于短路场景可能是有问题的，但是在大多数情况下，您的终端操作没有短路，因此它仍然是一种很好的方法。

至于您对内存消耗的担忧：是的，它根据树的深度消耗内存（更重要的是，它消耗堆栈）。如果您的树有数千个嵌套级别，您的解决方案将出现问题，因为您可能会点击默认-Xss设置的stackoverflowerrror。对于几百层的深度，它可以很好地工作。

我们在应用程序的业务逻辑层中使用了类似的方法，它对我们来说很好，尽管我们的树很少超过10层。

Answer 3

对我来说，你的解决方案已经尽可能优雅了，有限的懒惰不是你的错。最简单的解决方案是等待JRE开发人员修复它。它是用Java完成的

然而，如果今天实现的这种有限的惰性真的是一个问题，那么也许是时候用一种普遍的方式来解决这个问题了。好的，它是关于实现一个拆分器的，但并不特定于您的任务。相反，它是对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;
    }
}

使用它所需要的只是在代码中添加flatMap方法的import static，并更改表单流的表达式。平面图（函数）到平面图（流、函数）。

也就是说，在你的代码中

public Stream<String> descendants(String node) {
    return Stream.concat(
        Stream.of(node),
        flatMap(children(node), this::descendants)
    );
}

那么你就有了完全的懒惰行为。我甚至用无限的溪流来测试它…

请注意，我添加了一个切换以允许返回到原始实现，例如，当指定