LINQ-Rekursion-Funktion?

Nehmen wir als diese n-tier-tief-Struktur, zum Beispiel:

public class SomeItem 
{
     public Guid ID { get;set; }
     public string Name { get; set; }
     public bool HasChildren { get;set; }
     public IEnumerable<SomeItem> Children { get; set; }
}

Wenn ich bin auf der Suche, um ein bestimmtes Element durch ID (irgendwo in der Struktur) gibt es einige LINQ-Güte, die ich verwenden können, um es leicht zu bekommen in eine einzelne Anweisung oder muss ich nutzen, um einige rekursive Funktion, wie unten:

   private SomeItem GetSomeItem(IEnumerable<SomeItem> items, Guid ID)
    {
        foreach (var item in items)
        {
            if (item.ID == ID)
            {
                return item;
            }
            else if (item.HasChildren)
            {
                return GetSomeItem(item.Children, ID);
            }
        }
        return null;
    }
Brauchen Sie wirklich die HasChildren-Eigenschaft?
Nicht wirklich, nur ein Helfer, so dass es liest sich besser 🙂 - Kinder.Count > 0
Kinder.Jede() 🙂

InformationsquelleAutor The_Butcher | 2011-01-27

  1. 31

    LINQ nicht wirklich "tun" Rekursion schön. Ihre Lösung scheint angemessen zu sein - obwohl ich nicht sicher bin HasChildren wirklich erforderlich ist... warum nicht einfach eine leere Liste nach einem Element mit keine Kinder?

    Alternative ist das schreiben einer DescendantsAndSelf Methode, die zurückkehren wird alle der Nachkommen (einschließlich der Element selbst), so etwas wie dieses;

    //Warning: potentially expensive!
public IEnumerable<SomeItem> DescendantsAndSelf()
{
    yield return this;
    foreach (var item in Children.SelectMany(x => x.DescendantsAndSelf()))
    {
        yield return item;
    }
}

    Jedoch, wenn der Baum ist tief, die endet als sehr ineffizient, da jedes Element muss "passieren" alle Iteratoren von seiner Abstammung. Wes Dyer hat gebloggt über diese, zeigt eine effizientere Implementierung.

    Sowieso, wenn Sie eine Methode wie diese (aber es ist implementiert), können Sie einfach eine normale "where" - Klausel, um ein Element (oder die Erste/FirstOrDefault etc).

    Nicht die Anzahl der Iteratoren erzeugt eine Funktion der Gesamtzahl von Knoten statt von dem Baum der Tiefe? (DescendantsAndSelf heißt für jeden Knoten).
    Wenn Sie wiederholt aufrufen DescendantsAndSelf() wird es Durchlaufen, den ganzen Baum wieder oder muss LINQ halten Sie das Ergebnis?
    LINQ macht nichts Magisches hier. Es geht nicht um cache etwas für Sie. Natürlich, man könnte ToList zum erzeugen einer Cache-Kopie selbst.
    Stimmt, die Anzahl der Iteratoren erzeugt wird, basierend auf der Anzahl der Knoten - aber die Anzahl der Iteratoren jedes Element muss passieren, während es propagiert, um die top-iterator hängt von der Tiefe des Baumes. So einen tiefen Baum wird immer noch weniger effizient zu Durchlaufen, als ein oberflächlicher. Bearbeiten, um das klarer.
    Ich wollte gerade eine neue Frage stellen über rekursive linq und die Antwort(die DescendantsAndSelf trick) ist groß.(kombiniert mit SelectMany). danke. Kann dies geschrieben werden als Extension-Methode ?

    InformationsquelleAutor Jon Skeet

  2. 3

    hoffe, das hilft

    public static IEnumerable<Control> GetAllChildControls(this Control parent)
{
  foreach (Control child in parent.Controls)
  {
    yield return child;

    if (child.HasChildren)
    {
      foreach (Control grandChild in child.GetAllChildControls())
        yield return grandChild;
    }
  }
}
    danke - ähnlich wie mutable.net/blog/archive/2008/05/23/...
    Dies ist nicht rekursiv, aber.... nur eine Ebene tief 🙁

    InformationsquelleAutor Bonshington

  3. 3

    Hier ist einer, der ohne Rekursion. Dies vermeidet die Kosten, die durch mehrere Schichten von Iteratoren, also ich denke, es ist ungefähr so effizient, wie Sie kommen.

        public static IEnumerable<T> IterateTree<T>(this T root, Func<T, IEnumerable<T>> childrenF)
    {
        var q = new List<T>() { root };
        while (q.Any())
        {
            var c = q[0];
            q.RemoveAt(0);
            q.AddRange(childrenF(c) ?? Enumerable.Empty<T>());
            yield return c;
        }
    }

    Aufrufen, etwa so:

                var subtree = root.IterateTree(x => x. Children).ToList();
    Vielleicht sollte es auch verständlicher sein, wenn Sie implementiert die Funktion mit einer Warteschlange anstelle einer Liste. Die var c = q[0]; q.RemoveAt(0); ist wirklich eine potenziell ineffiziente Umsetzung der Queue.Dequeue() Methode
    du hast Recht.

    InformationsquelleAutor DenNukem

  4. 2

    Ist es wichtig, denken Sie daran, Sie müssen nicht alles tun, was mit LINQ, oder Standard-Rekursion. Es gibt interessante Optionen, wenn Sie Daten-Strukturen. Das folgende ist eine einfache Abflachung Funktion falls es jemanden interessiert.

        public static IEnumerable<SomeItem> Flatten(IEnumerable<SomeItem> items)
    {
        if (items == null || items.Count() == 0) return new List<SomeItem>();

        var result = new List<SomeItem>();
        var q = new Queue<SomeItem>(collection: items);

        while (q.Count > 0)
        {
            var item = q.Dequeue();
            result.Add(item);

            if (item?.Children?.Count() > 0)
                foreach (var child in item.Children)
                    q.Enqueue(child);
        }

        return result;
    }

    InformationsquelleAutor Felipe Ramos

  5. 1

    Zwar gibt es Verlängerung Methoden, mit denen die Rekursion in LINQ (und wahrscheinlich Aussehen wie Ihre Funktion) keine sind, zur Verfügung gestellt aus dem Kasten heraus.

    Beispiele für diese Erweiterung Methoden finden hier oder hier.

    Ich würde sagen, Ihre Funktion ist in Ordnung.

    InformationsquelleAutor Jens

Schreibe einen Kommentar