LINQ ile verimli grafik geçişi - yinelenen özyineleme

Question

Bugün, keyfi olarak derin bir grafiğe geçmek ve onu tek bir numarada düzleştirmek için bir yöntem uygulayacağım. Bunun yerine, önce küçük bir arama yaptım ve buldum: Bu iyi görünüyor, ancak pratikte bunun (durum doğar gibi) eşdeğer elle yazılmış kod kullanarak daha kötü anlamlı gerçekleştirir buldum Teoride

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

Bir grafikten geçmek ve yapılması gerekenleri yapmak. Bunun şundan şüpheleniyorum çünkü bu yöntemde, geri döndürdüğü her öğe için yığının keyfi olarak derin bir seviyeye kadar gevşemesi gerekiyor.

Ayrıca, bu yöntemin ortadan kaldırılması durumunda bu yöntemin çok daha verimli çalışacağından şüpheleniyorum. Aynı zamanda, özyinelemeyi ortadan kaldırmada çok iyi olmayacağım.

Özyinelemeyi gidermek için bu yöntemi yeniden yazmayı bilen var mı?

Yardımlarınız için teşekkür ederiz.

DÜZENLEME: Tüm ayrıntılı yanıtlar için çok teşekkürler. Bir çözümleyici yöntemi kullanmamaya benzeyen Eric'in çözümüne karşı orijinal çözümü kıyaslamaya çalıştım ve bunun yerine bir lambda ve garip bir şekilde tekrarlayan bir şekilde çaprazlama yaptım, lambda özyineleme diğer iki yöntemden çok daha hızlıdır. TraverseOld orijinal yöntemdir

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

, TraverseNew Eric'in yöntemdir ve açıkçası lamda lambda olduğunu.

Makinemde TraverseOld 10127 ms, TraverseNew 3038 ms alır, lambda özyineleme 1181 ms alır.

Bu tipik olarak, numaralandırma yöntemlerinin (verim dönüşü ile) anında yürütme yerine 3 kat daha uzun sürebilir mi? Yoksa başka bir şey mi oluyor?

Answer 1

Öncelikle, kesinlikle doğru; Eğer grafik, ortalama derinlik d n düğümlerine sahipse, o zaman, naif iç içe geçmiş yineleyiciler, zaman içinde O (n * d) ve yığında O (d) olan bir çözelti verir. Eğer d büyük bir n ise, o zaman bu bir O (n) algoritması olabilir ve eğer d büyükse, yığının tamamını tamamen patlatabilirsiniz. Eğer iç içe Yineleyicilerin bir performans analizi ile ilgileniyorsanız

, eski C# derleyicisi geliştirici Wes Dyer blog yazısı bkz:

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

dasblinkenlight çözümü standart yaklaşım bir çeşididir.

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

Ve sonra birden kökleri varsa: Genellikle böyle bir program yazıyormuş bir derece birbirine bağlı olup olmadığını Şimdi

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

, Geçişe istediğini değil olduğuna dikkat grafik veya döngüsel bir grafik! Eğer aşağı doğru işaret eden oklar ile bir grafik varsa: bir siklik ya da birbirine birleşik bir grafik varsa

  A 
     /\ 
     B-->C 
     \/
      D 

sonra geçişi, A, B, D, C, D, C, D o zaman ne istediğiniz olduğu geçişli kapatma.

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

Bu değişiklik sadece daha önce vermiştir edilmemiş öğeleri verir.

Ayrıca özyineleme ortadan kaldırılmasında çok iyi olamam.

Özyinelemeyi ortadan kaldırmak ve genel olarak yinelemeli programlama hakkında birkaç makale yazdım. Bu konu ilginizi çekiyorsa, bkz: Özellikle

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

: Bu yöntem çarpma recursing olduğu gibi ilk bakışta

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

Kodunuzda bir sıra kullanabilirsiniz. Sıra, üst düğüme eşit bir öğe ile bir liste olarak başlatılabilir. Daha sonra, listenin her elemanından ilkinden başlayarak yinelemeniz gerekir. İlk öğe, çocuk düğümleri içeriyorsa, hepsini sıraya sonuna eklersiniz. Sonra bir sonraki öğeye geçin. Kuyruğun sonuna ulaştığınızda grafiğiniz tamamen düzleşir.

Answer 3

Yinelemenin bir yığınla nasıl çalıştığının temellerini çoğaltarak yinelemeyi her zaman ortadan kaldırabilirsiniz.

1. yer yığını
2. üstünde ilk madde yığını boş olmasa da, şimdiki düğüm çocuk varsa, yığın kapalı
3. bir öğe pop yığını ekleyin
4. Verim, geçerli öğeyi döndürür.
5. 1. adıma geçin!

Çılgın akıllı teorik cevap: https://stackoverflow.com/a/933979/29093

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

Answer 4

Sen damgası yield return yapar kodunda ağaçları ve grafikler yürüyen, doğru verimsizlik büyük kaynağıdır.Genelde, yinelenen kodu bir yığınla yeniden yazdığınızda, genellikle derlenmiş kodda nasıl uygulandığına benzer şekilde.

Ben de denemek için bir şans vermedi, ama bu çalışması gerekir:

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