为什么JS中的简单因子算法要比Python或R快得多？

Question

为什么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代表循环,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在这个计算中要快得多？

Answer 1

详细说来,我只能说R,但这是我的2ct.也许你可以分析其他语言中发生的事情,然后得出结论.

首先,你的R版本factorialRecursive不是递归的:你调用factorial (n - 1)使用$\Gamma $函数的R' .

以下是我的基准测试结果,包括通过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环矢量.更进一步,即使用cumprod函数R提供的累积产品大大加快了计算速度:与R的基本实现$\Gamma $函数相比,我们在2 - 3的范围内(你可能会认为这是作弊因为cumprod可能后面有一个C函数 - 但是然后R解释器用C语言编写,所以区别在这里有点模糊).

我认为,基本上你在这里付出了很大的代价,因为它是为了交互式使用量身定制的所有安全检查.有关Python中的某些相关问题,请参阅" 为什么Python代码在函数中运行得更快？ ".

带回家消息1: R中的递归和显式循环只有在每个函数调用/循环内部的计算足够复杂时才是合理的选项,因此开销无关紧要.

带回家的消息2:了解你的数学可以提供很大的帮助:R factorial具有恒定的运行时间(在我的笔记本电脑上大约1.8μs):

带回家的消息3:然而,这种加速是否很重要？对于阶乘,可能不是:图表遍及x的整个范围,其中结果可以由double保持.两个函数的计算都不需要超过ca. 5μs.即使你的"最差"功能也会在500μs内完成.如果要计算大量因子,则使用查找表:170个元素的向量不是那么大.factorialCumprod为您计算5μs内的整个事物.
如果您在计算时碰巧需要更大数字的阶乘,可能您应该努力重新解决问题 - 我总是希望数字问题就在后面(即使您可以使用大整数 - 在R中有包gmp和Rmpfr)

PS:如果您想知道Fibonacci数字不能被类似的方便cumprod或cumsum调用所取代,请参阅这些博客文章关于递归和迭代计算(世界上最差的算法？)和封闭形式计算(使用计算Fibonacci数字)比奈的公式)

Answer 2

我认为主要区别在于Python有bignums而Javascript没有(它使用双IEEE754浮点).

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

公平地说,您需要找到并使用JS的bignum库.看到这个问题.