3

为什么 JavaScript 在这种计算中要快得多？

我一直在用四种简单的阶乘算法进行一些测试：递归、尾递归、while循环和for循环。我已经用 R、Python 和 Javascript 进行了测试。

我测量了每个算法计算 150 个阶乘、5000 次所花费的时间。对于 RI 使用system.time(replicate())。对于 Python，我使用time.clock()了 、resource模块和timeit模块。对于 JavaScript，我使用console.time()、 Date().getMilliseconds()和Date().getTime()，通过终端使用节点运行脚本。

这从来不是为了比较语言之间的运行时间，而是为了查看哪种形式（递归、尾递归、for 循环或 while 循环）对于我正在学习的语言来说更快。不过，JavaScript 算法的性能引起了我的注意。

您可以在此处查看 4 种不同的阶乘算法和测量实现：

R阶乘算法和性能。

Python 阶乘算法和性能。

JavaScript 阶乘算法和性能。

在以下示例中，f 代表 for 循环，w 代表 while 循环。

R 的结果是：

Running time of different factorial algorithm implementations, in seconds.
Compute 150 factorial 5000 times:

factorialRecursive()
 user  system elapsed 
0.044   0.001   0.045 

factorialTailRecursive()
 user  system elapsed 
3.409   0.012   3.429 

factorialIterW()
 user  system elapsed 
2.481   0.006   2.488 

factorialIterF()
 user  system elapsed 
0.868   0.002   0.874

Python的结果是：

Running time of different factorial algorithm implementations.
Uses timeit module, resource module, and a custom performance function.

Compute 150 factorial 5000 times:

factorial_recursive()
timeit:          0.891448974609
custom:          0.87
resource user:   0.870953
resource system: 0.001843

factorial_tail_recursive()
timeit:          1.02211785316
custom:          1.02
resource user:   1.018795
resource system: 0.00131

factorial_iter_w()
timeit:          0.686491012573
custom:          0.68
resource user:   0.687408
resource system: 0.001749

factorial_iter_f()
timeit:          0.563406944275
custom:          0.57
resource user:   0.569383
resource system: 0.001423

JavaScript 的结果是：

Running time of different factorial algorithm implementations.
Uses console.time(), Date().getTime() and Date().getMilliseconds()

Compute 150 factorial 5000 times:

factorialRecursive(): 30ms
Using Date().getTime(): 19ms
Using Date().getMilliseconds(): 19ms

factorialTailRecursive(): 44ms
Using Date().getTime(): 44ms
Using Date().getMilliseconds(): 43ms

factorialIterW(): 4ms
Using Date().getTime(): 3ms
Using Date().getMilliseconds(): 3ms

factorialIterF(): 4ms
Using Date().getTime(): 4ms
Using Date().getMilliseconds(): 3ms

如果我理解正确的话，没有办法使用 JS 代码测量 JavaScript 中的 CPU 时间，而上面使用的方法测量挂钟时间。

JavaScript 的挂钟时间测量比 Python 或 R 实现快得多。

例如，使用 for 循环的阶乘算法的挂钟运行时间：R：0.874s Python：0.57 s JavaScript：0.004s

为什么 JavaScript 在这种计算中要快得多？

4

2 回答 2

14

详细地说，我只能代表 R，但这是我的 2ct。也许您可以分析其他语言中发生的情况，然后得出结论。

但是，首先，您的 R 版本factorialRecursive不是递归的：您调用factorial (n - 1)使用 $\Gamma$ 函数的 R's。

这是我的基准测试结果，包括通过 gamma 函数的阶乘和表达迭代计算的更 Rish（矢量化）方式：

> factorialCumprod <- function(n) cumprod (seq_len (n))[n]

> microbenchmark(factorial(150), 
                 factorialRecursive(150), factorialTailRecursive(150), 
                 factorialIterF(150), factorialIterW(150), factorialCumprod (150),
                 times = 5000)
