Jak "rozwinąć" strukturę "rekurencyjną"

Znalazłem to pytanie, ponieważ szukałem i myślałem o podobnym rozwiązaniu - w moim przypadku stworzenie skutecznego IEnumerable<Control> dla ASP.NET sterowanie UI. Rekurencyjny yield, który miałem, jest szybki, ale wiedziałem, że może to mieć dodatkowy koszt, ponieważ im głębsza struktura kontrolna, tym dłużej może to potrwać. Teraz wiem, że to jest O (n log n).

Podane tutaj rozwiązanie daje pewną odpowiedź, ale, jak wspomniano w komentarzach, zmienia kolejność (o czym OP nie dbał). Zdałem sobie sprawę, że do zachowaÄ ‡ kolejnoĹ "Ä ‡ podanÄ ... przez OP i tak jak potrzebowaĺ' em, ani proste Queue (Jak uĺźyĺ 'Jon), ani Stack nie dziaĹ' aĹ 'y, poniewaĹź wszystkie obiekty rodzicä ... byĹ' y najpierw przekazywane, a nastÄ ™ pnie dzieci (lub vice-versa).

Aby to rozwiązać i zachować porządek zdałem sobie sprawę, że rozwiązaniem byłoby po prostu umieścić Enumerator się na Stack. Aby użyć oryginalnego pytania OPs, wyglądałoby to tak:

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
        yield break;

    var stack = new Stack<IEnumerator<T>>();

    stack.Push(subjects.GetEnumerator());

    while (stack.Count > 0)
    {
        var en = stack.Peek();
        if (en.MoveNext())
        {
            var subject = en.Current;
            yield return subject;

            stack.Push(selector(subject).GetEnumerator());
        }
        else 
        {
            stack.Pop();
        }
    }
}

Używam stack.Peek tutaj, aby nie zmuszać tego samego enumeratora do stos, ponieważ jest to prawdopodobnie częstsza operacja, oczekując, że enumerator dostarczy więcej niż jeden element.

Tworzy to taką samą liczbę enumeratorów jak w wersji rekurencyjnej, ale prawdopodobnie będzie mniej nowych obiektów niż umieszczenie wszystkich obiektów w kolejce lub stosie i kontynuowanie dodawania obiektów potomnych. Jest to czas O(n), ponieważ każdy enumerator stoi na swoim (w wersji rekurencyjnej niejawne wywołanie do one MoveNext wykonuje MoveNext na potomnych enumeratorach do aktualna głębokość stosu rekurencyjnego).

Użyj rozszerzenia zbiorczego...

    List<Person> persons = GetPersons(); 
    List<Person> result = new List<Person>(); 
    persons.Aggregate(result,SomeFunc);

    private static List<Person> SomeFunc(List<Person> arg1,Person arg2)
    {
    arg1.Add(arg2)
    arg1.AddRange(arg2.Persons);
    return arg1;
    }

Oto implementacja, która:

