java – 一起进行多线程和递归

发布时间：2020-12-15 02:49:45 所属栏目：Java 来源：网络整理

导读：我有递归代码,以深度优先的方式处理树结构.代码基本上如下所示： function(TreeNode curr) { if (curr.children != null !curr.children.isEmpty()) { for (TreeNode n : curr.children) { //do some stuff function(n); } } else { //do some other process

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

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的天真应用程序.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!