IEnumerable e Recursion usando retorno de rendimento

307

Eu tenho um IEnumerable<T>método que estou usando para encontrar controles em uma página WebForms.

O método é recursivo e estou tendo alguns problemas para retornar o tipo desejado quando o yield returnretorno é o valor da chamada recursiva.

Meu código é o seguinte:

    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>();
            }
        }
    }

No momento, isso gera um erro "Não é possível converter o tipo de expressão". Se, no entanto, esse método retornar tipo IEnumerable<Object>, o código será gerado, mas o tipo errado será retornado na saída.

Existe uma maneira de usar yield returnenquanto também usa recursão?

Jamie Dixon
fonte
1
stackoverflow.com/questions/1815497/… : link para a resposta "mrydengrens" no segmento "Enumerando coleções que não são inerentemente IEnumerable?" Seu código de exemplo é baseado em um artigo de blog de Eric Lippert, mostrando como usar pilhas na enumeração recursiva com o Linq, evitando assim o uso de memória possivelmente caro pelos iteradores. imho muito útil!
BillW
Entre. if(c.Controls.Count > 0)-> if(c.Controls.Any()), especialmente se você está rendendo bem :)
tymtam
Eu não acho que este caso se beneficie de ceder. Para completar, forneci uma implementação sem yield. Por favor, veja abaixo :) E é um one-liner também :)
tymtam
Você deve ter cuidado para evitar yield returnem funções recursivas, o uso da memória aumenta de forma explosiva. Veja stackoverflow.com/a/30300257/284795
Coronel Panic

Respostas:

485

Dentro de um método que retorna IEnumerable<T>, yield returntem que retornar T, não um IEnumerable<T>.

Substituir

yield return c.GetDeepControlsByType<T>();

com:

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

Você precisa produzir cada um dos itens gerados pela chamada 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;
            }
        }
    }
}

Observe que há um custo para se repetir dessa maneira - você acabará criando muitos iteradores, o que pode criar um problema de desempenho se você tiver uma árvore de controle realmente profunda. Se você deseja evitar isso, basicamente precisa fazer a recursão dentro do método, para garantir que haja apenas um iterador (máquina de estado) criado. Veja esta pergunta para obter mais detalhes e uma implementação de amostra - mas isso obviamente também adiciona uma certa complexidade.

Jon Skeet
fonte
2
Acho que é surpreendente que, em uma discussão sobre rendendo Jon não mencionou c.Controls.Count > 0vs. .Any():)
tymtam
@ Tymek, na verdade, é mencionado na resposta vinculada.
28

Como Jon Skeet e Coronel Panic observam em suas respostas, o uso de yield returnmétodos recursivos pode causar problemas de desempenho se a árvore for muito profunda.

Aqui está um método genérico de extensão não recursiva que executa uma travessia profunda de uma sequência de árvores:

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();
        }
    }
}

Diferentemente da solução de Eric Lippert , o RecursiveSelect trabalha diretamente com enumeradores para que não precise chamar Reverse (que armazena em buffer toda a sequência na memória).

Usando RecursiveSelect, o método original do OP pode ser reescrito da seguinte maneira:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    return control.Controls.RecursiveSelect(c => c.Controls).Where(c => c is T);
}
Michael Liu
fonte
Para que esse código (excelente) funcione, eu tive que usar 'OfType para obter o ControlCollection no formulário IEnumerable; No Windows Forms, um ControlCollection não é enumerável: return control.Controls.OfType <Control> () .RecursiveSelect <Control> (c => c.Controls.OfType <Control> ()) .Where (c => c is T );
BillW
17

Outros forneceram a resposta correta, mas não creio que seu caso seja beneficiado.

Aqui está um trecho que alcança o mesmo sem 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>()));
}
timtim
fonte
2
Não usa o LINQ yieldtambém? ;)
Philipp M
Isso é liso. Eu sempre fui incomodado pelo foreachloop adicional . Agora eu posso fazer isso com pura programação funcional!
Jsuddsjr
1
Eu gosto dessa solução em termos de legibilidade, mas ela enfrenta o mesmo problema de desempenho com os iteradores do que com o yield. @ PhilippM: Verificou-se que o LINQ usa yield sourcesource.microsoft.com/System.Core/R/…
Herman
Prepare-se para uma ótima solução.
Tomer W
12

Você precisa retornar os itens do enumerador, não do próprio enumerador, no seu 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
fonte
9

Eu acho que você tem que render retornar cada um dos controles nos enumeráveis.

    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
fonte
8

A sintaxe de Seredynski está correta, mas você deve evitar as yield returnfunções recursivas, pois é um desastre para o uso da memória. Consulte https://stackoverflow.com/a/3970171/284795, que escala de forma explosiva com a profundidade (uma função semelhante estava usando 10% da memória no meu aplicativo).

Uma solução simples é usar uma lista e passá-la com a recursão 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);
    }
}

Como alternativa, você pode usar uma pilha e um loop while para eliminar chamadas recursivas https://codereview.stackexchange.com/a/5661/754

Coronel Panic
fonte
0

Embora haja muitas boas respostas por aí, eu ainda acrescentaria que é possível usar os métodos LINQ para realizar a mesma coisa.

Por exemplo, o código original do OP pode ser reescrito 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
fonte
Uma solução usando essa mesma abordagem foi publicada há três anos .
Servy
@Servy Embora seja semelhante (que eu perdi entre todas as respostas ... enquanto escrevia essa resposta), ainda é diferente, pois usa .OfType <> para filtrar e .Union ()
yoel halb
2
O OfTypefato não é realmente diferente. No máximo, uma pequena mudança estilística. Um controle não pode ser filho de vários controles; portanto, a árvore atravessada já não é necessária . Usar em Unionvez de Concatverificar desnecessariamente a exclusividade de uma sequência já garantida como única e, portanto, é um downgrade objetivo.
Servy