使用 fork-join 进行 Java 多路树搜索

Question

我有多路树结构，我必须遍历它来确定状态。我正在研究首先处理叶节点的“后序”类型遍历。搜索结束条件取决于任何一个状态为非 Activity 的子节点。另外，从性能的角度来看，我会使用 JDK7 的 fork-join 机制。

Answer 1

这是一个(非常)粗略的草图，说明您如何做到这一点。

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);
        }
    }
}

一些需要修改的东西:

• 添加您对非 Activity 状态的检查。最简单的方法是在每个 RecursiveAction 中保留一个原子 boolean 值，在处理节点之前检查并在节点处于非 Activity 状态时更新，尽管这不是一个非常干净或实用的路线。
• 添加一种方法来决定何时应该使用新线程，上面为每个节点使用一个线程。此外，您可以通过不在每次调用 postorderParallel 时创建 ForkJoinPool 来稍微优化它。