递归中的任务

本文关键字：任务 递归 | 更新日期: 2023-09-27 18:01:31

我有一个递归遍历二叉树的函数。由于操作是计算密集型的，我认为在递归函数中使用任务生成多个线程，如下所示:

static void Traverse<T>(Tree<T> node, Action<T> action) 
{ 
 if (node == null) return; 
 var t1 = Task.Factory.StartNew(() => action(node.Data)); 
 var t2 = Task.Factory.StartNew(() => Traverse(node.Left, action)); 
 var t3 = Task.Factory.StartNew(() => Traverse(node.Right, action)); 
 Task.WaitAll(t1, t2, t3); 
}

现在这似乎确实有效。然而，我想知道在以递归方式使用任务时是否有什么需要注意的地方。例如，如果树的深度很长，它可能无法为较低级别创建任务并等待其他任务完成(这些任务永远不会完成，因为它们正在等待较低级别任务完成)?

递归中的任务

如果树非常大，产生那么多的任务可能会导致完全耗尽整个线程池的问题，从而导致其他地方的性能问题，这是因为节点与其父节点之间没有依赖关系，因此所有节点都将尝试并发运行。我要做的是让你的Tree<T>类实现IEnumerable<T>它将返回它自己的Data属性以及它所有子类的Data属性然后使用Parallel.ForEach 

static void Traverse<T>(Tree<T> node, Action<T> action) 
{
    Parallel.ForEach(node, action);
}

//Elsewhere
class Tree<T> : IEnumerable<T>
{
    Tree<T> Left { get; set; }
    Tree<T> Right { get; set; } 
    T Data { get; set; }
    public IEnumerator<T> GetEnumerator()
    {
        yield return this.Data;
        if (Left != null)
        {
            foreach (var left in Left)
            {
                yield return left.Data;
            }
        }
        if (Right != null)
        {
            foreach (var right in Right)
            {
                yield return right.Data;
            }
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

你唯一需要关注的问题是，树中是否存在任何闭合循环，其中子节点可能是更高级别节点的父节点，这会导致无限递归。

EDIT:这是一个新版本，不使用GetEnumerator递归，而是使用Stack<Tree<T>>对象来保持状态，所以如果你有非常高树，你就不能有StackOverflowException。此外，如果您从注释行中删除注释，它将停止以前版本所存在的"无限递归"问题。但是如果你知道你不会有任何循环结构，这是没有必要的，所以我把它注释掉了。

class Tree<T> : IEnumerable<T>
{
    Tree<T> Left { get; set; }
    Tree<T> Right { get; set; }
    T Data { get; set; }
    public IEnumerator<T> GetEnumerator()
    {
        Stack<Tree<T>> items = new Stack<Tree<T>>();
        //HashSet<Tree<T>> recursiveCheck = new HashSet<Tree<T>>();
        items.Push(this);
        //recursiveCheck.Add(this);
        while (items.Count > 0)
        {
            var current = items.Pop();
            yield return current.Data;
            if (current.Left != null)
                //if(recursiveCheck.Add(current.Left))
                    items.Push(current.Left);
            if (current.Right != null)
                //if (recursiveCheck.Add(current.Right))
                    items.Push(current.Right);
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

就像你说的，递归地生成线程似乎不是一个好主意，如果你的树足够长，你最终会得到很多线程，这将是较慢的，因为会有很多开销，或者你最终会达到并行线程在你的程序的限制。所以我建议你使用ThreadPool来管理你的线程。

您可能有一个线程来导航树，另外两个线程来完成繁重的工作。您还应该注意，使用线程并不好，除非您有一些阻塞操作，如I/O读/写或一些网络正在进行。如果不这样做，最好只使用一个线程来处理繁重的工作，另一个线程用于遍历树。

我不认为它会在任何时候停止工作，但是使用多线程会增加CPU使用率，因为计算机一次做更多的操作，所以它可能更安全，但更慢，不使用多线程，只使用以下命令:

static void Traverse<T>(Tree<T> node, Action<T> action)
{
 if (node == null) return;
 action(node);
 Traverse(node.Left, action);
 Traverse(node.Right, action);
}

这会比较慢，所以如果你担心它运行得有多快，你会想使用你的原始版本。

相关文章：