c# - que - IEnumerable y Recursion usando rendimiento de rendimiento.

yield return c# stack overflow

Question

Tengo un IEnumerable<T> que estoy usando para encontrar controles en una página de formularios web.

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

Mi código se ve como sigue:

    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 produce actualmente 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 genera, pero el tipo incorrecto se devuelve en la salida.

¿Hay alguna forma de utilizar la yield return cuando se usa también la recursión?

Answer 1

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

Aquí hay un método de extensión no recursivo genérico que realiza un recorrido primero 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 para que no tenga que llamar Reverse (que almacena toda la secuencia 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);
}

Answer 2

Creo que tienes que 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;
                }
            }
        }
    }

Answer 3

Debe ceder cada uno de los elementos generados 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 por 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 dentro del método, para asegurarse de que solo se haya creado un iterador (máquina de estado). Vea esta pregunta para obtener más detalles y una implementación de muestra, pero esto obviamente también agrega cierta complejidad.

Answer 4

Debe devolver los elementos del enumerador, no del propio enumerador, en su segundo yield 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;
            }
        }
    }
}

Answer 5

Dentro de un método que devuelve IEnumerable<T> , el yield return debe devolver T , no un IEnumerable<T> .

Reemplazar

yield return c.GetDeepControlsByType<T>();

con:

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

Answer 6

Otros le proporcionaron la respuesta correcta, pero no creo que su caso se beneficie del 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>()));
}

Answer 7

Si bien hay muchas respuestas buenas por ahí, 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>()));        
}

Answer 8

La sintaxis de Seredynski es correcta, pero debe tener cuidado de evitar el yield return en las funciones recursivas porque es un desastre para el uso de la memoria. Ver https://.com/a/3970171/284795 se escala de forma explosiva 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 bucle while para eliminar llamadas recursivas https://codereview.stackexchange.com/a/5661/754