IEnumerable and Recursion using return return

307

Mam IEnumerable<T>metodę, której używam do znajdowania formantów na stronie WebForms.

Ta metoda jest rekurencyjna i mam pewne problemy ze zwróceniem żądanego typu, gdy yield returnzwraca wartość wywołania rekurencyjnego.

Mój kod wygląda następująco:

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

To powoduje obecnie błąd „Nie można przekonwertować typu wyrażenia”. Jeśli jednak ta metoda zwraca typ IEnumerable<Object>, kod jest budowany, ale w wyniku zwracany jest niewłaściwy typ.

Czy istnieje sposób korzystania z yield returnjednoczesnej rekurencji?

Jamie Dixon
źródło
1
stackoverflow.com/questions/1815497/… : link do odpowiedzi „mrydengrens” w wątku „Wyliczanie kolekcji, które z natury nie są IEnumerable?” Jego przykładowy kod oparty jest na artykule Erica Lipperta na blogu, pokazującym, jak używać stosów w wyliczaniu rekurencyjnym za pomocą Linq, unikając w ten sposób potencjalnie kosztownego użycia pamięci przez iteratory. imho bardzo przydatne!
BillW
BTW. if(c.Controls.Count > 0)-> if(c.Controls.Any()), szczególnie jeśli również
ustępujesz
Nie sądzę, że ta sprawa przynosi korzyści z ustępowania. Dla kompletności zapewniłem wdrożenie bez yield. Zobacz poniżej :) I to też jest jedna linijka :)
tymtam
Należy zachować ostrożność, aby yield returnw funkcjach rekurencyjnych uniknąć skalowania użycia pamięci. Zobacz stackoverflow.com/a/30300257/284795
Pułkownik Panika

Odpowiedzi:

485

Wewnątrz metody, która zwraca IEnumerable<T>, yield returnmusi zwrócić T, a nie an IEnumerable<T>.

Zastąpić

yield return c.GetDeepControlsByType<T>();

z:

foreach (var x in c.GetDeepControlsByType<T>())
{
  yield return x;
}
Marcin Seredynski
źródło
98

Musisz wydać każdy przedmiot uzyskany w wyniku rekurencyjnego połączenia:

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

Zauważ, że rekursja w ten sposób wiąże się z pewnymi kosztami - w końcu stworzysz wiele iteratorów, które mogą powodować problemy z wydajnością, jeśli masz naprawdę głębokie drzewo kontroli. Jeśli chcesz tego uniknąć, po prostu musisz wykonać rekursję w ramach metody, aby upewnić się, że utworzono tylko jeden iterator (maszynę stanu). Zobacz to pytanie, aby uzyskać więcej szczegółów i przykładową implementację - ale to oczywiście dodaje pewnej złożoności.

Jon Skeet
źródło
2
Zaskakujące jest to, że w wątku na temat ustępowania Jona nie wspominałem c.Controls.Count > 0vs. .Any():)
tymtam,
@Tymek faktycznie jest wymieniony w powiązanej odpowiedzi.
28

Jak zauważają Jon Skeet i pułkownik Panic w swoich odpowiedziach, stosowanie yield returnmetod rekurencyjnych może powodować problemy z wydajnością, jeśli drzewo jest bardzo głębokie.

Oto ogólna nierekurencyjna metoda przedłużania, która wykonuje najpierw głębokość przechodzenia przez sekwencję drzew:

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

W przeciwieństwie do rozwiązania Erica Lipperta RecursiveSelect współpracuje bezpośrednio z modułami wyliczającymi, dzięki czemu nie musi wywoływać funkcji Reverse (która buforuje całą sekwencję w pamięci).

Za pomocą RecursiveSelect oryginalną metodę OP można przepisać w następujący sposób:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    return control.Controls.RecursiveSelect(c => c.Controls).Where(c => c is T);
}
Michael Liu
źródło
Aby ten (doskonały) kod działał, musiałem użyć „OfType”, aby uzyskać ControlCollection w postaci IEnumerable; w formularzach Windows ControlCollection nie jest wyliczalny: return control.Controls.OfType <Control> () .RecursiveSelect <Control> (c => c.Controls.OfType <Control> ()). Gdzie (c => c jest T );
BillW
17

Inni podali prawidłową odpowiedź, ale nie sądzę, aby twoja sprawa przyniosła korzyść z ustępstw.

Oto fragment kodu, który osiąga to samo bez ustępowania.

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
źródło
2
Nie używa również LINQ yield? ;)
Philipp M
To jest zręczne. Zawsze przeszkadzała mi dodatkowa foreachpętla. Teraz mogę to zrobić za pomocą czysto funkcjonalnego programowania!
jsuddsjr
1
Podoba mi się to rozwiązanie pod względem czytelności, ale w przypadku iteratorów występuje ten sam problem z wydajnością, co w przypadku wydajności. @PhilippM: sprawdzeniu, że zastosowania LINQ otrzymując referencesource.microsoft.com/System.Core/R/...
Herman
Kciuk w górę, aby uzyskać świetne rozwiązanie.
Tomer W
12

Musisz zwrócić elementy z modułu wyliczającego, a nie z samego modułu wyliczającego, na sekundę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;
            }
        }
    }
}
Rob Levine
źródło
9

Myślę, że musisz dać zwrot każdej z formantów w wyliczeniach.

    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
źródło
8

Składnia Seredynskiego jest poprawna, ale należy uważać, aby unikać yield returnfunkcji rekurencyjnych, ponieważ jest to katastrofa z powodu zużycia pamięci. Zobacz https://stackoverflow.com/a/3970171/284795 . Skaluje się gwałtownie z głębokością (podobna funkcja używała 10% pamięci w mojej aplikacji).

Prostym rozwiązaniem jest użycie jednej listy i przekazanie jej z rekurencją 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);
    }
}

Alternatywnie możesz użyć stosu i pętli while, aby wyeliminować rekurencyjne połączenia https://codereview.stackexchange.com/a/5661/754

Pułkownik Panika
źródło
0

Chociaż istnieje wiele dobrych odpowiedzi, nadal dodam, że możliwe jest użycie metod LINQ do osiągnięcia tego samego,.

Na przykład oryginalny kod OP może zostać przepisany jako:

public static IEnumerable<Control> 
                           GetDeepControlsByType<T>(this Control control)
{
   return control.Controls.OfType<T>()
          .Union(control.Controls.SelectMany(c => c.GetDeepControlsByType<T>()));        
}
yoel halb
źródło
Rozwiązanie wykorzystujące to samo podejście opublikowano trzy lata temu .
Servy
@Servy Chociaż jest podobny (którego BTW przeoczyłem między wszystkimi odpowiedziami ... podczas pisania tej odpowiedzi), nadal jest inny, ponieważ używa .OfType <> do filtrowania, a .Union ()
yoel halb
2
To OfTypenie jest naprawdę miażdżący inny. Co najwyżej niewielka zmiana styalistyczna. Kontrolka nie może być dzieckiem wielu kontrolek, więc drzewo, które przechodzi, jest już niepotrzebne. Używanie Unionzamiast Concatniepotrzebnie weryfikuje wyjątkowość sekwencji, która jest już gwarantowana jako wyjątkowa, a zatem jest obiektywnym obniżeniem poziomu.
Servy