我已经在 C# 中实现了一个四叉树,并且遇到了一个奇怪的事件,递归似乎比迭代执行得更好,尽管看起来应该相反。
我的节点是这样的:
class QuadNode
{
private QuadNode topLeft;
private QuadNode topRight;
private QuadNode bottomRight;
private QuadNode bottomLeft;
// other fields...
}
为了遍历树,我使用了以下在根节点上调用的递归方法:
Traverse()
{
// visit 'this'
if (topLeft != null)
topLeft.Traverse();
if (topRight != null)
topRight.Traverse();
if (bottomRight != null)
bottomRight.Traverse();
if (bottomLeft != null)
bottomLeft.Traverse();
}
主要是出于兴趣,我尝试创建一种遍历树的迭代方法。
我向每个节点添加了以下字段:private QuadNode next
,当我创建树时,我使用队列执行广度优先遍历,链接 next
每个节点的字段到行中的下一个节点。本质上,我从树的节点创建了一个单链表。
此时我可以使用以下方法遍历树:
Traverse()
{
QuadNode node = this;
while (node != null)
{
// visit node
node = node.next;
}
}
在测试了每种方法的性能后,我非常惊讶地发现迭代版本始终明显比递归版本慢。我已经在大树和小树上进行了测试,递归方法总是更快。 (我使用秒表
进行基准测试)
我已经确认这两种方法都成功遍历了整个树,并且迭代版本只按计划访问每个节点一次,因此它们之间的链接没有问题。
在我看来,迭代版本的性能会更好……这可能是什么原因造成的?关于为什么递归版本更快,我是否忽略了一些明显的原因?
我正在使用 Visual Studio 2012 并在 Release 下编译,任何 CPU(首选 32 位未选中)。
编辑:
我打开了一个新项目并创建了一个简单的测试,这也证实了我的结果。
这是完整的代码:http://pastebin.com/SwAsTMjQ
代码没有注释,但我认为它是非常 self 记录的。
最佳答案
缓存位置正在扼杀速度。尝试:
public void LinkNodes()
{
var queue = new Queue<QuadNode>();
LinkNodes(queue);
QuadNode curr = this;
foreach (var item in queue)
{
curr.next = item;
curr = item;
}
}
public void LinkNodes(Queue<QuadNode> queue)
{
queue.Enqueue(this);
if (topLeft != null)
topLeft.LinkNodes(queue);
if (topRight != null)
topRight.LinkNodes(queue);
if (bottomRight != null)
bottomRight.LinkNodes(queue);
if (bottomLeft != null)
bottomLeft.LinkNodes(queue);
}
现在迭代版本应该比递归版本快 30/40%。
缓慢的原因是您的迭代算法将采用广度优先而不是深度优先。您创建了元素深度优先,因此它们在内存中按深度优先排序。我的算法创建遍历列表深度优先。
(请注意,我在 LinkNodes()
中使用了一个 Queue
以使其更易于理解,但实际上您可以不这样做)
public QuadNode LinkNodes(QuadNode prev = null)
{
if (prev != null)
{
prev.next = this;
}
QuadNode curr = this;
if (topLeft != null)
curr = topLeft.LinkNodes(curr);
if (topRight != null)
curr = topRight.LinkNodes(curr);
if (bottomRight != null)
curr = bottomRight.LinkNodes(curr);
if (bottomLeft != null)
curr = bottomLeft.LinkNodes(curr);
return curr;
}
关于c# - 递归比迭代快,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18843227/