相关疑难解决方法(0)

C#中的并行树遍历

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

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

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

Run Code Online (Sandbox Code Playgroud)

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

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

编辑:@svick

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

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

@Enigmativity:

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

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

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

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

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