我在一个Node.js服务器上有一些性能敏感的代码需要计算组合数。从这个SO答案中,我使用了这个简单的递归函数来计算n个选择k个:
function choose(n, k) {
if (k === 0) return 1;
return (n * choose(n-1, k-1)) / k;
}
因为我们都知道迭代几乎总是比递归更快,所以我根据乘法公式编写了这个函数:
function choosei(n,k){
var result = 1;
for(var i=1; i <= k; i++){
result *= (n+1-i)/i;
}
return result;
}
我在自己的机器上运行了几个 基准测试。以下是其中一个测试的结果:
Recursive x 178,836 ops/sec ±7.03% (60 runs sampled)
Iterative x 550,284 ops/sec ±5.10% (51 runs sampled)
Fastest is Iterative
结果始终表明,在Node.js中,迭代方法确实比递归方法快3到4倍左右(至少在我的机器上)。
这对我的需求来说可能足够快了,但有没有办法让它更快呢?我的代码需要频繁调用这个函数,有时候n和k的值相当大,所以速度越快越好。
编辑
在使用le_m和Mike的解决方案进行了几次测试后,结果显示虽然两种方法都比我提出的迭代方法快得多,但是使用Pascal三角形的Mike方法似乎比le_m的对数表方法稍微快一些。
Recursive x 189,036 ops/sec ±8.83% (58 runs sampled)
Iterative x 538,655 ops/sec ±6.08% (51 runs sampled)
LogLUT x 14,048,513 ops/sec ±9.03% (50 runs sampled)
PascalsLUT x 26,538,429 ops/sec ±5.83% (62 runs sampled)
Fastest is PascalsLUT
在我的测试中,使用对数查找方法比迭代方法快了26-28倍,而使用Pascal三角形的方法比对数查找方法快1.3到1.8倍。
请注意,我按照le_m的建议使用mathjs预先计算了具有更高精度的对数,然后将它们转换回常规JavaScript Number
s(始终为双精度64位浮点数)。
fact(n) = max_known_fact_value(n) * [i for evey int for max_known_fact_int(n) to n]
,這將節省大量時間。 - gbtimmon