在Java中，如何高效优雅地传输树节点的后代？
假设我们有一组由唯一String标识的对象，以及一个定义它们层次结构的类Tree 。 该类使用从节点（由其ID表示）到其各自子节点ID的Collection的Map来实现。
class Tree { private Map<String, Collection> edges; // ... public Stream descendants(String node) { // To be defined. } }
我想启用流式节点的后代。 一个简单的解决方案是：
private Stream children(String node) { return edges.getOrDefault(node, Collections.emptyList()).stream(); } public Stream descendants(String node) { return Stream.concat( Stream.of(node), children(node).flatMap(this::descendants) ); }
在继续之前，我想对此解决方案做出以下断言。 （我对这些是正确的吗？）
-
从
descendants返回的Stream消耗资源（时间和内存） – 相对于树的大小 – 与复制的手动编码的复杂程度相同。 特别是，表示迭代状态的中间对象（Streams，Spliterators，…）形成堆栈，因此在任何给定时间的内存需求与树的深度具有相同的复杂度。 -
据我所知，只要我对从
descendants返回的Stream执行终止操作，对flatMap的根级调用将导致所有包含的Stream– 每个（递归）调用descendants– 立即实现。 因此，结果Stream只在第一级递归时是惰性的，但不会超出。 （根据Tagir Valeevs的回答编辑。）
如果我正确地理解了这些要点，我的问题是： 如何定义descendants以使得生成的Stream是懒惰的？
我希望解决方案尽可能优雅，因为我更喜欢一种隐含迭代状态的解决方案。 （为了澄清我的意思：我知道我可以编写一个Spliterator来Spliterator树，同时在每个级别上保持一个明确的Spliterator堆栈。我想避免这种情况。）
（在Java中可能有一种方法可以将其表示为生产者 – 消费者工作流程，就像可以在Julia和Go等语言中使用吗？）
对我来说，你的解决方案已经尽可能优雅，而且有限的懒惰不是你的错。 最简单的解决方案是等待JRE开发人员修复它。 它已经完成了Java 10 。
然而，如果今天实施的这种有限的懒惰确实是一个问题，那么也许是时候以一般的方式解决这个问题了。 好吧，它是关于实现Spliterator ，但不是特定于您的任务。 相反，它是flatmap操作的重新实现，服务于原始实现的有限flatmap所有情况：
public class FlatMappingSpliterator extends Spliterators.AbstractSpliterator implements Consumer { static final boolean USE_ORIGINAL_IMPL = Boolean.getBoolean("stream.flatmap.usestandard"); public static Stream flatMap( Stream in, Function> 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 src; final Function> f; Stream currStream; Spliterator curr; private FlatMappingSpliterator( Spliterator src, Function> 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 action) { do { if(curr!=null) { if(curr.tryAdvance(action)) return true; closeCurr(); } } while(src.tryAdvance(this)); return false; } @Override public void forEachRemaining(Consumer action) { if(curr!=null) { curr.forEachRemaining(action); closeCurr(); } src.forEachRemaining(s->{ try(Stream str=f.apply(s)) { if(str!=null) str.spliterator().forEachRemaining(action); } }); } @SuppressWarnings("unchecked") private static Spliterator sp(Stream str) { return str!=null? ((Stream )str).spliterator(): null; } @Override public Spliterator trySplit() { Spliterator split = src.trySplit(); if(split==null) { Spliterator prefix = curr; while(prefix==null && src.tryAdvance(s->curr=sp(f.apply(s)))) prefix=curr; curr=null; return prefix; } FlatMappingSpliterator prefix=new FlatMappingSpliterator<>(split, f); if(curr!=null) { prefix.curr=curr; curr=null; } return prefix; } }
使用它所需要的只是将flatMap方法的import static添加到代码中，并将表单stream.flatmap(function)表达式更改为flatmap(stream, function) 。
即你的代码
public Stream descendants(String node) { return Stream.concat( Stream.of(node), flatMap(children(node), this::descendants) ); }
然后你有完全懒惰的行为。 我用无限的流来测试它…
请注意，我添加了一个切换以允许返回到原始实现，例如在命令行上指定-Dstream.flatmap.usestandard=true时。
你说flatMap流并不是懒惰的，这有点不对劲。 有点懒，虽然它的懒惰真的有限。 让我们使用一些自定义Collection来跟踪Tree类中所请求的元素：
private final Set requested = new LinkedHashSet<>(); private class MyList extends AbstractList 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访问（因为Stream.concat是智能的）。 当请求第一个直接子项时，即使没有必要，也会处理该子项的整个子树。 然而，第二个直接孩子在第一个孩子完成之前不会被处理。 这对于短路情况可能会有问题，但在大多数情况下，您的终端操作不会短路，因此它仍然是很好的方法。
至于你对内存消耗的担忧：是的，它会根据树的深度来吃掉内存（更重要的是它会占用堆栈）。 如果您的树有数千个嵌套级别，则您的解决方案会出现问题，因为您可能会在StackOverflowError找到默认的-Xss设置。 对于几百个深度级别，它可以正常工作。
我们在应用程序的业务逻辑层中使用类似的方法，它对我们来说很好，尽管我们的树很少超过10个级别。
不是一个真正的答案，而只是一个想法：
如果您查看值集合并在下一步“解析”最后看到的值到新的值集合以递归方式以相同的方式返回下一个值，那么无论如何实现，它总是以某种“指针“指向树中深度当前”级别“的值集合中的当前元素，并且还有某种堆栈保存所有那些”指针“。
这是因为您需要有关树（堆栈）中较高级别的信息和当前级别当前元素的“指针”。 在这种情况下，一个导致另一个。
当然，您可以将其实现为包含迭代器堆栈的Spliterator （指向相应的值集合），但我想在每个深度级别始终会有一个“指针”状态，即使它隐藏在Java的flatMap中（或相关的）临时对象。
作为替代方案：如何使用包含对其父节点的引用的节点的“真实”树？ 另外，向树的根添加一个映射，该映射包含对所有单个节点的引用，以简化对子子子的访问。 我猜Spliterator实现非常简单，因为它只需要引用当前节点进行遍历，并且需要一个停止标准（初始节点值）来停止在树中“走高”。
我建议事实上类似于你不想要的东西，但实现起来比直接维护堆栈更容易和更优雅
public class TreeIterator { private Tree tree; private List topLevelNodes; public TreeIterator(Tree t, String node) { topLevelNodes = new List(); topLevelNodes.add(node); tree = t; } public String next() { if (topLevelNodes.size() > 0) { int last = topLevelNodes.size() - 1; String result = topLevelNodes.get(last); topLevelNodes.remove(last); topLevelNodes.addAll(tree.get(result)); return result; } return null; } }
对不起new List()和其他不正确的事情，只是想分享这个想法。