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

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

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 的解决方案进行基准测试，对比不使用枚举器方法而是使用 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 毫秒。

与立即执行相比，枚举器方法（带有yield 返回）花费的时间是通常的 3 倍，这是典型的情况吗？还是这里发生了其他事情？

First off, you are absolutely correct; if the graph has n nodes of average depth d then the naive nested iterators yield a solution which is O(n*d) in time, and O(d) in stack. If d is a large fraction of n then this can become an O(n²) algorithm, and if d is large then you can blow the stack entirely.

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

http://blogs.msdn.microsoft.com/wesdyer/2007/03/23/all-about-iterators 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 ;
}

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

          A
         / \
        B-->C
         \ /
          D

那么遍历是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/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/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/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 http://blogs.msdn.com/b/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx