javascript - 在 Node.js 中高效计算 n 选择 k

Question

我在 Node.js 服务器上有一些性能敏感代码需要计算组合。来自 this SO answer ，我使用这个简单的递归函数来计算 n 选择 k:

function choose(n, k) {
    if (k === 0) return 1;
    return (n * choose(n-1, k-1)) / k;
}

因为我们都知道迭代几乎总是比递归快，所以我根据 multiplicative formula 编写了这个函数:

function choosei(n,k){
    var result = 1;
    for(var i=1; i <= k; i++){
        result *= (n+1-i)/i;
    }
    return result;
}

我跑了几个benchmarks在我的机器上。以下是其中一个的结果:

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 三 Angular 形的方法似乎比 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 倍，使用帕斯卡三 Angular 形的方法比对数查找方法快大约 1.3 到 1.8 倍。

请注意，我遵循了 le_m 的建议，即使用 mathjs 以更高的精度预先计算对数。 ，然后将它们转换回常规的 JavaScript Number(始终为 double-precision 64 bit floats)。

Answer 1

永远不要计算阶乘，它们增长太快。而是计算您想要的结果。在这种情况下，您需要二项式数，它具有非常简单的几何构造:您可以构建 pascal's triangle ，根据需要，使用简单的算术来完成。

从 [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];
};

由于这是一个整数数组，因此内存占用很小。对于很多涉及二项式的工作，我们实际上每个整数甚至不需要超过两个字节，这使它成为一个极小查找表:我们不需要超过 2 个字节，直到您需要更高的二项式比 n=19，并且直到 n=19 的完整查找表只占用区区 380 个字节。与程序的其余部分相比，这不算什么。即使我们允许 32 位整数，我们也可以在仅 2380 字节的情况下达到 n=35。

所以查找速度很快:对于先前计算的值，要么是 O(constant)，要么是 (n*(n+1))/2 步，如果我们根本没有 LUT(在大 O 表示法中，那将是 O(n² )，但大 O 表示法几乎从来不是正确的复杂性度量)，对于我们需要但尚未在 LUT 中的术语，介于两者之间。为您的应用程序运行一些基准测试，这将告诉您您的初始 LUT 应该有多大，只需硬编码(说真的。这些是常量，它们正是 应该 进行硬编码)，并保留生成器以防万一。

但是，请记住，您是在 JavaScript 领域，并且受到 JavaScript 数字类型的限制:integers only go up to 2^53 ，除此之外，不保证整数属性(每个 n 都有一个不同的 m=n+1 使得 m-n=1)。不过，这几乎不会成为问题:一旦达到该限制，我们就会处理您永远不应该使用的二项式系数。