Duyệt đồ thị hiệu quả với LINQ - loại bỏ đệ quy

Question

Hôm nay tôi sẽ thực hiện một phương pháp để đi qua một đồ thị sâu tùy ý và làm phẳng nó thành một số đếm đơn. Thay vào đó, tôi đã làm một chút tìm kiếm đầu tiên và thấy điều này:

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector) 
{ 
    foreach (T item in enumerable) 
    { 
     yield return item; 

     IEnumerable<T> seqRecurse = recursivePropertySelector(item); 

     if (seqRecurse == null) continue; 
     foreach (T itemRecurse in Traverse(seqRecurse, recursivePropertySelector)) 
     { 
      yield return itemRecurse; 
     } 
    } 
} 

Về lý thuyết này có vẻ tốt, nhưng trong thực tế tôi đã tìm thấy nó thực hiện đáng kể kém hơn sử dụng mã viết tay tương đương (như tình hình phát sinh) để đi qua một đồ thị và làm bất cứ điều gì cần phải được thực hiện. Tôi nghi ngờ điều này là bởi vì trong phương pháp này, cho mỗi mục nó trả về, ngăn xếp phải thư giãn đến một mức độ tùy ý sâu.

Tôi cũng nghi ngờ rằng phương pháp này sẽ chạy hiệu quả hơn nhiều nếu đệ quy bị loại bỏ. Tôi cũng tình cờ không giỏi loại bỏ đệ quy.

Có ai biết cách viết lại phương pháp này để loại bỏ đệ quy không?

Cảm ơn bạn đã được trợ giúp.

EDIT: Cảm ơn rất nhiều vì tất cả các câu trả lời chi tiết. Tôi đã thử benchmarking giải pháp ban đầu so với giải pháp của Eric vs không sử dụng một phương pháp đếm và thay vì đệ quy đi qua với một lambda và kỳ quặc, đệ quy lambda nhanh hơn đáng kể so với một trong hai phương pháp kia.

class Node 
{ 
    public List<Node> ChildNodes { get; set; } 

    public Node() 
    { 
     ChildNodes = new List<Node>(); 
    } 
} 

class Foo 
{ 
    public static void Main(String[] args) 
    { 
     var nodes = new List<Node>(); 
     for(int i = 0; i < 100; i++) 
     { 
      var nodeA = new Node(); 
      nodes.Add(nodeA); 
      for (int j = 0; j < 100; j++) 
      { 
       var nodeB = new Node(); 
       nodeA.ChildNodes.Add(nodeB); 
       for (int k = 0; k < 100; k++) 
       { 
        var nodeC = new Node(); 
        nodeB.ChildNodes.Add(nodeC); 
        for(int l = 0; l < 12; l++) 
        { 
         var nodeD = new Node(); 
         nodeC.ChildNodes.Add(nodeD); 
        } 
       } 
      } 
     }    

     nodes.TraverseOld(node => node.ChildNodes).ToList(); 
     nodes.TraverseNew(node => node.ChildNodes).ToList(); 

     var watch = Stopwatch.StartNew(); 
     nodes.TraverseOld(node => node.ChildNodes).ToList(); 
     watch.Stop(); 
     var recursiveTraversalTime = watch.ElapsedMilliseconds; 
     watch.Restart(); 
     nodes.TraverseNew(node => node.ChildNodes).ToList(); 
     watch.Stop(); 
     var noRecursionTraversalTime = watch.ElapsedMilliseconds; 

     Action<Node> visitNode = null; 
     visitNode = node => 
     { 
      foreach (var child in node.ChildNodes) 
       visitNode(child); 
     }; 

     watch.Restart(); 
     foreach(var node in nodes) 
      visitNode(node); 
     watch.Stop(); 
     var lambdaRecursionTime = watch.ElapsedMilliseconds; 
    } 
} 

Trường hợp TraverseOld là phương thức gốc, TraverseNew là phương thức của Eric và rõ ràng lambda là lambda.

Trên máy của tôi, TraverseOld mất 10127 ms, TraverseNew mất 3038 ms, đệ trình lambda mất 1181 ms.

Đây có phải là điển hình mà phương pháp liệt kê (với lợi tức lợi nhuận) có thể mất 3X miễn là trái ngược với thực hiện ngay lập tức không? Hoặc là một cái gì đó khác đang xảy ra ở đây?

Answer 1

Trước hết, bạn là hoàn toàn chính xác; nếu đồ thị có n nút có độ sâu trung bình d thì các trình vòng lặp lồng nhau ngây thơ tạo ra một giải pháp là O (n * d) theo thời gian và O (d) trong ngăn xếp. Nếu d là một phần lớn n thì điều này có thể trở thành một thuật toán O (n) và nếu d lớn thì bạn có thể thổi hoàn toàn ngăn xếp.

