C#中的并行树遍历

Question

我需要快速遍历一棵树,我想并行完成.我宁愿使用并行扩展而不是手动旋转一堆线程.

我当前的代码看起来像这样:

   public void Traverse(Node root)
    {
        var nodeQueue = new Queue<Node>();
        nodeQueue.Enqueue(root);
        while (nodeQueue.Count!=0)
        {
            var node = nodeQueue.Dequeue();
            if (node.Property = someValue) DoSomething(node);
            foreach (var node in node.Children)
            {
                nodeQueue.Enqueue(node);
            }
        }
    }

我真的希望Parallel.ForEach有一个Parallel.While模拟.我遇到了Stephen Toub关于使用Parallel.ForEach实现Parallels Parallel的文章.如果正确读取它仍然无法工作,因为我正在改变我试图迭代的队列.

我是否需要使用任务工厂和递归(这有风险吗？)？还是有一些我忽略的简单解决方案？

编辑:@svick

该树有超过250,000个节点.现在最大深度是14个节点,包括根.

根目录下有大约500个节点,之后的平衡具有相当随机的分布.我很快就会得到更好的分布统计数据.

@Enigmativity:

是的,许多用户同时修改了树,但我通常会为树或子树提供共​​享读锁,或允许脏读.

对node.Children的调用可以被认为是原子的.

DoSomething实际上是几个代理之一,对于一些昂贵的操作,我可能会收集节点的快照列表并在遍历之外处理它们.

我意识到我应该看一般情况(遍历的子树而不是整个树.)为此,我在树的每个节点上运行遍历并查看总时间.

我为每个遍历算法使用了Parallel.ForEach(nodes,Traverse),其中节点包含所有~250k节点.这模拟(某种程度上)许多用户同时请求许多不同的节点.

00256ms广度优先顺序

00323ms广度优先连续工作(我将静态计数器增加为"工作")

01495ms Kirks第一个回答

01143ms Svicks第二个答案

00000ms Recursive Single Threaded在60s后没有完成

00000ms电子书的答案在60年代后没有完成

@Enigma,我想我可能会以某种方式搞砸你的算法,因为它似乎应该更快.

结果令我惊讶的是至少可以说.为了让自己相信编译器并没有神奇地优化遍历,我不得不在广度第一顺序中添加一些工作.

对于头部的单次遍历,并行化第一级仅具有最佳性能.但几乎没有,这个数字有所改善,因为我向第二级添加了更多节点(2000而不是500).

Answer 1

最直接的方法是Task为每个子节点创建一个,然后等待所有子节点:

public void Traverse(Node root)
{
    if (node.Property == someValue)
        DoSomething(node);

    var tasks = new List<Task>();

    foreach (var node in node.Children)
    {
        // tmp is necessary because of the way closures close over loop variables
        var tmp = node;
        tasks.Add(Task.Factory.StartNew(() => Traverse(tmp)));
    }

    Task.WaitAll(tasks.ToArray());
}

Task重量相当轻,因此创造很多它们的效果相当不错.但它们确实有一些开销,所以做一些更复杂的事情就像拥有一些共享队列的任务一样可能会更快.如果这是你要去的方式,不要忘记空队列并不意味着所有工作都已完成.System.Collections.Concurrent如果你采用这种方式,命名空间中的类将会派上用场.

编辑:由于树的形状(根有大约500个孩子),并行处理第一级应该提供良好的性能:

public void Traverse(Node root, bool parallel = true)
{
    if (node.Property == someValue)
        DoSomething(node);

    if (parallel)
    {
        Parallel.ForEach(node.Children, node =>
        {
            Traverse(node, false);
        });
    }
    else
    {
        foreach (var node in node.Children)
        {
            Traverse(node, false);
        }
    }
}