• wykonuje najpierw rekurencyjną selekcję głębi,
• nie wymaga podwójnej iteracji kolekcji potomnych,
• nie używa zbiorów pośrednich dla wybranych elementów,
• nie obsługuje cykli,
• Można to zrobić od tyłu.

  public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector)
  {
      return new RecursiveEnumerable<T>(rootItems, selector, false);
  }
  
  public static IEnumerable<T> SelectRecursiveReverse<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector)
  {
      return new RecursiveEnumerable<T>(rootItems, selector, true);
  }
  
  class RecursiveEnumerable<T> : IEnumerable<T>
  {
      public RecursiveEnumerable(IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector, bool reverse)
      {
          _rootItems = rootItems;
          _selector = selector;
          _reverse = reverse;
      }
  
      IEnumerable<T> _rootItems;
      Func<T, IEnumerable<T>> _selector;
      bool _reverse;
  
      public IEnumerator<T> GetEnumerator()
      {
          return new Enumerator(this);
      }
  
      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
      {
          return GetEnumerator();
      }
  
      class Enumerator : IEnumerator<T>
      {
          public Enumerator(RecursiveEnumerable<T> owner)
          {
              _owner = owner;
              Reset();
          }
  
          RecursiveEnumerable<T> _owner;
          T _current;
          Stack<IEnumerator<T>> _stack = new Stack<IEnumerator<T>>();
  
  
          public T Current
          {
              get 
              {
                  if (_stack == null || _stack.Count == 0)
                      throw new InvalidOperationException();
                  return _current; 
              }
          }
  
          public void Dispose()
          {
              _current = default(T);
              if (_stack != null)
              {
                  while (_stack.Count > 0)
                  {
                      _stack.Pop().Dispose();
                  }
                  _stack = null;
              }
          }
  
          object System.Collections.IEnumerator.Current
          {
              get { return Current; }
          }
  
          public bool MoveNext()
          {
              if (_owner._reverse)
                  return MoveReverse();
              else
                  return MoveForward();
          }
  
          public bool MoveForward()
          {
              // First time?
              if (_stack == null)
              {
                  // Setup stack
                  _stack = new Stack<IEnumerator<T>>();
  
                  // Start with the root items
                  _stack.Push(_owner._rootItems.GetEnumerator());
              }
  
              // Process enumerators on the stack
              while (_stack.Count > 0)
              {
                  // Get the current one
                  var se = _stack.Peek();
  
                  // Next please...
                  if (se.MoveNext())
                  {
                      // Store it
                      _current = se.Current;
  
                      // Get child items
                      var childItems = _owner._selector(_current);
                      if (childItems != null)
                      {
                          _stack.Push(childItems.GetEnumerator());
                      }
  
                      return true;
                  }
  
                  // Finished with the enumerator
                  se.Dispose();
                  _stack.Pop();
              }
  
              // Finished!
              return false;
          }
  
          public bool MoveReverse()
          {
              // First time?
              if (_stack == null)
              {
                  // Setup stack
                  _stack = new Stack<IEnumerator<T>>();
  
                  // Start with the root items
                  _stack.Push(_owner._rootItems.Reverse().GetEnumerator());
              }
  
              // Process enumerators on the stack
              while (_stack.Count > 0)
              {
                  // Get the current one
                  var se = _stack.Peek();
  
                  // Next please...
                  if (se.MoveNext())
                  {
                      // Get child items
                      var childItems = _owner._selector(se.Current);
                      if (childItems != null)
                      {
                          _stack.Push(childItems.Reverse().GetEnumerator());
                          continue;
                      }
  
                      // Store it
                      _current = se.Current;
                      return true;
                  }
  
                  // Finished with the enumerator
                  se.Dispose();
                  _stack.Pop();
  
                  if (_stack.Count > 0)
                  {
                      _current = _stack.Peek().Current;
                      return true;
                  }
              }
  
              // Finished!
              return false;
          }
  
          public void Reset()
          {
              Dispose();
          }
      }
  }
  

Możesz też użyć metody nie rekurencyjnej takiej jak Ta:

  HashSet<Person> GatherAll (Person p) {
     Stack<Person> todo = new Stack<Person> ();
     HashSet<Person> results = new HashSet<Person> ();
     todo.Add (p); results.Add (p);
     while (todo.Count > 0) {
        Person p = todo.Pop (); 
        foreach (Person f in p.Friends) 
           if (results.Add (f)) todo.Add (f);
     }
     return results;
  }

To powinno obsługiwać cykle prawidłowo, jak również. Iam zaczyna się od jednej osoby, ale można to łatwo rozszerzyć, aby rozpocząć od listy osób.

Rekurencja jest zawsze zabawna. Być może mógłbyś uprościć swój kod do:

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector) {
    // Stop if subjects are null or empty 
    if (subjects == null || !subjects.Any())
        return Enumerable.Empty<T>();

    // Gather a list of all (selected) child elements of all subjects
    var subjectChildren = subjects.SelectMany(selector);

    // Jump into the recursion for each of the child elements
    var recursiveChildren = SelectRecursive(subjectChildren, selector);

    // Combine the subjects with all of their (recursive child elements).
    // The union will remove any direct parent-child duplicates.
    // Endless loops due to circular references are however still possible.
    return subjects.Union(recursiveChildren);
}

Spowoduje to mniej duplikatów niż oryginalny kod. Jednak nadal mogą być duplikatami powodującymi niekończącą się pętlę, Unia zapobiegnie tylko bezpośrednim duplikatom rodzica-dziecka.

A kolejność przedmiotów będzie inna niż Twoja:)

Edit: zmienił ostatnią linię kodu na trzy instrukcje i dodał nieco więcej dokumentacji.