n的有效计算在Node.js中选择k

Question

我在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的解决方案运行了一些测试之后,事实证明,虽然两者都比我提出的迭代方法快得多,但Mike使用Pascal三角形的方法似乎比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(总是双精度64位浮点数).

Answer 1

给定具有空间复杂度O(n)的对数阶乘的线性查找表,以下算法具有O(1)的运行时复杂度.

将n和k限制在范围[0,1000]是有意义的,因为binomial(1000, 500)已经危险地接近Number.MAX_VALUE.因此,我们需要一个大小为1000的查找表.

在现代JavaScript引擎上,n个数字的紧凑数组的大小为n*8个字节.因此,完整的查找表需要8千字节的内存.如果我们将输入限制在[0,100]范围内,则表只占用800个字节.

var logf = [0, 0, 0.6931471805599453, 1.791759469228055, 3.1780538303479458, 4.787491742782046, 6.579251212010101, 8.525161361065415, 10.60460290274525, 12.801827480081469, 15.104412573075516, 17.502307845873887, 9.987214495661885, 22.552163853123425, 25.19122118273868, 27.89927138384089, 30.671860106080672, 33.50507345013689, 36.39544520803305, 39.339884187199495, 42.335616460753485, 45.38013889847691, 48.47118135183523, 51.60667556776438, 54.78472939811232, 58.00360522298052, 61.261701761002, 64.55753862700634, 67.88974313718154, 71.25703896716801, 74.65823634883016, 78.0922235533153, 81.55795945611504, 85.05446701758152, 88.58082754219768, 92.1361756036871, 95.7196945421432, 99.33061245478743, 102.96819861451381, 106.63176026064346, 110.32063971475739, 114.0342117814617, 117.77188139974507, 121.53308151543864, 125.3172711493569, 129.12393363912722, 132.95257503561632, 136.80272263732635, 140.67392364823425, 144.5657439463449, 148.47776695177302, 152.40959258449735, 156.3608363030788, 160.3311282166309, 164.32011226319517, 168.32744544842765,  172.3527971391628, 176.39584840699735, 180.45629141754378, 184.53382886144948, 188.6281734236716, 192.7390472878449, 196.86618167289, 201.00931639928152, 205.1681994826412, 209.34258675253685, 213.53224149456327, 217.73693411395422, 221.95644181913033, 226.1905483237276, 230.43904356577696, 234.70172344281826, 238.97838956183432, 243.2688490029827, 247.57291409618688, 251.8904022097232, 256.22113555000954, 260.5649409718632, 264.9216497985528, 269.2910976510198, 273.6731242856937, 278.0675734403661, 282.4742926876304, 286.893133295427, 291.3239500942703, 295.76660135076065, 300.22094864701415, 304.6868567656687, 309.1641935801469, 313.65282994987905, 318.1526396202093, 322.66349912672615, 327.1852877037752, 331.7178871969285, 336.26118197919845, 340.815058870799, 345.37940706226686, 349.95411804077025, 354.5390855194408, 359.1342053695754, 363.73937555556347];

function binomial(n, k) {
    return Math.exp(logf[n] - logf[n-k] - logf[k]);
}

console.log(binomial(5, 3));

说明

从原始迭代算法开始,我们首先用对数之和替换产品:

function binomial(n, k) {
    var logresult = 0;
    for (var i = 1; i <= k; i++) {
        logresult += Math.log(n + 1 - i) - Math.log(i);
    }
    return Math.exp(logresult);
}

我们的循环现在总结超过k项.如果我们重新排列总和,我们可以很容易地看到我们总结了连续的对数log(1) + log(2) + ... + log(k)等,我们可以用sum_of_logs(k)实际上相同的对数替换log(k!).预先计算这些值并将它们存储在我们的查找表中,logf然后得到上述单行算法.

计算查找表:

我建议以更高的精度预先计算查找表,并将结果元素转换为64位浮点数.如果您不需要那么一点额外的精度或者想在客户端运行此代码,请使用:

var size = 1000, logf = new Array(size);
logf[0] = 0;
for (var i = 1; i <= size; ++i) logf[i] = logf[i-1] + Math.log(i);

