IEnumerable y recursiva utilizando rendimiento de rendimiento

307

Tengo un IEnumerable<T>método que estoy usando para buscar controles en una página de WebForms.

El método es recursivo y tengo algunos problemas para devolver el tipo que quiero cuando yield returndevuelve el valor de la llamada recursiva.

Mi código se ve de la siguiente manera:

    public static IEnumerable<Control> 
                               GetDeepControlsByType<T>(this Control control)
    {
        foreach(Control c in control.Controls)
        {
            if (c is T)
            {
                yield return c;
            }

            if(c.Controls.Count > 0)
            {
                yield return c.GetDeepControlsByType<T>();
            }
        }
    }

Esto actualmente arroja un error "No se puede convertir el tipo de expresión". Sin embargo, si este método devuelve el tipo IEnumerable<Object>, el código se construye, pero el tipo incorrecto se devuelve en la salida.

¿Hay alguna forma de usar yield returnmientras se usa también la recursividad?

Jamie Dixon
fuente
1
stackoverflow.com/questions/1815497/… : enlace a la respuesta "mrydengrens" en el hilo "¿Enumerar colecciones que no son inherentemente IEnumerable?" Su código de muestra se basa en un artículo de blog de Eric Lippert que le muestra cómo usar pilas en la enumeración recursiva con Linq, evitando así el uso de memoria posiblemente costoso por los iteradores. En mi humilde opinión muy útil!
BillW
Por cierto. if(c.Controls.Count > 0)-> if(c.Controls.Any()), especialmente si también estás cediendo :)
tymtam
No creo que este caso se beneficie del rendimiento. Para completar, proporcioné una implementación sin yield. Por favor, vea a continuación :) Y también es una
frase
Debe tener cuidado de evitar yield returnen las funciones recursivas, el uso de la memoria aumenta de forma explosiva. Ver stackoverflow.com/a/30300257/284795
Coronel Panic

Respuestas:

485

Dentro de un método que regresa IEnumerable<T>, yield returntiene que regresar T, no un IEnumerable<T>.

Reemplazar

yield return c.GetDeepControlsByType<T>();

con:

foreach (var x in c.GetDeepControlsByType<T>())
{
  yield return x;
}
Marcin Seredynski
fuente
98

Debe entregar cada uno de los elementos producidos por la llamada recursiva:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach(Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if(c.Controls.Count > 0)
        {
            foreach (Control control in c.GetDeepControlsByType<T>())
            {
                yield return control;
            }
        }
    }
}

Tenga en cuenta que hay un costo para recurrir de esta manera: terminará creando muchos iteradores, lo que puede crear un problema de rendimiento si tiene un árbol de control realmente profundo. Si desea evitar eso, básicamente necesita hacer la recursión usted mismo dentro del método, para asegurarse de que solo se haya creado un iterador (máquina de estado). Consulte esta pregunta para obtener más detalles y una implementación de muestra, pero esto obviamente también agrega una cierta cantidad de complejidad.

Jon Skeet
fuente
2
Me parece sorprendente que en un hilo sobre ceder Jon no haya mencionado c.Controls.Count > 0vs. .Any():)
tymtam
@Tymek en realidad se menciona en la respuesta vinculada.
28

Como Jon Skeet y el coronel Panic señalan en sus respuestas, el uso yield returnde métodos recursivos puede causar problemas de rendimiento si el árbol es muy profundo.

Aquí hay un método genérico de extensión no recursiva que realiza un recorrido en profundidad de una secuencia de árboles:

public static IEnumerable<TSource> RecursiveSelect<TSource>(
    this IEnumerable<TSource> source, Func<TSource, IEnumerable<TSource>> childSelector)
{
    var stack = new Stack<IEnumerator<TSource>>();
    var enumerator = source.GetEnumerator();

    try
    {
        while (true)
        {
            if (enumerator.MoveNext())
            {
                TSource element = enumerator.Current;
                yield return element;

                stack.Push(enumerator);
                enumerator = childSelector(element).GetEnumerator();
            }
            else if (stack.Count > 0)
            {
                enumerator.Dispose();
                enumerator = stack.Pop();
            }
            else
            {
                yield break;
            }
        }
    }
    finally
    {
        enumerator.Dispose();

        while (stack.Count > 0) // Clean up in case of an exception.
        {
            enumerator = stack.Pop();
            enumerator.Dispose();
        }
    }
}

