递归比迭代更快

Question

递归比迭代更快

c#performancerecursioniterationcomplexity-theory

9

我在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，虽然代码没有注释，但我认为它相当容易理解。

- Acidic

1

你的测量结果在哪里？ - Tim Schmelter

@Arie看到的恰好相反，因此他才会问这个问题。在他的情况下，迭代速度较慢。 - Bart Friederichs

你如何存储“下一个”指针？当切换到下一个时，您是否更改代码以仅存储一个节点指针？ - Aleksander Fular

1

你为什么不选择与递归（深度优先）相同的方式，并拥有一个要访问的元素堆栈？在计时时，创建链表所需的额外时间占用了多少时间？ - Sylwester

@Sylwester 我在测试之前就链接了节点。在测试期间，我只进行迭代。 - Acidic

显示剩余2条评论

2个回答

0

看了你的代码，两种方法看起来都能正常工作，但是在递归方法中，你会在一个“循环”中访问4个节点，这意味着你不会在3个测试之间“跳跃”，而在迭代中，你每次运行时会“跳跃”到循环的开头。我认为如果你想看到几乎相似的行为，你需要将迭代循环展开成类似于以下的形式：

Traverse(int depth)
{
    QuadNode node = this;
    while (node != null)
    {
        // visit node

        node = node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;

    }
}

- Gar

大多数现代编译器都会执行循环展开，手动执行只会使您的代码更难阅读。 - Aleksander Fular

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- xanatos · Accepted Answer

缓存本地性正在影响速度。尝试以下方法：

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()中使用了一个队列来使其更易于理解，但事实上您也可以不用它)

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