Javascript:如何使用异步递归树遍历来控制流？

Question

我需要在树上进行递归,以使用异步操作在特定节点上执行操作.如何控制流量,以便在完成后可以访问节点？

这是一个示例情况:

data = {
  name: "deven",
  children: [
    { name: "andrew" },
    { name: "donovan" },
    { name: "james",
      children: [
        { name: "donatello" },
        { name: "dan" }
      ]
    },
    { name: "jimmy",
      children: [
        { name: "mike" },
        { name: "dank" }
      ]
    }
  ]
};

我有一个函数,它的目标是遍历树并将所有以'd'开头的名称大写.之后,我想将树传递给另一个函数来做更多工作(可能删除所有名称以'a'开头的节点),但只有在完成初始处理之后:

function capitalize_d(node) {
    if(node.name === "d") {
        node.name = node.name.toUpperCase();
    }

    if(node.children != null) {
        for(var i = 0; i < node.children.length; i++) {
            capitalize_d(node.children[i]);
        }
    }
}

function remove_a(node) {
}

capitalize_d(data);

// Should only get called after all the d's have been capitalized.
remove_a(data);

上面的代码工作正常,因为capitalize_d是阻塞的.如果capitalize_d异步递归,我们如何保证remove_a在完成后调用？请注意setTimeout电话capitalize_d.

function capitalize_d(node) {
    setTimeout(function() {

        if(node.name === "d") {
            node.name = node.name.toUpperCase();
        }

        if(node.children != null) {
            for(var i = 0; i < node.children.length; i++) {
                capitalize_d(node.children[i]);
            }
        }

    }, 1);
}

function remove_a(node) {
}

capitalize_d(data);

// Should only get called after all the d's have been capitalized.
remove_a(data);

问题是我们对树的不同分支的处理同时被解雇了,并且无法确定它何时最终完成处理树.

我怎么解决这个问题？

Answer 1

让我总结一下我对您的要求的理解：

• 您有一个数据树，其中每个节点都可以通过一组操作异步更改（capitalize_d在remove_a您的示例中），
• 您需要确保每个节点都已执行给定操作，然后才允许执行下一个操作。

我花了 10 年或更长时间来设计实时嵌入式软件，相信我，这个领域的要求比大多数网络程序员一生中经历的任何事情都更加严峻和严峻。这让我警告你，你似乎走错了路。

正如我可以想象的那样，您的问题是以某种有意义的结构组织一组单独的数据。某些进程收集随机信息（在示例中称为“节点”），并且在某些时候您希望将所有这些节点放入一致的整体数据结构（示例中的分层树）。

换句话说，您手头有三项任务：

• 异步收集节点的数据采集过程
• 数据生产过程将呈现一致、精致的数据树
• 一个控制器进程，将同步数据采集和生产（如果上述两个进程足够智能，可能直接是用户界面，但不要太依赖它）。

我的建议：不要尝试同时进行采集和生产。

只是为了让您了解您即将面临的噩梦：

• 根据操作的触发方式，给定操作有可能永远不会完全处理树。假设控制软件忘记调用capitalize_d一些节点，remove_a将永远不会获得绿灯

• 相反，如果您随机对树进行射击，则某些节点很可能会被多次处理，除非您跟踪操作覆盖范围以防止对给定节点应用两次相同的转换

• 如果您希望remove_a处理开始，您可能必须阻止控制软件发送更多capitalize_d请求，否则指示灯可能会永远保持红色。您最终将以一种或另一种方式对您的请求进行流量控制（或者更糟：您不会做任何事情，并且如果操作流程偏离您偶然遇到的最佳点，您的系统可能会死机） ）。

• 如果某个操作改变了树的结构（remove_a显然是这样），则必须防止并发访问。至少，您应该锁定从remove_a正在处理的节点开始的子树，否则您将允许处理可能被异步更改和/或销毁的子树。

嗯，这是可行的。我见过优秀的年轻人通过做这个主题的变体赚大钱。他们通常每周也会花几个晚上在电脑前吃披萨，但是嘿，这就是你如何区分冷酷的黑客和吃乳蛋饼的人群的方法，对吧？

我认为您在这里发布这个问题意味着您真的不想这样做。现在，如果你的老板确实这么做了，好吧，引用一位著名的机器人的话，我不能在你的机会上对你撒谎，但是……我对你表示同情。

现在说真的，伙计们……这就是我解决问题的方法。

1）在给定时间点拍摄数据快照

您可以使用尽可能多的标准清除原始数据（上次数据采集太旧，输入不正确，任何允许您构建尽可能最小的树的东西）。

2) 使用快照构建树，然后在此给定快照上顺序应用 Capitalize_d、remove_a 和 Camelize_z 操作。

同时，数据采集过程将继续收集新节点或更新现有节点，准备拍摄下一个快照。

此外，您还可以向前推进一些处理。显然capitalize_d没有利用树结构的任何优势，因此您可以capitalize_d在构建树之前将其应用于快照中的每个节点。您甚至可以更早地应用一些转换，即对每个收集的样本进行转换。这可以为您节省大量处理时间和代码复杂性。

最后以一些理论上的废话结束，

• 您的方法是将数据树视为一个共享对象，它应该支持数据采集和数据生产过程的并发访问，
• 我的方法是使数据采集过程（异步）向数据生产过程提供一致的数据集，然后数据生产过程可以顺序处理所述数据集。

数据生成过程可以按需触发（例如，当最终用户单击“向我展示一些东西”按钮时），在这种情况下，反应性会相当差：用户将被困在观看沙漏或任何 Web2.0 性感旋转的东西构建和处理树所需的时间（假设 7-8 秒）。

或者您可以定期激活数据生成过程（每 10 秒向其提供一个新快照，该时间段安全地高于数据集的平均处理时间）。然后，“向我显示一些内容”按钮将仅显示最后一组已完成的数据。立即得到答案，但数据可能比上次收到的样本早 10 秒。

我很少看到这种情况被认为是不可接受的，特别是当你生成一堆复杂的数据时，操作员需要几十秒的时间来消化。

理论上，我的方法会失去一些反应性，因为处理的数据会稍微过时，但并发访问方法可能会导致软件速度甚至更慢（而且肯定会变大 5-10 倍且错误较多）。