c# - 使用 LINQ 进行高效的图遍历 - 消除递归

Question

今天我打算实现一种方法来遍历任意深度的图并将其展平为单个可枚举。相反，我先做了一点搜索，发现了这个：

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector)
{
    foreach (T item in enumerable)
    {
        yield return item;

        IEnumerable<T> seqRecurse = recursivePropertySelector(item);

        if (seqRecurse == null) continue;
        foreach (T itemRecurse in Traverse(seqRecurse, recursivePropertySelector))
        {
            yield return itemRecurse;
        }
    }
}

从理论上讲，这看起来不错，但在实践中，我发现它的性能比使用等效的手写代码（随着情况的出现）来遍历图表并执行任何需要做的事情要差得多。我怀疑这是因为在这种方法中，对于它返回的每个项目，堆栈都必须展开到任意深度。

我还怀疑如果消除递归，这种方法会更有效地运行。我也恰好不擅长消除递归。

有谁知道如何重写这个方法来消除递归？

谢谢你的帮助。

编辑：非常感谢所有详细的回复。我尝试对原始解决方案与 Eric 的解决方案进行基准测试，而不是使用枚举器方法，而是使用 aa lambda 递归遍历，奇怪的是，lambda 递归比其他两种方法中的任何一种都要快得多。

class Node
{
    public List<Node> ChildNodes { get; set; } 

    public Node()
    {
        ChildNodes = new List<Node>();
    }
}

class Foo
{
    public static void Main(String[] args) 
    {
        var nodes = new List<Node>();
        for(int i = 0; i < 100; i++)
        {
            var nodeA = new Node();
            nodes.Add(nodeA);
            for (int j = 0; j < 100; j++)
            {
                var nodeB = new Node();
                nodeA.ChildNodes.Add(nodeB);
                for (int k = 0; k < 100; k++)
                {
                    var nodeC = new Node();
                    nodeB.ChildNodes.Add(nodeC);
                    for(int l = 0; l < 12; l++)
                    {
                        var nodeD = new Node();
                        nodeC.ChildNodes.Add(nodeD);
                    }
                }
            }
        }            

        nodes.TraverseOld(node => node.ChildNodes).ToList();
        nodes.TraverseNew(node => node.ChildNodes).ToList();

        var watch = Stopwatch.StartNew();
        nodes.TraverseOld(node => node.ChildNodes).ToList();
        watch.Stop();
        var recursiveTraversalTime = watch.ElapsedMilliseconds;
        watch.Restart();
        nodes.TraverseNew(node => node.ChildNodes).ToList();
        watch.Stop();
        var noRecursionTraversalTime = watch.ElapsedMilliseconds;

        Action<Node> visitNode = null;
        visitNode = node =>
        {
            foreach (var child in node.ChildNodes)
                visitNode(child);
        };

        watch.Restart();
        foreach(var node in nodes)
            visitNode(node);
        watch.Stop();
        var lambdaRecursionTime = watch.ElapsedMilliseconds;
    }
}

其中 TraverseOld 是原始方法， TraverseNew 是 Eric 的方法，显然 lambda 是 lambda。

在我的机器上，TraverseOld 需要 10127 毫秒，TraverseNew 需要 3038 毫秒，lambda 递归需要 1181 毫秒。

这是典型的枚举器方法（带有收益返回）可能需要 3 倍的时间而不是立即执行吗？还是这里发生了其他事情？

score 21 · Accepted Answer

首先，您是绝对正确的；如果图有 n 个平均深度为 d 的节点，那么朴素的嵌套迭代器会产生一个时间为 O(n*d) 的解，而堆栈中的解为 O(d)。如果 d 是 n 的很大一部分，那么这可以变成 O(n ² ) 算法，如果 d 很大，那么你可以完全破坏堆栈。

如果您对嵌套迭代器的性能分析感兴趣，请参阅前 C# 编译器开发人员 Wes Dyer 的博客文章：

http://blogs.msdn.microsoft.com/wesdyer/2007/03/23/all-about-iterators

dasblinkenlight 的解决方案是标准方法的一种变体。我通常会这样编写程序：

public static IEnumerable<T> Traverse<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count != 0)
    {
        T item = stack.Pop();
        yield return item;
        foreach(var child in children(item))
            stack.Push(child);
    }
}

然后，如果您有多个根：

public static IEnumerable<T> Traverse<T>(
    IEnumerable<T> roots, 
    Func<T, IEnumerable<T>> children)
{
    return from root in roots 
           from item in Traverse(root, children)
           select item ;
}

现在，请注意，如果您有高度互连的图或循环图，则不需要遍历！如果您有一个带有向下箭头的图表：

那么遍历是 A、B、D、C、D、C、D。如果你有一个循环图或互连图，那么你想要的是传递闭包。

public static IEnumerable<T> Closure<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var seen = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(root);

    while(stack.Count != 0)
    {
        T item = stack.Pop();
        if (seen.Contains(item))
            continue;
        seen.Add(item);
        yield return item;
        foreach(var child in children(item))
            stack.Push(child);
    }
}

这种变化只会产生以前没有产生过的物品。

我也恰好不擅长消除递归。

我写了许多关于消除递归的方法以及一般的递归编程的文章。如果您对此主题感兴趣，请参阅：

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

尤其是：

http://blogs.msdn.com/b/ericlippert/archive/2005/08/01/recursion-part-two-unrolling-a-recursive-function-with-an-explicit-stack.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/04/recursion-part-three-building-a-dispatch-engine.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx

score 8 · Accepted Answer

你是对的，在代码中递归地遍历树和图yield return是效率低下的一大来源。

通常，您使用堆栈重写递归代码 - 与通常在编译代码中实现的方式类似。

我没有机会尝试一下，但这应该可行：

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector) {
    var stack = new Stack<IEnumerable<T>>();
    stack.Push(enumerable);
    while (stack.Count != 0) {
        enumerable = stack.Pop();
        foreach (T item in enumerable) {
            yield return item;
            var seqRecurse = recursivePropertySelector(item);
            if (seqRecurse != null) {
                stack.Push(seqRecurse);
            }
        }
    }
}

score 2 · Accepted Answer

您总是可以通过复制递归如何与堆栈一起工作的基础知识来消除递归。

将第一项放在栈顶
当堆栈不为空时，从堆栈中弹出一个项目
如果当前节点有子节点，则将它们添加到堆栈中
Yield 返回当前项目。
转到第 1 步！

疯狂聪明的理论答案：https ://stackoverflow.com/a/933979/29093

http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf

score 0 · Accepted Answer

您可以在代码中使用队列。队列可以初始化为一个列表，其中一个元素等于顶部节点。然后，您必须从第一个元素开始遍历列表的每个元素。如果第一个元素包含子节点，则将它们全部附加到队列的末尾。然后移动到下一个元素。当您到达队列末尾时，您的图表将完全变平。

c# - 使用 LINQ 进行高效的图遍历 - 消除递归

4 回答 4

Related

Reference