Unit: microseconds
                        expr     min      lq   median       uq       max neval
              factorial(150)   1.258   2.026   2.2360   2.5850    55.386  5000
     factorialRecursive(150) 273.014 281.325 285.0265 301.2310  2699.336  5000
 factorialTailRecursive(150) 291.732 301.858 306.4690 323.9295  4958.803  5000
         factorialIterF(150)  71.728  74.941  76.1290  78.7830  2894.819  5000
         factorialIterW(150) 218.118 225.102 228.0360 238.3020 78845.045  5000
       factorialCumprod(150)   3.493   4.959   5.3790   5.9375    65.444  5000

microbenchmark随机化函数调用的顺序。有时，与执行完全相同的函数调用的块相比，这确实会有所不同。

我想您可以在这里学到的是，在选择算法时，您需要考虑语言/语言实现的开发人员的设计决策。

众所周知，R 在递归时很慢。我发现一个简单的函数调用除了返回一个常量之外什么都不做，已经花费了大约 750 ns，所以 150 个函数调用已经占了递归算法时间的一半左右。直接调用 gamma (150 + 1)而不是间接调用会factorial (150)产生类似的差异。如果您想了解更多为什么会这样，您必须询问 R 核心团队。

循环在检查事情上花费了大量的开销。给你一个印象：

> for (i in 1 : 3) {
+    cat (i ," ")
+    i <- 10
+    cat (i ,"\n")
+ }
1  10 
2  10 
3  10

我认为保存这项工作本质上是矢量化函数加速的来源。

while和迭代版本之间的区别for可能来自循环中的向量化的n : 1事实for。更进一步，即使用cumprodR 为累积乘积提供的函数大大加快了计算速度：与 R 的基本实现 $\Gamma$ 函数相比，我们在 2 - 3 倍之内（你可能会说这是作弊，因为cumprod 后面可能有一个 C 函数 - 但是 R 解释器是用 C 编写的，所以这里的区别有点模糊）。

我认为基本上你在这里为 R 已经和必须进行的所有安全检查付出了沉重的代价，因为它是为交互式使用量身定制的。有关 Python 中的一些相关问题，请参阅“为什么 Python 代码在函数中运行得更快？ ”。

带回家的消息 1： R 中的递归和显式循环都是明智的选择，前提是每个函数调用/循环内部的计算足够复杂，因此开销无关紧要。

带回家的信息 2：了解你的数学可以极大地帮助：Rfactorial具有恒定的运行时间（在我的笔记本电脑上大约 1.8 微秒）：

微基准阶乘与 cumprod

带回家的信息 3：但是，加速是否重要？对于阶乘，可能不是：该图跨越了 x 的整个范围，其中结果可以由双精度数保持。这两个函数的计算时间不超过 ca。5微秒。即使是您的“最差”功能也可以在 500 μs 内完成。如果要计算大量的阶乘，则可以使用查找表：170 个元素的向量并没有那么大。factorialCumprod为您在 5 μs 内计算整个事情。
如果您碰巧需要更大数字的阶乘来进行计算，那么您可能应该努力重新制定问题-无论如何我希望数字问题就在拐角处（即使您可以使用大整数-在 R 中有包gmp 和 Rmpfr)

PS：如果您想知道斐波那契数不能被类似的方便cumprod或调用取代，请参阅这些关于递归和迭代计算（世界上最糟糕的算法？）和封闭形式计算（使用计算斐波那契数cumsum）的博客文章比奈公式）

于 2013-10-07T11:02:51.937 回答
9

我相信主要区别在于 Python 有bignums而 Javascript 没有（它使用双 IEEE754 浮点）。

所以你的程序不会计算同样的东西。使用 Python，他们计算阶乘的所有数字，而 JS 只是一个粗略的浮点近似，尾数约为 15 位。

公平地说，您需要找出并使用一个用于 JS 的 bignum 库。看到这个问题。

于 2013-10-07T04:38:24.903 回答