4

ツリー ノードのデスカンダントであるすべてのリーフ ノードを取得するように依頼されました。私はすぐに、この仕事を 1 行で行うことができるという考えにたどり着きました!

public Set<TreeNode<E>> getLeaves() {
    return getChildrenStream().flatMap(n -> n.getChildrenStream()).collect(toSet());
}

一見良かったのですが、すぐにStackOverflowExcepetionツリーの深さが 10 に達すると、受け入れられないものに遭遇しました。後で、再帰とストリームを使用しない実装を開発しました (ただし、私の脳はローストされflatMapています)が、ストリームの内部に触れずに再帰を実行することは不可能であることがわかったため、ストリームを使用して再帰を実行する方法があるかどうかはまだ疑問に思っています。それを行うには、新しい Op が必要になるか、すべての結果をすべてのステップRecursiveOpsに収集して、後で操作する必要があります。SetSet

Set<TreeNode<E>> prev = new HashSet<>();
prev.add(this);
while (!prev.isEmpty()) {
    prev = prev.stream().flatMap(n -> n.getChildrenStream()).collect(toSet());
}
return prev;

見た目ほど良くない。ストリームはパイプラインであることを意図しています。その結果と中間結果は、端末操作が追加されるまで計算されません。上記のアプローチは、明らかにその原則に違反しています。ストリームほど簡単に並列化することもできません。すべての中間結果を手動で計算せずに再帰的に flatMap を実行できますか?

PS1: TreeNode 宣言:

public class TreeNode<E> {
    // ...
    /**
     * Get a stream of children of the current node. 
     *
     */
    public Stream<TreeNode<E>> getChildrenStream(){
        // ...
    }

    public Set<TreeNode<E>> getLeaves() {
        // main concern
    }
}f
4

1 に答える 1

0

これがあなたが興味を持っているものになるかどうかは完全にはわかりません：

public static Set<TreeNode<String>> getAllLeaves(TreeNode<String> treeNode) {
    final Stream<TreeNode<String>> childrenStream = treeNode.getChildrenStream();
    if (childrenStream == null) {
        return new HashSet<>();
    }

    Set<TreeNode<String>> ownLeaves = treeNode.getLeaves();
    ownLeaves.addAll(childrenStream.flatMap(stringTreeNode -> getAllLeaves(stringTreeNode).parallelStream())
            .collect(Collectors.toSet()));

    return ownLeaves;
}

箱から出して、この方法にはいくつかの不便があります。最後の反復で空の Set を返し、 と同様にストリームを作成していflatMapます。flatMapただし、最初にストリームが作成されなかった場所で再帰的に作成された結合セットを取得したい場所から使用することを考えているので、これはあなたが探しているものだと思います。ところで、これを -1000 レベルで試してみましたが、それでも非常に高速で問題なく動作します。

于 2016-05-28T15:30:18.570 に答える