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 的解决方案进行基准测试，比较不使用枚举器方法而是使用 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 倍的时间是典型的吗？还是这里发生了其他事情？

Answer 1

首先，你是绝对正确的；如果图有 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-->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);
    }
}

此变体仅产生之前未产生的项目。

I also happen to not be very good at eliminating 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/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