A diferencia de la solución de Eric Lippert , RecursiveSelect trabaja directamente con los enumeradores, por lo que no necesita llamar a Reverse (que almacena la secuencia completa en la memoria).

Usando RecursiveSelect, el método original del OP se puede reescribir simplemente así:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    return control.Controls.RecursiveSelect(c => c.Controls).Where(c => c is T);
}
Michael Liu
fuente
Para que este código (excelente) funcione, tuve que usar 'OfType para obtener ControlCollection en forma IEnumerable; en Windows Forms, una ControlCollection no es enumerable: return control.Controls.OfType <Control> () .RecursiveSelect <Control> (c => c.Controls.OfType <Control> ()) .Where (c => c es T );
BillW
17

Otros le proporcionaron la respuesta correcta, pero no creo que su caso se beneficie con el rendimiento.

Aquí hay un fragmento que logra lo mismo sin ceder.

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
   return control.Controls
                 .Where(c => c is T)
                 .Concat(control.Controls
                                .SelectMany(c =>c.GetDeepControlsByType<T>()));
}
tymtam
fuente
2
¿No usa LINQ yieldtambién? ;)
Philipp M
Esto es resbaladizo. Siempre me ha molestado el foreachbucle adicional . ¡Ahora puedo hacer esto con programación funcional pura!
jsuddsjr
1
Me gusta esta solución en términos de legibilidad, pero enfrenta el mismo problema de rendimiento con los iteradores que con el rendimiento. @PhilippM: Verificado que LINQ utiliza el rendimiento referencesource.microsoft.com/System.Core/R/…
Herman
Pulgar para una gran solución.
Tomer W
12

Debe devolver los elementos del enumerador, no del enumerador en sí, en su segundoyield return

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach (Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if (c.Controls.Count > 0)
        {
            foreach (Control ctrl in c.GetDeepControlsByType<T>())
            {
                yield return ctrl;
            }
        }
    }
}
Rob Levine
fuente
9

Creo que debe devolver cada uno de los controles en los enumerables.

    public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
    {
        foreach (Control c in control.Controls)
        {
            if (c is T)
            {
                yield return c;
            }

            if (c.Controls.Count > 0)
            {
                foreach (Control childControl in c.GetDeepControlsByType<T>())
                {
                    yield return childControl;
                }
            }
        }
    }
Torbjörn Hansson
fuente
8

La sintaxis de Seredynski es correcta, pero debe tener cuidado de evitarla yield returnen las funciones recursivas porque es un desastre para el uso de la memoria. Consulte https://stackoverflow.com/a/3970171/284795 que escala explosivamente con la profundidad (una función similar estaba usando el 10% de la memoria en mi aplicación).

Una solución simple es usar una lista y pasarla con la recursión https://codereview.stackexchange.com/a/5651/754

/// <summary>
/// Append the descendents of tree to the given list.
/// </summary>
private void AppendDescendents(Tree tree, List<Tree> descendents)
{
    foreach (var child in tree.Children)
    {
        descendents.Add(child);
        AppendDescendents(child, descendents);
    }
}

Alternativamente, puede usar una pila y un ciclo while para eliminar las llamadas recursivas https://codereview.stackexchange.com/a/5661/754

Coronel Panic
fuente
0

Si bien hay muchas buenas respuestas, todavía agregaría que es posible usar métodos LINQ para lograr lo mismo,.

Por ejemplo, el código original del OP podría reescribirse como:

public static IEnumerable<Control> 
                           GetDeepControlsByType<T>(this Control control)
{
   return control.Controls.OfType<T>()
          .Union(control.Controls.SelectMany(c => c.GetDeepControlsByType<T>()));        
}
Yoel Halb
fuente
Hace tres años se publicó una solución que utiliza ese mismo enfoque .
Servy
@Servy Aunque es similar (que por cierto me perdí entre todas las respuestas ... mientras escribía esta respuesta), sigue siendo diferente, ya que utiliza .OfType <> para filtrar, y .Union ()
yoel halb
2
El OfTypeno es realmente un significado diferente. A lo sumo un pequeño cambio realista. Un control no puede ser hijo de controles múltiples, por lo que el árbol atravesado ya no es obligatorio. Usar en Unionlugar de Concates verificar innecesariamente la unicidad de una secuencia que ya se garantiza que es única y, por lo tanto, es una degradación objetiva.
Servy