Làm thế nào để "cuộn" a "đệ quy" cấu trúc

Question

Không chắc làm thế nào để gọi nó, nhưng nói rằng bạn có một lớp trông như thế này:

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

Sau đó bạn có một người và bạn muốn "cuộn" cấu trúc này đệ quy để bạn kết thúc với một danh sách duy nhất của tất cả mọi người mà không có bản sao.

Bạn sẽ làm như thế nào? Tôi đã tạo ra một thứ gì đó có vẻ như đang hoạt động, nhưng tôi tò mò muốn xem người khác sẽ làm như thế nào và đặc biệt nếu có thứ gì đó tích hợp với LINQ, bạn có thể sử dụng một cách thông minh để giải quyết vấn đề nhỏ này :)

---

đây là giải pháp của tôi:

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

có thể được sử dụng một cái gì đó như thế này:

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

Answer 1

tôi không tin rằng có điều gì được xây dựng vào LINQ để làm điều này.

Có vấn đề với việc làm theo cách đệ quy như thế này - bạn sẽ tạo ra một số lượng lớn các trình vòng lặp. Điều này có thể khá không hiệu quả nếu cây là sâu. Wes Dyer và Eric Lippert có cả hai blog về điều này.

Bạn có thể loại bỏ sự không hiệu quả này bằng cách loại bỏ đệ quy trực tiếp. Ví dụ:

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

Điều này cũng sẽ thay đổi thứ tự lặp - nó trở thành chiều rộng đầu tiên thay vì chiều sâu; viết lại nó vẫn còn sâu đầu tiên là khó khăn. Tôi cũng đã thay đổi nó để không sử dụng Any() - phiên bản sửa đổi này sẽ không đánh giá bất kỳ trình tự nhiều hơn một lần, mà có thể được thuận tiện trong một số kịch bản. Điều này có một vấn đề, nhớ bạn - nó sẽ mất nhiều bộ nhớ hơn, do xếp hàng. Chúng ta có lẽ có thể làm giảm bớt điều này bằng cách lưu trữ một hàng đợi của các vòng lặp thay vì các mục, nhưng tôi không chắc chắn lắm ... nó chắc chắn sẽ phức tạp hơn.

Một điểm cần lưu ý (cũng được ChrisW chú ý khi tôi đang tìm kiếm các bài đăng trên blog :) - nếu bạn có bất kỳ chu kỳ nào trong danh sách bạn bè của bạn (ví dụ: nếu A có B và B có A) thì bạn sẽ recurse mãi mãi.

Answer 2

Bạn có thể sử dụng một phương pháp không đệ quy như thế này cũng như:

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

này nên xử lý chu kỳ đúng là tốt. Tôi am bắt đầu bằng một người, nhưng bạn có thể dễ dàng mở rộng điều này để bắt đầu với danh sách người.

Answer 3

Đệ quy luôn vui vẻ. Có lẽ bạn có thể đơn giản hóa mã của mình thành:

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

Nó sẽ dẫn đến ít trùng lặp hơn mã ban đầu của bạn. Tuy nhiên, chúng có thể vẫn là các bản sao gây ra một vòng lặp vô tận, liên minh sẽ chỉ ngăn các bản sao gốc (s) trực tiếp của cha mẹ.

Và thứ tự của các mục sẽ khác với bạn :)

Edit: Thay đổi dòng cuối cùng của mã để ba tuyên bố và bổ sung tài liệu hơn một chút.

Answer 4

sử dụng phần mở rộng tổng hợp ...

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

Tôi tìm thấy câu hỏi này như tôi đang tìm kiếm và suy nghĩ về một giải pháp tương tự - trong trường hợp của tôi tạo ra một hiệu quả IEnumerable<Control> cho các điều khiển ASP.NET UI. Các đệ quy yield Tôi đã có được nhanh chóng nhưng tôi biết rằng có thể có thêm chi phí, kể từ khi sâu hơn cơ cấu kiểm soát lâu hơn nó có thể mất. Bây giờ tôi biết đây là O (n log n).

Giải pháp đưa ra ở đây cung cấp một số câu trả lời nhưng, như được thảo luận trong các ý kiến, nó thay đổi thứ tự (mà OP không quan tâm). Tôi nhận ra rằng để giữ trật tự như được OP và khi cần, không đơn giản Queue (như Jon đã sử dụng) cũng không phải Stack sẽ hoạt động vì tất cả các đối tượng cha mẹ sẽ được sinh ra trước và sau đó bất kỳ trẻ em nào sau chúng (hoặc ngược lại)).

Để giải quyết vấn đề này và duy trì thứ tự, tôi đã nhận ra giải pháp đơn giản là đặt chính số Enumerator trên Stack. Để sử dụng các câu hỏi Ops gốc nó sẽ trông như thế này:

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

tôi sử dụng stack.Peek đây để tránh phải đẩy các điều tra viên cùng trở lại vào ngăn xếp như thế này có khả năng là hoạt động thường xuyên hơn, mong rằng điều tra viên để cung cấp nhiều hơn một mục.

Điều này tạo ra cùng một số điều tra như trong phiên bản đệ quy nhưng có thể sẽ ít đối tượng mới hơn đặt tất cả các đối tượng trong hàng đợi hoặc ngăn xếp và tiếp tục thêm bất kỳ đối tượng hậu duệ nào. Đây là thời gian O (n) khi mỗi điều tra tự đứng lên (trong phiên bản đệ quy, một cuộc gọi ngầm đến một số MoveNext thực hiện MoveNext trên các điều tra con đến độ sâu hiện tại trong ngăn xếp đệ quy).

Answer 6

Dưới đây là một thực rằng:

• Liệu độ sâu đầu tiên đệ quy chọn,
• Không yêu cầu lặp kép của các bộ sưu tập trẻ em,
• Không sử dụng bộ sưu tập trung cho các yếu tố được lựa chọn,
• Không xử lý các chu kỳ,

• Có thể làm ngược lại.

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