递归比迭代更快

Question

我已经在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;
    }
}

测试每个方法的表现后,我很惊讶地得知,迭代版本是一致且明显比递归一个慢.我已经在巨大的树木和小树上进行了测试,递归方法总是更快.(我用了一个Stopwatch标杆)
,我证实,这两种方法成功地遍历整个树和迭代版本只访问每个节点恰好一次按计划进行,所以它不是与它们之间的连接有问题.

对我来说,似乎很明显迭代版本会表现得更好......这可能是什么原因造成的？我是否忽略了一个明显的原因,为什么递归版本更快？

_{我正在使用Visual Studio 2012并在Release,Any CPU下编译(更喜欢32位未选中).}

编辑:
我已经打开了一个新项目并创建了一个简单的测试,它也证实了我的结果.
这是完整的代码:http://pastebin.com/SwAsTMjQ
代码没有注释,但我认为这是非常自我记录.

Answer 1

缓存局部性正在扼杀速度。尝试：

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%。

缓慢的原因是您的迭代算法将采用广度优先而不是深度优先。您创建了元素深度优先，因此它们在内存中按深度优先排序。我的算法创建深度优先的遍历列表。

（请注意，我使用了QueueinLinkNodes()是为了更容易理解，但实际上您也可以不使用 in）

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