在Node.js中高效地选择n [英] Efficient computation of n choose k in Node.js

问题描述

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

I have some performance sensitive code on a Node.js server that needs to count combinations. From this SO answer, I used this simple recursive function for computing n choose k:

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

然后，因为我们都知道迭代几乎总是比递归快，所以我写了这个函数基于乘法公式：

Then since we all know iteration is almost always faster than recursion, I wrote this function based on the multiplicative formula:

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

我跑了几个基准在我的计算机上。以下是其中之一的结果：

I ran a few benchmarks on my machine. Here are the results of just one of them:

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倍（至少在我的机器上）。

The results consistently showed that the iterative method is indeed about 3 to 4 times faster than the recursive method in Node.js (at least on my machine).

大概足够快以满足我的需求，但是有什么方法可以使其更快吗？我的代码必须非常频繁地调用此函数，有时它们的 n 和 k 值相当大，因此更好。

This is probably fast enough for my needs, but is there any way to make it faster? My code has to call this function very frequently, sometimes with fairly large values of n and k, so the faster the better.

使用le_m和Mike的解决方案再运行了几次测试后，事实证明两者都比我提出的迭代方法快得多，迈克使用Pascal三角形的方法似乎比le_m的对数表方法稍快。

After running a few more tests with le_m's and Mike's solutions, it turns out that while both are significantly faster than the iterative method I proposed, Mike's method using Pascal's triangle appears to be slightly faster than le_m's log table method.

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倍。

The logarithmic look up method has been around 26-28 times faster than the iterative method in my tests, and the method using Pascal's triangle has been about 1.3 to 1.8 times faster than the logarithmic look up method.

请注意，我遵循le_m的建议，即使用 mathjs 以更高的精度预先计算对数，然后将它们转换回常规JavaScript Number s（始终为双精度64位浮点数）。

Note that I followed le_m's suggestion of pre-computing the logarithms with higher precision using mathjs, then converted them back to regular JavaScript Numbers (which are always double-precision 64 bit floats).

推荐答案

从不计算阶乘，它们增长太快。而是计算您想要的结果。在这种情况下，您需要具有非常简单的几何构造的二项式数：您可以构建 pascal的三角形，并根据需要使用普通算术进行操作。

Never compute factorials, they grow too quickly. Instead compute the result you want. In this case, you want the binomial numbers, which have an incredibly simple geometric construction: you can build pascal's triangle, as you need it, and do it using plain arithmetic.

从[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]，依此类推。如您所见，没有阶乘，对数，甚至没有乘法：只是超快速加法和干净的整数。如此简单，您可以手动构建一个庞大的查找表。

Start with [1] and [1,1]. The next row has [1] at the start, [1+1] in the middle, and [1] at the end: [1,2,1]. Next row: [1] at the start, the sum of the first two terms in spot 2, the sum of the next two terms in spot three, and [1] at the end: [1,3,3,1]. Next row: [1], then 1+3=4, then 3+3=6, then 3+1=4, then [1] at the end, and so on and so on. As you can see, no factorials, logarithms, or even multiplications: just super fast addition with clean integer numbers. So simple, you can build a massive lookup table by hand.

而且应该。

从不计算编写您可以手动计算的内容，并将其作为常量进行立即查找；在这种情况下，写出最多n = 20左右的表绝对是微不足道的，然后可以将其用作启动LUT，甚至可能永远都不会访问高行。

Never compute in code what you can compute by hand and just include as constants for immediate lookup; in this case, writing out the table for up to something around n=20 is absolutely trivial, and you can then just use that as your "starting LUT" and probably never even access the high rows.

但是，如果您确实需要它们，或者更多，那么因为您无法构建无限的查找表而受到损害：您从预先指定的LUT开始，然后使用一个可以填充它的函数，从某种意义上说，您还需要它：

But, if you do need them, or more, then because you can't build an infinite lookup table you compromise: you start with a pre-specified LUT, and a function that can "fill it up" to some term you need that's not in it yet:

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;
}());

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

Since this is an array of ints, the memory footprint is tiny. For a lot of work involving binomials, we realistically don't even need more than two bytes per integer, making this a minute lookup table: we don't need more than 2 bytes until you need binomials higher than n=19, and the full lookup table up to n=19 takes up a measly 380 bytes. This is nothing compared to the rest of your program. Even if we allow for 32 bit ints, we can get up to n=35 in a mere 2380 bytes.

因此查找速度很快：对于以前计算的值，如果我们根本没有LUT，则（n *（n + 1））/ 2个步骤（以大O表示法，将是O（n²），但大O表示法几乎永远不是正确的复杂性度量），在介于两者之间的某个术语中，我们需要的不在LUT中。为您的应用程序运行一些基准测试，这将告诉您初始LUT应该有多大，只需简单地硬编码（严重。这些是常量，它们完全是应该进行硬编码），并保持生成器在周围以防万一。

So the lookup is fast: either O(constant) for previously computed values, (n*(n+1))/2 steps if we have no LUT at all (in big O notation, that would be O(n²), but big O notation is almost never the right complexity measure), and somewhere in between for terms we need that aren't in the LUT yet. Run some benchmarks for your application, which will tell you how big your initial LUT should be, simply hard code that (seriously. these are constants, they're are exactly the kind of values that should be hard coded), and keep the generator around just in case.

但是，请记住您在JavaScript领域，并且受到JavaScript数值类型的约束：整数最多只能达到2 ^ 53 ，超出整数属性（每个 n 具有明显的 m = n + 1 ，因此不能保证 mn = 1 ）。但是，这几乎永远不会成为问题：一旦达到该极限，我们就将处理甚至不应该使用的二项式系数。

However, do remember that you're in JavaScript land, and you are constrained by the JavaScript numerical type: integers only go up to 2^53, beyond that the integer property (every n has a distinct m=n+1 such that m-n=1) is not guaranteed. This should hardly ever be a problem, though: once we hit that limit, we're dealing with binomial coefficients that you should never even be using.

这篇关于在Node.js中高效地选择n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！