n的有效计算在Node.js中selectk
我有一些性能敏感的代码需要计数组合的Node.js服务器上。 从这个答案 ，我用这个简单的recursion函数来计算nselectk：
function choose(n, k) { if (k === 0) return 1; return (n * choose(n-1, k-1)) / k; } 那么既然我们都知道迭代几乎总是比recursion快，我写了这个函数的基础上的乘法公式 ：
function choosei(n,k){ var result = 1; for(var i=1; i <= k; i++){ result *= (n+1-i)/i; } return result; }
我在我的机器上运行了一些基准testing 。 下面是其中一个的结果：
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中的recursion方法（至less在我的机器上）要快3到4倍。
这可能足够满足我的需求，但有什么办法可以让它更快 ？ 我的代码必须非常频繁地调用这个函数，有时n和k值相当大，所以越快越好。
编辑
在用le_m和Mike的解决scheme运行了几个testing之后，结果表明虽然两者都比我提出的迭代方法快得多，但是使用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
在我的testing中，对数查找方法比迭代方法快26-28倍，使用帕斯卡三angular的方法比对数查找法快1.3到1.8倍。
请注意，我遵循le_m的build议，使用mathjs以更高的精度预先计算对数，然后将它们转换回常规的JavaScript Number （总是双精度64位浮点数 ）。
从来没有计算因子，他们增长得太快。 反而计算你想要的结果。 在这种情况下，您需要二项数字，它具有令人难以置信的简单几何结构：您可以根据需要构build帕斯卡三angular形 ，并使用普通算术进行。
从[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]结束，依此类推。 正如你所看到的，没有阶乘，对数，甚至是乘法：只需要用干净的整数进行超快速加法。 这么简单，你可以手动build立一个庞大的查询表。
你应该。
不要用代码来计算你可以手工计算的东西，而只是硬编码，在这种情况下，把表格写出来n = 20是绝对微不足道的，然后你就可以用它作为你的“起始LUT”，甚至不需要那些高排。
但是，如果你确实需要它们，或者更多，那么因为你不能build立一个无限的查找表，所以你会妥协：你从一个预先指定的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,54,70,54,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表示O（n2）），那么对于先前计算的值，O（常数），（n *（n + 1））/大O符号几乎从来都不是正确的复杂性度量），而在我们需要的术语之间的某个位置，还不在LUT中。 为你的应用程序运行一些基准testing，它会告诉你初始的lut应该有多大，简单的硬编码（严格来说，这些是常量，它们正是 应该被硬编码的那种值），并且保持发生器以防万一。
但是，请记住，您在JavaScript领域，并且受到JavaScript数字types的约束： 整数只能达到2 ^ 53 ，超出整数属性（每个n具有不同的m=n+1例如mn=1 ）不能保证。 但是，这应该不会成为一个问题：一旦我们达到了这个极限，我们正在处理你甚至不应该使用的二项式系数。
给定一个具有空间复杂度O（n）的对数阶乘的线性查找表，以下algorithm的运行时复杂度为O（1 ） 。
由于binomial(1000, 500) Number.MAX_VALUE binomial(1000, 500)已经危险地接近Number.MAX_VALUE binomial(1000, 500)所以将n和k限制在[ Number.MAX_VALUE ]的范围内是Number.MAX_VALUE 。 因此我们需要一个大小为1000的查找表。
在现代的JavaScript引擎中，n个数字的紧凑数组的大小为n * 8个字节。 完整的查找表将需要8千字节的内存。 如果我们将input限制在[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[nk] - logf[k]); } console.log(binomial(5, 3));