Attraversamento grafico efficiente con LINQ - eliminazione della ricorsione

Question

Oggi stavo per implementare un metodo per attraversare un grafo arbitrariamente profondo e appiattirlo in una singola enumerabile. Invece, ho fatto un po 'di ricerca prima e trovato questo:

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

In teoria, questo sembra buono, ma in pratica ho trovato esegue significativamente più scarsa rispetto all'utilizzo di codice scritto a mano equivalente (come la situazione si verifica) per passare attraverso un grafico e fare tutto ciò che deve essere fatto. Sospetto che ciò avvenga perché in questo metodo, per ogni oggetto restituito, lo stack deve svolgersi a un livello arbitrariamente profondo.

Ho anche il sospetto che questo metodo sarebbe molto più efficiente se la ricorsione fosse eliminata. Inoltre, non sono molto bravo nell'eliminare la ricorsione.

Qualcuno sa come riscrivere questo metodo per eliminare la ricorsione?

Grazie per qualsiasi aiuto.

MODIFICA: Grazie mille per tutte le risposte dettagliate. Ho provato il benchmarking della soluzione originale contro la soluzione di Eric vs non usando un metodo di enumerazione e invece ricorsivamente attraversando con un lambda e stranamente, la ricorsione lambda è significativamente più veloce di uno degli altri due metodi.

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

Dove TraverseOld è il metodo originale, TraverseNew è il metodo di Eric, e, ovviamente, il lambda è la lambda.

Sulla mia macchina, TraverseOld richiede 10127 ms, TraverseNew richiede 3038 ms, la ricorsione lambda richiede 1181 ms.

È questo tipico che i metodi di enumerazione (con rendimento restituito) possono richiedere 3 volte più che l'esecuzione immediata? O qualcos'altro sta succedendo qui?

Answer 1

Prima di tutto, si è assolutamente corretto; se il grafico ha n nodi di profondità media d allora gli iteratori nidificati ingenui producono una soluzione che è O (n * d) nel tempo, e O (d) in pila. Se d è una grande frazione di n allora questo può diventare un algoritmo O (n), e se d è grande allora puoi saltare tutto lo stack.

Se siete interessati ad un analisi delle prestazioni di iteratori nidificati, vedere post del blog di ex compilatore C# sviluppatore Wes Dyer: soluzione

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

di dasblinkenlight è una variante del metodo standard. Vorrei solito scrivere il programma in questo modo:

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

E poi se si dispone di più radici:

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

Ora, si noti che un attraversamento è non quello che vuoi se si dispone di un altamente interconnesso grafico o un grafico ciclico! Se si dispone di un grafico con le frecce rivolte verso il basso:

  A 
     /\ 
     B-->C 
     \/
      D 

quindi l'attraversamento è A, B, D, C, D, C, D. Se ha un grafico ciclico o interconnessi allora ciò che si desidera è la chiusura transitiva.

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

Questa variazione produce solo articoli che non sono stati ceduti prima.

Mi capita anche di non essere molto bravo a eliminare la ricorsione.

Ho scritto una serie di articoli sui modi per eliminare la ricorsione e sulla programmazione ricorsiva in generale. Se questo argomento vi interessa, vedi:

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

In particolare:

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

È possibile utilizzare una coda nel codice. La coda può essere inizializzata come una lista con un elemento uguale al nodo superiore. Quindi è necessario scorrere tutti gli elementi dell'elenco a partire dal primo. Se il primo elemento contiene nodi figlio, li aggiungi tutti alla fine della coda. Quindi passa all'elemento successivo. Il tuo grafico sarà completamente appiattito quando raggiungi la fine della coda.

Answer 3

È sempre possibile eliminare la ricorsione replicando le nozioni di base su come la ricorsione funziona con una pila.

1. luogo il primo elemento in cima alla pila
2. Mentre la pila non è vuota, pop un elemento dallo stack
3. se il nodo corrente ha figli, aggiungerli alla pila
4. Restituisce l'articolo corrente.
5. Passare al punto 1!

Pazzo risposta teorica intelligente: https://stackoverflow.com/a/933979/29093

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

Answer 4

Hai ragione, camminando alberi e grafici in modo ricorsivo in codice che fa yield return è una grande fonte di inefficienza.

Generalmente, si riscrive il codice ricorsivo con uno stack, in modo simile a come viene solitamente implementato nel codice compilato.

non ho avuto la possibilità di provarlo, ma questo dovrebbe funzionare:

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