c# - Eficaz recorrido de gráficos con LINQ-eliminando la recursión
.net recursion (4)
En primer lugar, tienes toda la razón; 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 2 ), y si d es grande, entonces puedes volar la pila por completo.
Si está interesado en un análisis de rendimiento de iteradores anidados, consulte la publicación de blog anterior del desarrollador del compilador 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 programa así:
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 luego si tienes 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 cruce no es lo que desea 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
luego, el recorrido es A, B, D, C, D, C, D. Si tiene un gráfico cíclico o interconectado, lo que quiere es el 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.
Además, no soy muy bueno para eliminar la recursión.
He escrito varios artículos sobre cómo eliminar la recursión y sobre la programación recursiva en general. Si este tema le interesa, vea:
http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/
En particular:
Hoy iba a implementar un método para atravesar un gráfico arbitrariamente profundo y aplanarlo en un solo enumerable. En cambio, 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 he descubierto que tiene un rendimiento mucho peor que el uso de un código escrito a mano equivalente (según surja la situación) para 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.
EDITAR: Muchas gracias por todas las respuestas detalladas. Intenté comparar la solución original versus la solución de Eric versus no usar un método de enumerador y, en cambio, 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;
}
}
Donde TraverseOld es el método original, TraverseNew es el método de Eric, y obviamente el lambda es el lambda.
En mi máquina, TraverseOld toma 10127 ms, TraverseNew toma 3038 ms, la recursión lambda demora 1181 ms.
¿Es típico que los métodos del enumerador (con retorno de rendimiento) puedan tomar 3 veces más que la ejecución inmediata? ¿O algo más está pasando aquí?
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.
Tienes razón, caminar árboles y gráficos de forma recursiva en un código que produce yield return es una gran fuente de ineficiencia.
En general, reescribe el código recursivo con una pila, de forma similar a cómo se implementa generalmente en el código compilado.
No tuve 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);
}
}
}
}
Siempre puede eliminar la recursión al replicar los conceptos básicos de cómo funciona la recursión con una pila.
- coloca el primer elemento en la parte superior de la pila
- Mientras que la pila no está vacía, saca un elemento de la pila
- si el nodo actual tiene hijos, agréguelos a la pila
- Rendimiento devuelve el artículo actual.
- ¡Ve al paso 1!
Respuesta teórica inteligente loca: https://.com/a/933979/29093
http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf