Recorrido eficiente del gráfico con LINQ – eliminando la recursión

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 Traverse(this IEnumerable enumerable, Func<T, IEnumerable> recursivePropertySelector) { foreach (T item in enumerable) { yield return item; IEnumerable 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 he encontrado que su desempeño es significativamente más deficiente que el uso de un código escrito a mano equivalente (a medida que se presenta la situación) para recorrer un gráfico y hacer lo que sea necesario. Sospecho que esto se debe a que, en este método, para cada elemento que devuelve, la stack tiene que desenrollarse a un nivel arbitrariamente profundo.

También sospecho que este método se ejecutaría de manera mucho más eficiente si se eliminara la recursión. También resulta que no soy muy bueno eliminando 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. He intentado realizar una evaluación comparativa de la solución original frente a la solución de Eric frente a no usar un método de enumerador y, en cambio, atravesar recursivamente con aa lambda y, curiosamente, la repetición de lambda es significativamente más rápida que cualquiera de los otros dos métodos.

 class Node { public List ChildNodes { get; set; } public Node() { ChildNodes = new List(); } } class Foo { public static void Main(String[] args) { var nodes = new List(); 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  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 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; } } 

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

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

¿Es esto típico que los métodos de enumerador (con rendimiento) pueden demorar 3 veces mientras se oponga a la ejecución inmediata? ¿O está pasando algo más aquí?

En primer lugar, usted es absolutamente correcto; Si la gráfica tiene n nodos de profundidad media d, los iteradores nesteds no generados producen una solución que es O (n * d) en el tiempo y O (d) en la stack. Si d es una gran fracción de n, entonces esto puede convertirse en un algoritmo O (n 2 ), y si d es grande, entonces puedes volar la stack por completo.

Si está interesado en un análisis de rendimiento de los iteradores nesteds, consulte la publicación del blog del anterior comstackdor de C #, Wes Dyer:

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

La solución de dasblinkenlight es una variación del enfoque estándar. Normalmente escribiría el progtwig así:

 public static IEnumerable Traverse( T root, Func> children) { var stack = new Stack(); stack.Push(root); while(stack.Count != 0) { T item = stack.Pop(); yield return item; foreach(var child in children(item)) stack.Push(child); } } 

Y luego si tienes múltiples raíces:

 public static IEnumerable Traverse( IEnumerable roots, Func> children) { return from root in roots from item in Traverse(root, children) select item ; } 

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

  A / \ B-->C \ / D 

entonces el recorrido es A, B, D, C, D, C, D. Si tiene un gráfico cíclico o interconectado, entonces lo que desea es el cierre transitivo .

 public static IEnumerable Closure( T root, Func> children) { var seen = new HashSet(); var stack = new Stack(); 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 artículos que no han sido cedidos anteriormente.

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

He escrito una serie de artículos sobre formas de eliminar la recursión y sobre la progtwigción recursiva en general. Si este tema le interesa, vea:

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

Tienes razón, caminar árboles y gráficos de forma recursiva en el código que produce yield return es una gran fuente de ineficiencia.

En general, reescribe el código recursivo con una stack, de manera similar a la forma en que generalmente se implementa en el código comstackdo.

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

 public static IEnumerable Traverse(this IEnumerable enumerable, Func> recursivePropertySelector) { var stack = new Stack>(); 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); } } } } 

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

  1. coloca el primer elemento en la parte superior de la stack
  2. Mientras que la stack no está vacía, saca un elemento de la stack
  3. Si el nodo actual tiene hijos, agrégalos a la stack.
  4. Devuelve el artículo actual.
  5. ¡Ve al paso 1!

Respuesta teórica inteligente e inteligente: https://stackoverflow.com/a/933979/29093

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

Puedes usar una cola en tu código. La cola se puede inicializar como una lista con un elemento igual al nodo superior. Luego debes iterar a través de cada elemento de la lista a partir del primero. Si el primer elemento contiene nodos secundarios, los agrega al final de la cola. Luego pasar al siguiente elemento. Su gráfico se aplanará completamente cuando llegue al final de la cola.