Эффективный обход графов с помощью 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;
        }
    }
}

Теоретически это выглядит хорошо, но на практике я обнаружил, что он работает значительно хуже, чем использование эквивалентного рукописного кода (при возникновении ситуации) для прохождения графа и выполнения всего, что нужно сделать. Я подозреваю, что это связано с тем, что в этом методе для каждого элемента, который он возвращает, стек должен развернуться до некоторого произвольно глубокого уровня.

Я также подозреваю, что этот метод будет работать намного эффективнее, если рекурсия будет устранена. Я также не очень хорош в устранении рекурсии.

Кто-нибудь знает, как переписать этот метод, чтобы устранить рекурсию?

Спасибо за любую помощь.

РЕДАКТИРОВАТЬ: Большое спасибо за все подробные ответы. Я попытался сравнить исходное решение с решением Эрика, не используя метод перечислителя и вместо этого рекурсивно обходить с помощью лямбды и, как ни странно, лямбда-рекурсия значительно быстрее, чем любой из двух других методов.

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 - метод Эрика, и, очевидно, лямбда - это лямбда.

На моей машине TraverseOld занимает 10127 мс, TraverseNew - 3038 мс, лямбда-рекурсия - 1181 мс.

Типично ли, что методы перечислителя (с возвращаемым доходом) могут занимать 3 раза дольше, чем немедленное выполнение? Или здесь что-то еще происходит?

4 ответа

Решение

Во-первых, вы абсолютно правы; если в графе имеется n узлов средней глубины d, то наивные вложенные итераторы дают решение, которое по времени равно O(n*d), а по стеку - O(d). Если d - большая доля n, то это может стать алгоритмом O (n2), а если d велико, то вы можете полностью удалить стек.

Если вы заинтересованы в анализе производительности вложенных итераторов, посмотрите сообщение в блоге бывшего разработчика компилятора C# Уэса Дайера:

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

Вы правы, ходя по деревьям и графикам рекурсивно в коде, который делает 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);
            }
        }
    }
}

Вы всегда можете устранить рекурсию, воспроизведя основы работы рекурсии со стеком.

  1. поместите первый предмет на вершину стека
  2. Пока стек не пуст, вытолкнуть предмет из стека
  3. если у текущего узла есть дети, добавьте их в стек
  4. Урожай возвращает текущий товар.
  5. Переходите к шагу 1!

Сумасшедший умный теоретический ответ: /questions/8246522/mozhet-li-kazhdaya-rekursiya-byit-preobrazovana-v-iteratsiyu/8246551#8246551

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

Вы можете использовать очередь в своем коде. Очередь может быть инициализирована как список с одним элементом, равным верхнему узлу. Затем вы должны перебирать каждый элемент списка, начиная с первого. Если первый элемент содержит дочерние узлы, вы добавляете их все в конец очереди. Затем перейдите к следующему элементу. Ваш график будет полностью сплющен, когда вы достигнете конца очереди.

Другие вопросы по тегам