5

我正在使用一种可以翻译成 JavaScript 的语言。为了避免一些堆栈溢出，我通过将某些函数转换为 for 循环来应用尾调用优化。令人惊讶的是，转换并不比递归版本快。

http://jsperf.com/sldjf-lajf-lkajf-lkfadsj-f/5

递归版本：

(function recur(a0,s0){
    return a0==0 ? s0 : recur(a0-1, a0+s0)
})(10000,0)

尾调用优化后：

ret3 = void 0;
a1   = 10000;
s2   = 0;
(function(){
    while (!ret3) {
        a1 == 0 
            ? ret3     = s2
            : (a1_tmp$ = a1 - 1 ,
               s2_tmp$ = a1 + s2,
               a1      = a1_tmp$,
               s2      = s2_tmp$);
     }
})();
ret3;

使用 Google Closure Compiler 进行一些清理后：

ret3 = 0;
a1   = 1E4;
for(s2 = 0; ret3 == 0;)
    0 == a1 
        ? ret3     = s2 
        : (a1_tmp$ = a1 - 1 ,
           s2_tmp$ = a1 + s2,
           a1      = a1_tmp$,
           s2      = s2_tmp$);
c=ret3;

递归版本比“优化”版本更快！如果递归版本必须处理数千个上下文更改，这怎么可能？

4

3 回答 3

5

优化不仅仅是尾调用优化。

例如，我注意到您正在使用两个临时变量，而您只需要：

s2 += a1;
a1--;

仅此一项就实际上将操作次数减少了三分之一，从而使性能提高了 50%

从长远来看，在尝试优化操作本身之前优化正在执行的操作非常重要。

编辑：这是一个更新的jsperf

于 2013-10-05T22:32:00.923 回答
2

递归版本内部并没有您期望的那么多上下文更改，因为命名函数recur包含在其recur自身的范围内/它们共享相同的范围。原因与 JavaScript 引擎评估范围的方式有关，并且有很多网站解释了这个主题，所以我不会在这里做。再看一遍，您会注意到这recur也是一个所谓的“纯”函数，这基本上意味着只要内部执行运行，它就不必离开自己的范围（简单地说：直到它返回一个值）。这两个事实使它基本上很快。我只想在这里提一下，第一个示例是所有三个中唯一优化的尾调用 - tc 优化只能在递归函数中完成，这是唯一的递归函数。

然而，再看第二个例子（不是双关语）发现，“优化器”让你的情况变得更糟，因为它通过将操作拆分为前一个纯函数来引入范围

  • 变量而不是参数
  • 一个while循环
  • 一个 IIFE（立即调用的函数表达式），用于分隔引入的内部和外部变量

这导致性能下降，因为现在引擎必须处理 10000 次上下文更改。

说实话我不知道为什么第三个例子的性能比递归的差，所以也许它与：

  • 您使用的浏览器（曾经尝试过另一个浏览器并比较结果？）
  • 变量数
  • 由 for 循环创建的堆栈帧（虽然从未听说过），这与第一个示例有关：JS 引擎解释一个纯递归函数，直到它找到一个返回语句。如果语句后面的最后一件事是函数调用，则计算要作为参数传递的任何表达式（如果有）和变量，调用函数并丢弃框架
  • 有些东西，只有浏览器供应商才能真正告诉你:)
于 2015-04-01T16:39:39.000 回答
2

正如Kolink所说，您的代码所做的只是简单地添加n到总数中，减少n1，然后循环直到n达不到0

所以就这样做：

n = 10000, o = 0; while(n) o += n--;

它比递归版本更快更易读，当然输出相同的结果

于 2013-10-06T00:04:46.643 回答