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

Question

在需要计数组合的Node.js服务器上，我有一些性能敏感的代码。在这就是答案中，我使用了这个简单的递归函数来计算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的建议，使用马提斯以更高的精度预计算对数，然后将其转换回常规的JavaScript Numbers (通常是双精度64位浮点数)。

Answer 1

永远不要计算阶乘，它们增长得太快了。相反，计算您想要的结果。在这种情况下，您需要二项数，它有一个非常简单的几何结构:您可以根据需要构建帕斯卡三角，并使用简单的算术来完成它。

从1和1开始。下一行有1开始，1+1在中间，1在结尾: 1, 2，1。下一行:1在开始，前两个项的和在点2，后面两个项的和在点3，和1在结尾: 1,3,3,1。下一行: 1，然后是1+3=4，然后是3+3=6，然后是3+1=4，然后是1，等等。正如你所看到的，没有阶乘，对数，甚至乘法:只是超快的加法与干净的整数。非常简单，您可以手工构建一个庞大的查找表。

你应该这么做。

永远不要在代码中计算您可以手工计算的内容，只需将其作为常量立即查找；在这种情况下，为n=20周围的某个内容编写表是非常简单的，然后您就可以将它用作“启动LUT”，甚至可能永远也不会访问高行。

但是，如果您确实需要它们，或者更多，那么因为您无法构建无限查找表，所以您会妥协:首先是预先指定的LUT，然后是一个函数，它可以“填充”到您需要的某个术语，而这个词还没有包含在其中：

// step 1: a basic LUT with a few steps of Pascal's triangle
const 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.
module.exports = 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];
};

因为这是一个ints数组，所以内存占用很小。对于许多涉及二项式的工作，我们实际上每个整数甚至不需要超过两个字节，这使得这是一个微小的查找表:在需要比n=19高的二进制数之前，我们不需要超过2个字节，而n=19的完整查找表只需要380个字节。与程序的其他部分相比，这一点都不重要。即使我们允许32位ints，我们也可以以2380字节的速度到达n=35。

所以查找是快速的:对于先前计算的值，(n*(n+1))/2步骤(如果我们根本没有LUT )(在大O表示法中，那就是O(N 2)，但大O表示法几乎永远不是正确的复杂度度量)，或者在我们所需要的项之间的某个位置上查找是快速的。为您的应用程序运行一些基准测试，这将告诉您初始LUT应该有多大，只需编写(认真的)硬代码。这些都是常量，它们正是应该被硬编码的值)，并且保持生成器在附近，以防万一。

但是，请记住，您在JavaScript域，并且受到JavaScript数值类型：整数只上升到2^53的约束，除此之外，整数属性(每个n都有一个不同的m=n+1，因此m-n=1)没有得到保证。这几乎不应该是一个问题，但是:一旦我们达到了这个极限，我们就会处理你根本不应该使用的二项式系数。

Answer 2

以下算法的运行时复杂度为O(1)，给出了具有空间复杂度O(n)的日志因子线性查找表。

将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, 19.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)等上求和，我们可以用一个与log(k!)完全相同的sum_of_logs(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!)而不是查找表，并且在运行时和空间复杂度O(1)中仍然可以得到上述计算的12个重要数字。

​

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 3

利用Pascal三角形是一种快速计算n选择k的方法。

我所知道的最快的方法是利用"关于因子计算的复杂性“的结果。只需计算所有3个阶乘，然后执行两个除法操作，每个除法操作都使用复杂度M(n logn)。