0

私は多方向のツリー構造を持っており、ステータスを判断するためにトラバースする必要があります。リーフノードが最初に処理される「ポストオーダー」タイプのトラバーサルを調べています。また、検索の終了条件は、ステータスが非アクティブの子ノードのいずれかに依存します。また、パフォーマンスの観点から、JDK7のフォーク結合メカニズムを使用します。

ここに画像の説明を入力してください

4

1 に答える 1

2

以下は、それを行う方法の (非常に) 大まかなスケッチです。

final class TreeNode {
    private final Iterable<TreeNode> children;

    TreeNode(Iterable<TreeNode> aChildren) {
        children = aChildren;
    }

    Iterable<TreeNode> getChildren() {
        return children;
    }

    void postorder(TreeNodeIterator iterator) {
        postorderTraverse(this, iterator);
    }

    private void postorderTraverse(TreeNode node, TreeNodeIterator iterator) {
        for (TreeNode child : children) {
            postorderTraverse(child, iterator);
        }
        iterator.visit(node);
    }

    void postorderParallel(TreeNodeIterator iterator) {
        new ForkJoinPool().invoke(new VisitNodeAction(iterator, this));
    }

    interface TreeNodeIterator {
        void visit(TreeNode child);
    }

    private class VisitNodeAction extends RecursiveAction {
        private final TreeNodeIterator iterator;
        private final TreeNode node;

        private VisitNodeAction(TreeNodeIterator iterator, TreeNode node) {
            this.iterator = iterator;
            this.node = node;
        }

        @Override
        protected void compute() {
            List<RecursiveAction> tasks = new LinkedList<RecursiveAction>();
            for (TreeNode child : children) {
                tasks.add(new VisitNodeAction(iterator, child));
            }
            invokeAll(tasks);
            iterator.visit(node);
        }
    }
}

変更する必要があるいくつかのこと:

  • ステータスが非アクティブであることのチェックを追加します。RecursiveAction最も簡単な方法は、ノードを処理する前にチェックされ、ノードが非アクティブになったときに更新されるアトミックブール値をそれぞれに保持することですが、これは非常にクリーンまたは機能的なルートではありません。
  • 新しいスレッドをいつ使用するかを決定する方法を追加すると、上記はすべてのノードにスレッドを使用します。ForkJoinPoolまた、の呼び出しごとにを作成しないことで、少し最適化できる可能性がありますpostorderParallel
于 2013-01-09T20:04:48.473 に答える