Come si attraversa un albero senza ricorrere alla ricorsione?

Question

Come si attraversa un albero senza ricorrere alla ricorsione?

#1 da (21 voti)
#2 da (4 voti)
#3 da (-3 voti)

14

Ho un albero dei nodi di memoria molto grande e ho bisogno di attraversare l'albero. Passando i valori restituiti di ciascun nodo figlio al nodo genitore. Questo deve essere fatto fino a quando tutti i nodi hanno i loro dati fino al nodo radice.

L'attraversamento funziona così.

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

Funziona bene, ma temo che lo stack delle chiamate limiti la dimensione dell'albero dei nodi.

Come può essere riscritto il codice in modo che non vengano effettuate chiamate ricorsive a Execute ?

c# optimization trees

posta cgTag 30.01.2014 - 22:10

fonte

3 risposte

21

Ecco un'implementazione trasversale di albero per scopi generali che non utilizza la ricorsione:

public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

Nel tuo caso puoi quindi chiamarlo in questo modo:

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

Utilizza un Queue invece di un Stack per una respirazione per prima, piuttosto che per la profondità prima, cerca. Utilizza un PriorityQueue per la migliore prima ricerca.

risposta data 30.01.2014 - 22:43

fonte

-3

Non è possibile attraversare una struttura dati a forma di albero senza ricorrere alla ricorsione - se non si utilizzano i telai dello stack e le chiamate di funzione fornite dalla propria lingua, in pratica è necessario programmare il proprio stack e le chiamate di funzione, ed è improbabile che tu riesca a farlo all'interno della lingua in modo più efficiente di quello che gli scrittori di compilatori hanno fatto sulla macchina su cui sarebbe stato eseguito il tuo programma.

Pertanto, evitare la ricorsione per timore di incorrere in limiti di risorse è solitamente fuorviante. Per essere sicuro, l'ottimizzazione prematura delle risorse è sempre errata, ma in questo caso è probabile che anche se si misura e si conferma che l'utilizzo della memoria è il collo di bottiglia, probabilmente non si sarà in grado di migliorarlo senza scendendo al livello dello scrittore del compilatore.

risposta data 30.01.2014 - 22:41

fonte

Leggi altre domande sui tag c# optimization trees

In DDD, la logica dell'applicazione di convalida o la logica del dominio? Le interfacce fluenti sono più flessibili degli attributi e perché?

score 4 · Accepted Answer

Se hai preventivamente una stima per la profondità del tuo albero, forse è sufficiente che il tuo caso adotti le dimensioni dello stack? In C # dalla versione 2.0 questo è possibile ogni volta che inizi una nuova discussione, vedi qui:

link

In questo modo puoi mantenere il tuo codice ricorsivo, senza dover implementare qualcosa di più complesso. Ovviamente, la creazione di una soluzione non ricorsiva con il proprio stack potrebbe essere più efficiente in termini di tempo e memoria, ma sono abbastanza sicuro che il codice non sarà così semplice come lo è ora.