multithreading和递归一起

我有递归代码，以深度优先的方式处理树结构。 代码基本上如下所示：

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

我想使用线程来加快完成速度。 大部分时间都花在遍历上，所以我不想只创建一个线程来处理“其他处理”，因为它不需要那么长时间。 我想我想在“做一些事情”时分叉线程，但是它会如何工作？

Answer 1

对于将包含在Java 7中的Fork / Join框架来说 ，这是一个很好的例子。作为与Java 6一起使用的独立库，可以在此处下载。

像这样的东西：

 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 subtasks = new ArrayList(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的天真应用程序。

Answer 2

在// do some stuff你在单个Node上工作的// do some stuff代码块，你可以做的是将Node提交给某种ExecutorService （以Runnable的forms在Node上工作）。

您可以配置由一定数量的线程池支持的ExecutorService ，允许您从树解析中解耦“处理”逻辑（以及创建线程的逻辑，创建的数量等）逻辑。

Answer 3

此解决方案假定处理仅发生在叶节点处，并且树的实际递归不需要很长时间。

我会让调用者线程做递归，然后是通过线程池处理叶子的工人的BlockingQueue 。 我没有在这里的几个地方处理InterruptedException 。

 public void processTree(TreeNode top) { final LinkedBlockingQueue queue = new LinkedBlockingQueue(MAX_NUM_QUEUED); // create a pool that starts at 1 threads and grows to MAX_NUM_THREADS ExecutorService pool = new ThreadPoolExecutor(1, MAX_NUM_THREADS, 0L, TimeUnit.MILLISECONDS, queue, new RejectedExecutionHandler() { public void rejectedExecution(Runnable r, ThreadPoolExecutor e) { queue.put(r); // block if we run out of space in the pool } }); walkTree(top, pool); pool.shutdown(); // i think this will join with all of the threads pool.awaitTermination(WAIT_TILL_CHILDREN_FINISH_MILLIS, TimeUnit.MILLISECONDS); } private void walkTree(final TreeNode curr, ExecutorService pool) { if (curr.children == null || curr.children.isEmpty()) { pool.submit(new Runnable() { public void run() { processLeaf(curr); } }); return; } for (TreeNode child : curr.children) { walkTree(child, pool); } } private void processLeaf(TreeNode leaf) { // ... }