我有递归代码,以深度优先的方式处理树结构.代码基本上如下所示：
function(TreeNode curr)
{
if (curr.children != null && !curr.children.isEmpty())
{
for (TreeNode n : curr.children)
{
//do some stuff
function(n);
}
}
else
{
//do some other processing
}
}
我想使用线程来加快完成速度.大部分时间都花在遍历上,所以我不想只创建一个线程来处理“其他处理”,因为它不需要那么长时间.我想我想在“做一些事情”时分叉线程,但是如何工作呢？
解决方法
这是
Fork/Join framework的一个很好的例子,它将被包含在Java 7中.作为与Java 6一起使用的独立库,可以下载到
here.
像这样的东西：
public class TreeTask extends RecursiveAction {
private final TreeNode node;
private final int level;
public TreeTask(TreeNode node,int level) {
this.node = node;
this.level = leve;
}
public void compute() {
// It makes sense to switch to single-threaded execution after some threshold
if (level > THRESHOLD) function(node);
if (node.children != null && !node.children.isEmpty()) {
List<TreeTask> subtasks = new ArrayList<TreeTask>(node.children.size());
for (TreeNode n : node.children) {
// do some stuff
subtasks.add(new TreeTask(n,level + 1));
}
invokeAll(subtasks); // Invoke and wait for completion
} else {
//do some other processing
}
}
}
...
ForkJoinPool p = new ForkJoinPool(N_THREADS);
p.invoke(root,0);
fork / join框架的关键点是工作窃取 – 在等待子任务线程完成时执行其他任务.它允许您以直接的方式编写算法,同时避免线程耗尽的问题,作为ExecutorService的天真应用程序.