我需要快速遍历一棵树,我想并行完成.我宁愿使用并行扩展而不是手动旋转一堆线程.
我当前的代码看起来像这样:
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).
我有一个接受Enumerable的函数.我需要确保对枚举数进行评估,但是如果它在List或其他"冻结"集合中已经准备就绪,我宁愿不创建它的副本(例如,通过ToList()或ToArray()).冻结我指的是已经建立了一组项目的集合,例如List,Array,FsharpSet,Collection等,而不是像Select()和where()这样的linq.
是否有可能创建一个函数"ForceEvaluation",可以确定枚举是否已将执行挂起,然后评估可枚举？
public void Process(IEnumerable<Foo> foos)
{
IEnumerable<Foo> evalutedFoos = ForceEvaluation(foos)
EnterLockedMode(); // all the deferred processing needs to have been done before this line.
foreach (Foo foo in foos)
{
Bar(foo);
}
}
public IEnumerable ForceEvaluation(IEnumerable<Foo> foos)
{
if(??????)
{ return foos}
else
{return foos.ToList()}
}
}
经过一些研究后,我意识到这在任何实际意义上都是不可能的,并且需要对每个迭代器进行复杂的代码检查.
所以我将使用Mark的答案的变体并创建一个已知安全类型的白名单,并且只需调用ToList()不在白名单上的任何内容.
感谢大家的帮助.
编辑*经过更多的反思,我意识到这相当于停止问题.所以非常不可能.
我一直在努力构建一个简单的3D图形引擎,我正在尝试找到一个好的基于整数的线光栅化算法.(我不是想重新发明轮子,我试图更深入地了解轮子).
是否有任何线光栅化算法不依赖于任何浮点数学？
谢谢.
这就是它.我不需要旧石器时代的高精度,但我希望能够代表这些日期而不会跳过太多的箍.