如何在JavaScript中实现最快的自下而上的树转换器？我应该独自管理记忆吗？

Question

我正在JavaScript中实现一个自下而上的树转换器.它将用于超级组合器减速器的解释器，因此该算法必须尽可能快，因为它影响到构建在上面的每一个程序。这是我目前的实现：

function transform(tree,fn){
    var root = tree,
        node = tree,
        child,
        parent,
        is_node,
        dir;
    root.dir = 0;
    while(true) {
        is_node = typeof(node)==="object";
        dir = is_node ? node.dir : 2;
        if (dir < 2)
            child = node[dir],
            node.dir++,
            child.parent = parent = node,
            child.dir = 0,
            node = child;
        else if ((changed = fn(node))!==undefined)
            changed.parent = parent,
            changed.dir = 0,
            node = changed;
        else
            if (!parent)
                return node;
            else
                parent[parent.dir-1] = node,
                node = parent,
                parent = node.parent;
    };
};

// TEST
var tree = [[1,2],[[3,4],[5,6]]];
console.log(
    JSON.stringify(transform(tree,function(a){
        if (a[0]===1) return [3,[5,5]];
        if (a[0]===5) return 77;
    })) === "[[3,77],[[3,4],77]]");

这显然远远不是最优的。如何使变压器尽可能快？也许我不需要寻找更快的算法，而是可以自己管理内存，并使用asm.js。

Answer 1

你有几个选择，从最简单，但最慢到最快，但最棘手。

使用正则JavaScript

这就是你现在所做的。看看你的算法，我看不出有什么东西能真正显示出速度的微不足道的增长。

使用asm.js

对您来说，使用asm.js可能是一个选项。这将提供一个提速。您不会深入了解这个系统在何处使用的详细信息，但是如果它能够工作，那么实现这样的系统应该不会太困难。您可能会看到性能的提高，但取决于您计划如何使用它，它可能没有您想要的那么大(对于这样的东西，您可能会看到速度增长了50%-500%，这取决于代码的效率)。

用不同的、编译的、类型化的语言构建它。

如果速度确实很高，取决于您的用例，最好用不同的语言编写这个程序(或者至少编写这个函数)。然后，您可以在服务器上运行此编译脚本，并通过web服务与其通信。

如果您需要在短时间内转换树的次数很大，那么由于发送和接收数据所需的时间不多，这不会有太大的帮助。但是，如果您只执行相对较少但运行时间较长的树转换，则可以看到性能上的巨大好处。编译、类型化语言(C++、Java等)总是比解释的、无类型的语言(如JavaScript )具有更好的性能。

在服务器上运行它的另一个好处是，您通常可以将更多的马力投在服务器上，因为您可以将其编写为多线程，甚至可以在一组机器上运行，而不是仅在一台机器上运行(用于高端构建)。使用JavaScript，您通常只限于一个线程，也受终端用户计算机的限制.