この同期再帰関数を非同期にする方法

Question

私は再帰的にツリーを歩くjavascript関数を持っています。関数自体のスコープの上にfalseまたはtrueに設定された2つの "フラグ"変数があるため、 "walkTree"関数が再帰されている間にフラグが1回trueに設定されていると、すべての再帰。一方、forループは、何かのためにリターンを持つ関数の中に存在するかもしれません。私が持っている問題は、再帰が多すぎるときにエラーが発生したときです。

私はsetTimeoutをへのforループ内のサブwalkTree（）の呼び出しを入れて試してみた、この再帰関数を非同期に行うことで、この問題を回避したいのですが、私は今持っている問題があることが、残りのです関数が実行され（そして間違った値を返すかもしれません）、残りの非同期処理が完了します。だから、私はこれを非同期にして、正しい値が返されるようにします（再帰の先頭の関数呼び出しではありません）。

トップ1を確認する前に、関数の最後には、すべてのコールで共有することflagB「変数」を利用している見ることができる、と私たちは（何かと返された）すべての再帰呼び出しが完了していることを確認する必要があるとしてこれらの条件のために。ありがとう！

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

} 

Answer 1

alex vasiが示唆しているように、再帰的ではなく反復的なツリートラバースを考慮する必要があります。ただし、データセットが膨大で、データの処理に時間がかかる場合、UIがフリーズすることがあります。したがって、処理を非同期で行うこともできます。ここ

はアレックスの例の変形例は次のとおり上記

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

コードスニペットは、このように自分自身を更新するために、UIにいくつかの時間を与え、非同期反復トラバースを行います。

jsFiddleここでは、同期トラバースと非同期トラバースの違いに気付くことができます。同期トラバースにより、ブラウザーは短時間停止しますが、非同期バージョンでは、ブラウザーはツリーの処理中に呼吸を停止します。更新jsFiddle

Answer 2

タイムアウトを使用してツリーを真剣に歩いていますか？あなたは反復的ではなく反復的なツリートラバーサルを使うことを考えましたか？

例：

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

またthis so questionとwikipeida articleを参照してください。