Recorrido eficiente de gráficos con LINQ - eliminando la recursión

Question

Hoy iba a implementar un método para atravesar un gráfico arbitrariamente profundo y aplanarlo en un solo enumerable. En su lugar, hice un poco de búsqueda primero y encontré esto:

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

En teoría esto se ve bien, pero en la práctica lo he encontrado funciona claramente peor que el uso de código escrito a mano equivalente (según sea la situación) pasar por un gráfico y hacer lo que sea necesario hacer. Sospecho que esto se debe a que en este método, por cada elemento que devuelve, la pila debe relajarse a un nivel arbitrariamente profundo.

También sospecho que este método funcionaría mucho más eficientemente si se eliminara la recursión. Además, no soy muy bueno para eliminar la recursión.

¿Alguien sabe cómo reescribir este método para eliminar la recursión?

Gracias por cualquier ayuda.

EDIT: Muchas gracias por todas las respuestas detalladas. Intenté comparar la solución original con la de Eric versus la de no usar un método de enumerador y, en lugar de eso, atravesar recursivamente con a lambda y, curiosamente, la recursión lambda es significativamente más rápida que cualquiera de los otros dos métodos.

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

Dónde TraverseOld es el método original, TraverseNew es el método de Eric, y obviamente el lambda es la lambda.

En mi máquina, TraverseOld lleva 10127 ms, TraverseNew tarda 3038 ms, la recursión lambda tarda 1181 ms.

¿Es típico que los métodos del enumerador (con retorno de rendimiento) pueden tomar 3 veces más tiempo que la ejecución inmediata? ¿O algo más está pasando aquí?

Answer 1

En primer lugar, que esté absolutamente correcta; si el gráfico tiene n nodos de profundidad media d, entonces los iteradores anidados ingenuos producen una solución que es O (n * d) en el tiempo y O (d) en la pila. Si d es una gran fracción de n, esto puede convertirse en un algoritmo O (n), y si d es grande, entonces puede volar la pila por completo.

Si usted está interesado en un análisis del rendimiento de los iteradores anidados, ver el blog de ex desarrollador compilador de C# Wes Dyer: solución

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

de dasblinkenlight es una variación en el método estándar. normalmente me gustaría escribir el programa como este:

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

Y entonces, si usted tiene múltiples raíces:

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

Ahora, tenga en cuenta que un recorrido es no lo que quiere si tiene una muy interconectado gráfico o un gráfico cíclico! Si tiene un gráfico con flechas apuntando hacia abajo:

  A 
     /\ 
     B-->C 
     \/
      D 

continuación, el recorrido es A, B, D, C, D, C, D. Si tiene un gráfico cíclico o interconectado a continuación, lo que quiere es la cierre transitivo.

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

Esta variación solo produce elementos que no han sido cedidos antes.

También sucede que no soy muy bueno eliminando la recursión.

He escrito una serie de artículos sobre cómo eliminar la recursividad y sobre la programación recursiva en general. Si este tema le interesa, ver:

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

En particular:

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

Puede usar una cola en su código. La cola se puede inicializar como una lista con un elemento igual al nodo superior. Luego debe iterar a través de cada elemento de la lista comenzando desde el primero. Si el primer elemento contiene nodos secundarios, los agrega al final de la cola. Luego pasa al siguiente elemento. Su gráfico se aplanará por completo cuando llegue al final de la cola.

Answer 3

Siempre puede eliminar la recursión replicando los conceptos básicos de cómo funciona la recursión con una pila.

1. lugar el primer punto de la parte superior de la pila
2. Mientras que la pila no está vacía, sacar un item de la pila
3. si el nodo actual tiene hijos, añadirlos a la pila
4. Rendimiento devuelve el artículo actual.
5. ¡Vaya al paso 1!

loco inteligente respuesta teórica: https://stackoverflow.com/a/933979/29093

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

Answer 4

tiene usted razón, caminando árboles y gráficos de forma recursiva en el código que hace yield return es una gran fuente de ineficiencia.

En general, reescribe el código recursivo con una pila, de forma similar a como se implementa generalmente en el código compilado.

No he tenido la oportunidad de probarlo, pero esto debería funcionar:

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