使用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 ms,TraverseNew需要3038 ms,lambda递归需要1181 ms.

这种典型的枚举器方法(带有yield return)可能需要3倍才能立即执行吗？或者还有其他事情发生在这里？

Answer 1

首先,你是绝对正确的; 如果图形具有n个平均深度为d的节点,那么幼稚嵌套迭代器产生的解决方案是时间为O(n*d),堆栈中为O(d).如果d是n的一小部分,那么这可以成为O(n ²)算法,如果d很大,那么你可以完全吹掉堆栈.

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

http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx

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

此变化仅产生之前未产生的项目.

我也不太擅长消除递归.

我已经写了很多关于消除递归的方法,以及一般的递归编程.如果您对此主题感兴趣,请参阅:

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

Answer 2

你是对的,在代码中递归地运行树和图,这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);
            }
        }
    }
}