Nếu bạn quan tâm đến một phân tích hiệu suất của vòng lặp lồng nhau, xem bài đăng blog cựu C phát triển # biên dịch Wes Dyer của: giải pháp

http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx

dasblinkenlight là một biến thể của phương pháp tiêu chuẩn. Tôi thường sẽ viết chương trình như thế này:

public static IEnumerable<T> Traverse<T>(
    T root, 
    Func<T, IEnumerable<T>> children) 
{ 
    var stack = new Stack<T>(); 
    stack.Push(root); 
    while(stack.Count != 0) 
    { 
     T item = stack.Pop(); 
     yield return item; 
     foreach(var child in children(item)) 
      stack.Push(child); 
    } 
} 

Và sau đó nếu bạn có nhiều rễ:

public static IEnumerable<T> Traverse<T>(
    IEnumerable<T> roots, 
    Func<T, IEnumerable<T>> children) 
{ 
    return from root in roots 
      from item in Traverse(root, children) 
      select item ; 
} 

Bây giờ, lưu ý rằng một traversal là không những gì bạn muốn nếu bạn có một đánh giá cao kết nối với nhau biểu đồ hoặc đồ thị tuần hoàn! Nếu bạn có một đồ thị với các mũi tên trỏ xuống:

  A 
     /\ 
     B-->C 
     \/
      D 

thì traversal là A, B, D, C, D, C, D. Nếu bạn có một đồ thị có chu kỳ hoặc kết nối với nhau sau đó những gì bạn muốn là đóng cửa chuyển tiếp.

public static IEnumerable<T> Closure<T>(
    T root, 
    Func<T, IEnumerable<T>> children) 
{ 
    var seen = new HashSet<T>(); 
    var stack = new Stack<T>(); 
    stack.Push(root); 

    while(stack.Count != 0) 
    { 
     T item = stack.Pop(); 
     if (seen.Contains(item)) 
      continue; 
     seen.Add(item); 
     yield return item; 
     foreach(var child in children(item)) 
      stack.Push(child); 
    } 
} 

Biến thể này chỉ mang lại các mục chưa được tạo trước đó.

Tôi cũng tình cờ không giỏi loại bỏ đệ quy.

Tôi đã viết một số bài viết về cách loại bỏ đệ quy và về lập trình đệ quy nói chung. Nếu vấn đề này bạn quan tâm, xem:

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

Đặc biệt:

http://blogs.msdn.com/b/ericlippert/archive/2005/08/01/recursion-part-two-unrolling-a-recursive-function-with-an-explicit-stack.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/04/recursion-part-three-building-a-dispatch-engine.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx

Answer 2

Bạn có thể sử dụng hàng đợi trong mã của mình. Hàng đợi có thể được khởi tạo như một danh sách với một phần tử bằng nút trên cùng. Sau đó, bạn phải lặp qua từng phần tử của danh sách bắt đầu từ phần tử đầu tiên. Nếu phần tử đầu tiên chứa các nút con, bạn nối tất cả chúng vào cuối hàng đợi. Sau đó chuyển sang phần tử tiếp theo. Biểu đồ của bạn sẽ hoàn toàn phẳng khi bạn đến cuối hàng đợi.

Answer 3

Bạn luôn có thể loại bỏ đệ quy bằng cách sao chép các khái niệm cơ bản về cách đệ quy hoạt động với ngăn xếp.

1. nơi mục đầu tiên trên đỉnh của ngăn xếp
2. Trong khi chồng không phải là trống rỗng, bật một mục ra khỏi stack
3. nếu nút hiện có trẻ em, thêm chúng vào ngăn xếp
4. Lợi nhuận trả về mục hiện tại.
5. Chuyển đến bước 1!

điên thông minh câu trả lời lý thuyết: https://stackoverflow.com/a/933979/29093

http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf

Answer 4

Bạn nói đúng, đi bộ cây và đồ thị đệ quy trong mã mà không yield return là một nguồn lớn không hiệu quả.

Nói chung, bạn viết lại mã đệ quy bằng ngăn xếp - theo cách tương tự như cách nó thường được triển khai trong mã được biên dịch.

tôi đã không nhận được một cơ hội để thử nó ra, nhưng điều này sẽ làm việc:

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector) { 
    var stack = new Stack<IEnumerable<T>>(); 
    stack.Push(enumerable); 
    while (stack.Count != 0) { 
     enumerable = stack.Pop(); 
     foreach (T item in enumerable) { 
      yield return item; 
      var seqRecurse = recursivePropertySelector(item); 
      if (seqRecurse != null) { 
       stack.Push(seqRecurse); 
      } 
     } 
    } 
}