多线程和递归一起 [英] Multithreading and recursion together
问题描述
我有递归代码,以深度优先的方式处理树结构。代码基本上如下所示:
I have recursive code that processes a tree structure in a depth first manner. The code basically looks like this:
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
}
}
我想使用线程来加快完成速度。大部分时间都花在遍历上,所以我不想只创建一个线程来处理其他处理,因为它不需要那么长时间。我想我想在做一些事情时分叉线程,但是如何工作?
I want to use threads to make this complete faster. Most of the time is spent traversing so I don't want to just create a thread to handle "the other processing" because it doesn't take that long. I think I want to fork threads at "do some stuff" but how would that work?
推荐答案
这是一个很好的案例< a href =http://download.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html\"rel =noreferrer> Fork / Join框架,它将包含在Java 7中。可以从这里下载用于Java 6的独立库。 。
It's a good case for Fork/Join framework which is to be included into Java 7. As a standalone library for use with Java 6 it can be downloaded 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框架的关键点是工作窃取 - 在等待子任务完成时线程执行其他任务。它允许您以直接的方式编写算法,同时避免线程耗尽的问题作为一个天真的apporach与 ExecutorService
将有。
The key point of fork/join framework is work stealing - while waiting for completion of subtasks thread executes other tasks. It allows you to write algorithm in straightforward way, while avoiding problems with thread exhausting as a naive apporach with ExecutorService
would have.
这篇关于多线程和递归一起的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!