Rendimiento del rendimiento nested en un árbol

Tengo una estructura similar a un árbol. Cada elemento en esta estructura debería poder devolver un Enumerable de todos los elementos a los que es root. Llamemos a este método IEnumerable GetAll() . Entonces si tenemos

  A <-- topmost root / \ BC / \ / \ DEFG 

una llamada a GetAll en el elemento C devuelve {C, F, G} (el orden fijo de los elementos sería bueno, pero no es necesario). Supongo que todos ya lo sabían.

La implementación actual de GetAll ve así:

 public IEnumerable GetAll () { yield return this; foreach (Foo foo in MyChildren) { foreach (Foo f in foo.GetAll ()) { yield return f; } } } 

En una implementación anterior, devolví una lista y agregué los child-foos usando List.AddRange() .

Mi pregunta es si la versión que usa rendimiento se implementa correctamente o si se debe mejorar (especialmente en términos de rendimiento). ¿O es esto simplemente malo y debería seguir con List s (o ReadOnlyCollections ) en su lugar?

Ciertamente, no es ideal en términos de rendimiento: terminas creando muchos iteradores para árboles grandes, en lugar de un único iterador que sabe cómo atravesar de manera eficiente.

Algunas entradas de blog relacionadas con esto:

  • Wes Dyer: Todo sobre iteradores
  • Eric Lippert: Inmutabilidad en C #, parte 6
  • Eric otra vez: inmutabilidad en C #, parte 7

Vale la pena señalar que F # tiene el equivalente del ” yield foreach ” propuesto con ” yield! “.

Puede mejorar el rendimiento si desenrolla el recurse en la stack, por lo que tendrá solo un iterador:

 public IEnumerable GetAll() { Stack FooStack = new Stack(); FooStack.Push(this); while (FooStack.Count > 0) { Foo Result = FooStack.Pop(); yield return Result; foreach (Foo NextFoo in Result.MyChildren) FooStack.Push(NextFoo); } } 

Una mejor solución podría ser crear un método de visita que atraviese recursivamente el árbol y usarlo para recoger elementos.

Algo como esto (asumiendo un árbol binario):

 public class Node { public void Visit(Action action) { action(this); left.Visit(action); right.Visit(action); } public IEnumerable GetAll () { var result = new List(); Visit( n => result.Add(n)); return result; } } 

Tomando este enfoque

  • Evita la creación de grandes números de iteradores nesteds
  • Evita crear más listas de las necesarias
  • Es relativamente eficiente
  • Se cae si solo necesita una parte de la lista regularmente

No, eso se ve bien.

Eche un vistazo a mi entrada de blog , puede ser de alguna utilidad 🙂

Según mis experiencias anteriores, usar rendimiento es mucho más efectivo que crear una lista. Si está usando .NET 3.5, esta implementación debería estar bien. Pero no olvides

 yield break; 

Al final. 🙂