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