2011-11-14 30 views
6

Ho una funzione javascript che percorre un albero in modo ricorsivo. Ha due variabili "flag" che sono impostate su false o true al di sopra dell'ambito della funzione stessa, e quindi se un flag è impostato su true una volta mentre la funzione "walkTree" viene ripetuta, sarà vera per ogni ricorsione . D'altra parte, il ciclo for potrebbe esistere la funzione con un ritorno anche se qualcosa è per. Il problema che ho è quando ci sono troppe ricorsioni ottengo un errore.come rendere questa funzione ricorsiva sincrona asincrona

Vorrei evitare questo problema rendendo questa funzione ricorsiva asincrona, Ho provato a mettere il sub walkTree() chiamata all'interno del ciclo for in un setTimeout, ma il problema che ho ora è che il resto della la funzione verrà eseguita (e potrebbe restituire il valore errato) prima che venga eseguito il resto delle cose asincrone. Quindi, come posso renderlo asincrono pur continuando a verificare che venga restituito il valore corretto (e non la chiamata alla funzione principale nella ricorsione)?

Come si può vedere la fine della funzione si avvale di che flagB "variabile" condiviso da tutte le chiamate, e quindi abbiamo bisogno di assicurarsi che tutte le chiamate ricorsive sono stati completati (e restituito qualcosa) prima di quella superiore controlli per questi condizionali. Grazie!

var flagA = false; 
var flagB = false; 

var walkTree = function (n) { 
    var sub; 

    for (var i = 0; i < n.children.length; i++) { 
     sub = walkTree(n.children[i]); 
     if (sub === 'something-special') { 
     return sub; 
     } 
    } 

    var test = doSomethingWith(n); 

    if (test === "something") { 
    flagA = true; 
    } 

    if (test === "something-else") { 
    flagB = true; 
    } 

    if (flagB === true) { 
    return true; 
    } 
    if (test === "something-special") { 
    return test; 
    } else { 
    return false; 
    } 

} 
+0

funzioni asincrone non sarà in grado di restituire un valore utile, è necessario fornire una funzione di callback come parametro. – zzzzBov

+0

Perché non stai controllando se l'elemento (argomento) ha figli prima di eseguirne il ciclo? – Headshota

+0

Sì, nella mia funzione effettiva sto facendo se (n.children! = Undefined && n.children.length> 0) –

risposta

1

Come suggerito da alex vasi, è possibile considerare iterative tree traversal anziché ricorsive. Tuttavia, se il set di dati è enorme e l'elaborazione dei dati richiede molto tempo, l'interfaccia utente potrebbe bloccarsi. Pertanto, si potrebbe ancora voler eseguire l'elaborazione in modo asincrono.

Ecco una variante dell'esempio di alex:

function asyncIterativeWalkTree(node) { 
    var queue = [node]; 

    var processQueue = function() { 
     var n = queue.shift(); 
     for (var i = 0; i < n.children.length; i++) { 
      queue.push(n.children[i]); 
      setTimeout(processQueue, 0); 
     } 
     doSomethingWith(n); 
    } 

    processQueue(); 
} 

Il frammento di codice di cui sopra fa traslazione iterativo asincrono, dando così un certo tempo per l'interfaccia utente per aggiornare stessa.

Ecco uno jsFiddle in cui è possibile notare la differenza tra traslazione sincrona e asincrona. La traversa sincrona blocca il browser per un breve periodo di tempo, mentre la versione asincrona dà al browser un po 'di tempo per respirare mentre elabora l'albero. (Il codice è un po 'confuso, mi spiace ...)

Modifica: Aggiornato jsFiddle

+0

Ahh! molto carino, grazie! Cercherò di renderlo asincrono e vedere se a volte aiuta l'interfaccia utente. Grazie! –

1

Utilizzare timeout per camminare sull'albero, sul serio? Hai preso in considerazione l'uso di iterative tree traversal anziché ricorsive?

Esempio:

var walkTree = function(node) { 
    var queue = [node]; 
    while (queue.length) { 
     var n = queue.shift(); 
     for (var i = 0; i < n.children.length; i++) { 
      queue.push(n.children[i]); 
     } 
     doSomethingWith(n); 
    } 
} 

vedere anche this so question e wikipeida article.

+0

grazie, esamineremo questo. Ho cercato di far funzionare questa funzione ricorsiva non ho pensato di cercare un altro modo di farlo. –

+0

Si noti che se la propria struttura è enorme, si potrebbe comunque voler procedere con una soluzione asincrona per impedire il blocco dell'interfaccia utente. – rap1ds

Problemi correlati