数值精度:

通过使用对数阶乘,我们避免了存储原始阶乘所固有的精度问题.

我们甚至可以使用斯特灵公式为log(n!),而不是一个查找表,仍然获得了上述计算12个显著数字均运行时间和空间复杂度为O(1) :

function logf(n) {
    return n === 0 ? 0 : (n + .5) * Math.log(n) - n + 0.9189385332046728 + 0.08333333333333333 / n - 0.002777777777777778 * Math.pow(n, -3);
}

function binomial(n , k) {
    return Math.exp(logf(n) - logf(n - k) - logf(k));
}

console.log(binomial(1000, 500)); // 2.7028824094539536e+299

Answer 2

永远不要计算阶乘,它们增长太快.而是计算你想要的结果.在这种情况下,您需要二项式数字,它具有非常简单的几何结构:您可以根据需要构建pascal三角形,并使用简单算术进行.

从[1]和[1,1]开始.下一行在开始时为[1],在中间为[1 + 1],在末尾为[1]:[1,2,1].下一行:[1]在开始时,第2点的前两个项的总和,第3点的下两个项的总和,以及[1,3]的结尾:[1,3,3,1].下一行:[1],然后1 + 3 = 4,然后3 + 3 = 6,然后3 + 1 = 4,最后是[1],依此类推,依此类推.正如您所看到的,没有阶乘,对数甚至乘法:只需要使用干净整数进行超快速加法.如此简单,您可以手动构建一个庞大的查找表.

你应该.

永远不要在代码中计算你可以手动计算什么,只需硬编码,在这种情况下写出表格最多说n = 20绝对是微不足道的,然后你可以把它当作你的"起始LUT",甚至可能永远不需要那些高排.

但是,如果你确实需要它们,或者更多,那么因为你不能构建一个无限的查找表而你会妥协:你从一个预先指定的LUT开始,一个可以"填充"到某个术语的函数你需要它尚未进入:

module.exports = (function() {
  // step 1: a basic LUT with a few steps of Pascal's triangle
  var binomials = [
    [1],
    [1,1],
    [1,2,1],
    [1,3,3,1],
    [1,4,6,4,1],
    [1,5,10,10,5,1],
    [1,6,15,20,15,6,1],
    [1,7,21,35,35,21,7,1],
    [1,8,28,56,70,56,28,8,1],
    ...
  ];

  // step 2: a function that builds out the LUT if it needs to.
  function binomial(n,k) {
    while(n >= binomials.length) {
      let s = binomials.length;
      let nextRow = [];
      nextRow[0] = 1;
      for(let i=1, prev=s-1; i<s; i++) {
        nextRow[i] = binomials[prev][i-1] + binomials[prev][i];
      }
      nextRow[s] = 1;
      binomials.push(nextRow);
    }
    return binomials[n][k];
  }

  return binomial;
}());

由于这是一个整数数组,因此内存占用很小.对于涉及二项式的大量工作,我们实际上甚至不需要每个整数超过两个字节,这使得这是一个分钟查找表:我们不需要超过2个字节,直到您需要高于n = 19的二项式,并且直到n = 19的完整查找表占用了380个字节.与您的其他程序相比,这没什么.即使我们允许32位整数,我们也可以在2380字节内达到n = 35.

所以查找很快:如果我们根本没有LUT,则先前计算的值为O(常数),(n*(n + 1))/ 2步(大O表示法,即O(n²),但是大O符号几乎从来都不是正确的复杂性度量),而且介于两者之间我们需要的术语还不在LUT中.为您的应用程序运行一些基准测试,它将告诉您初始LUT应该有多大,只需硬编码(严重.这些是常量,它们正是应该硬编码的那种值),并保留生成器为了以防万一.

但是,请记住,您处于JavaScript领域,并且您受JavaScript数字类型的约束:整数只能达到2 ^ 53,超出整数属性(每个n都有一个明显的m=n+1这样m-n=1)不能得到保证.但这应该不是一个问题:一旦我们达到了这个极限,我们就会处理你永远不应该使用的二项式系数.