Как «развернуть» «рекурсивную» структуру

Question

Не знаю, как это назвать, но скажем, у вас есть класс, который выглядит так:

class Person
{
    public string Name;
    public IEnumerable<Person> Friends;
}

После этого у вас есть человек, и вы хотите рекурсивно «развернуть» эту структуру, чтобы получить единый список всех людей без дубликатов.

Как бы вы это сделали? Я уже сделал что-то, что, кажется, работает, но мне любопытно посмотреть, как это сделают другие, особенно если в Linq есть что-то встроенное, что вы можете использовать умным способом для решения этой маленькой проблемы:

---

Вот мое решение:

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)
        yield break;

    // For each subject
    foreach(var subject in subjects)
    {
        // Yield it
        yield return subject;

        // Then yield all its decendants
        foreach (var decendant in SelectRecursive(selector(subject), selector))
            yield return decendant;
    }
}

Будет использоваться что-то вроде этого:

var people = somePerson.SelectRecursive(x => x.Friends);

Answer 1

Я не верю, что в LINQ есть что-то встроенное для этого.

Есть проблема с рекурсивным выполнением этого - в итоге вы создаете большое количество итераторов. Это может быть совершенно неэффективно, если дерево глубоко. Уэс Дайер и Эрик Липперт сообщили об этом в блоге.

Вы можете устранить эту неэффективность, удалив прямую рекурсию. Например:

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

    Queue<T> stillToProcess = new Queue<T>(subjects);

    while (stillToProcess.Count > 0)
    {
        T item = stillToProcess.Dequeue();
        yield return item;
        foreach (T child in selector(item))
        {
            stillToProcess.Enqueue(child);
        }
    }
}

Это также изменит порядок итерации - он становится шириной, а не глубиной; переписать его так, чтобы он все еще был первым, сложно. Я также изменил его, чтобы не использовать Any() - эта пересмотренная версия не будет оценивать какую-либо последовательность более одного раза, что может быть полезно в некоторых сценариях. Имейте в виду, есть одна проблема - из-за очередей потребуется больше памяти. Мы могли бы, вероятно, смягчить это, сохранив очередь итераторов вместо элементов, но я не уверен, что это было бы необоснованно ... это, безусловно, было бы более сложным.

Один замечание (также отмечено ChrisW, когда я просматривал сообщения в блоге :) - если у вас есть какие-либо циклы в списке друзей (то есть, если у A есть B, а у B есть A), вы будете возвращаться навсегда .

Answer 2

Я нашел этот вопрос, когда искал и думал о похожем решении - в моем случае я создал эффективный IEnumerable<Control> для элементов управления ASP.NET UI. Рекурсивный yield, который у меня был, быстрый, но я знал, что это может привести к дополнительным расходам, поскольку чем глубже структура управления, тем дольше он может занять. Теперь я знаю, что это O (n log n).

Решение, приведенное здесь, дает некоторый ответ, но, как обсуждалось в комментариях, оно меняет порядок (который ОП не заботил). Я понял, что для сохранения порядка, заданного ОП и по мере необходимости, не будут работать ни простые Queue (как использовал Джон), ни Stack, поскольку сначала будут получены все родительские объекты, а затем любые потомки после них ( или наоборот).

Чтобы решить эту проблему и сохранить порядок, я понял, что решение будет просто поместить Enumerator в Stack. Если использовать оригинальный вопрос ОП, это будет выглядеть так:

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

Я использую stack.Peek здесь, чтобы избежать необходимости помещать один и тот же перечислитель обратно в стек, так как это, вероятно, будет более частой операцией, ожидая, что перечислитель предоставит более одного элемента.

При этом создается то же количество перечислителей, что и в рекурсивной версии, но, скорее всего, будет меньше новых объектов, чем при помещении всех объектов в очередь или стек и продолжении добавления любых объектов-потомков. Это время O (n), поскольку каждый перечислитель стоит сам по себе (в рекурсивной версии неявный вызов одного MoveNext выполняет MoveNext на дочерних перечислителях до текущей глубины в стеке рекурсии).

Answer 3

Вот реализация, которая:

• рекурсивный выбор глубины,
• Не требует двойной итерации дочерних коллекций,
• Не использует промежуточные коллекции для выбранных элементов,
• Не обрабатывает циклы,

• Можно сделать это задом наперед.

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

Answer 4

использовать совокупное расширение ...

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

Answer 5

Рекурсия это всегда весело.Возможно, вы могли бы упростить свой код до:

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

Это приведет к меньшему количеству дубликатов, чем ваш исходный код.Однако они все еще могут быть дубликатами, приводящими к бесконечному циклу, объединение будет предотвращать только прямые дубликаты родительского (ых) ребенка (ей).

И порядок элементов будет отличаться от вашего:)

Редактировать: Изменена последняя строка кода на три оператора и добавлено немного больше документации.

Answer 6

Вы также можете использовать нерекурсивный метод, подобный этому:

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

Это должно правильно обрабатывать циклы. Я я начинаю с одного человека, но вы можете легко расширить это, чтобы начать со списка людей.