Effiziente Berechnung von n Wählen Sie k in Node.js

Question

Ich habe einige leistungsabhängige Code auf einem Node.js-Server, der Kombinationen zählen muss. Von this SO answer ich diese einfache rekursive Funktion für die Berechnung verwendete n wählen k:

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

Dann, da wir alle Iteration wissen fast immer schneller als Rekursion ist, schrieb ich diese Funktion auf der Grundlage der multiplicative formula:

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

Ich lief ein paar benchmarks auf meiner Maschine. Hier sind die Ergebnisse von nur einem von ihnen:

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 

Die Ergebnisse konsequent zeigten, dass die iterativen Verfahren sind in der Tat etwa 3 bis 4 mal schneller als die rekursive Methode in Node.js (zumindest auf meinem Rechner).

Dies ist wahrscheinlich schnell genug für meine Bedürfnisse, aber ist es eine Möglichkeit, es schneller zu machen? Mein Code muss diese Funktion sehr häufig aufrufen, manchmal mit ziemlich großen Werten von n und k, je schneller desto besser.

EDIT

Nach ein paar Tests mit le_m ist und Mikes Lösungen laufen, stellt sich heraus, dass zwar beide deutlich schneller als das iterative Verfahren I vorgeschlagen, Mike Methode Pascals Dreieck mit scheint schneller zu sein leicht als le_m Logbuch Tabellenmethode. um 26-28 mal schneller als die iterativen Verfahren in meinen Tests

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 

Die logarithmische aufblick Methode wurde und das Verfahren Pascals Dreieck mit war etwa 1,3 bis 1,8-mal schneller als die logarithmische Methode nachschlagen.

Bitte beachte, dass ich le_m Vorschlag der Pre-Berechnung der Logarithmen mit höherer Genauigkeit gefolgt mathjs verwenden, konvertiert sie dann wieder zu den regulären JavaScript Number s (was immer double-precision 64 bit floats sind).

Answer 1

Berechne niemals Faktoren, sie wachsen zu schnell. Berechnen Sie stattdessen das gewünschte Ergebnis. In diesem Fall möchten Sie die binomischen Zahlen, die eine unglaublich einfache geometrische Konstruktion haben: Sie können pascal's triangle, wie Sie es brauchen, und verwenden Sie einfache Arithmetik.

Beginnen Sie mit [1] und [1,1]. Die nächste Zeile hat [1] am Anfang, [1 + 1] in der Mitte und [1] am Ende: [1,2,1]. Nächste Reihe: [1] am Anfang, die Summe der ersten beiden Terme in Platz 2, die Summe der nächsten beiden Terme in Platz drei und [1] am Ende: [1,3,3,1]. Nächste Reihe: [1], dann 1 + 3 = 4, dann 3 + 3 = 6, dann 3 + 1 = 4, dann [1] am Ende und so weiter und so weiter. Wie Sie sehen können, keine faktoriellen, logarithmischen oder sogar Multiplikationen: nur super schnelle Addition mit sauberen ganzen Zahlen. So einfach, Sie können eine massive Nachschlagetabelle von Hand erstellen.

Und Sie sollten.

Niemals in Code berechnen, was Sie mit der Hand berechnen können und nur Hardcode, in diesem Fall ist das Schreiben der Tabelle für bis zu sagen n = 20 absolut trivial, und Sie können dann einfach als "Start LUT" und Wahrscheinlich brauchen Sie nie diese hohen Reihen.

Aber wenn Sie sie brauchen, oder mehr, dann können Sie keine unendliche Nachschlagetabelle erstellen, die Sie kompromittieren: Sie beginnen mit einer vordefinierten LUT und einer Funktion, die Sie für einen Begriff "auffüllen" kann brauche das noch nicht drin ist:

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

Da dies ein Array von Ints ist, ist der Speicherbedarf winzig. Für eine Menge Arbeit mit Binomen benötigen wir realistischerweise nicht einmal mehr als zwei Bytes pro Integer, was eine Minute Nachschlagetabelle ergibt: Wir brauchen nicht mehr als 2 Bytes, bis Sie Binomialwerte höher als n = 19 benötigen. und die vollständige Nachschlagetabelle bis zu n = 19 benötigt nur magere 380 Bytes. Dies ist nichts im Vergleich zum Rest Ihres Programms. Selbst wenn wir 32 Bit-Ints zulassen, können wir bis zu n = 35 in nur 2380 Bytes erreichen.

So ist die Suche schnell: entweder O (konstant) für vorher berechnete Werte, (n * (n + 1))/2 Schritte, wenn wir überhaupt keine LUT haben (in großer O-Notation wäre das O (n²), aber die große O-Notation ist fast nie das richtige Komplexitätsmaß, und irgendwo dazwischen brauchen wir Begriffe, die wir noch nicht in der LUT haben. Führen Sie einige Benchmarks für Ihre Anwendung, die Ihnen sagen wird, wie groß Ihre anfängliche lut sein sollte, einfach hart Code, (ernsthaft. Das sind Konstanten, sie sind genau die Art von Werten, die sollte hart codiert werden), und halten Sie den Generator für alle Fälle bereit.

aber denken Sie daran, dass Sie in JavaScript Land sind, und Sie werden durch die JavaScript numerischen Typ eingeschränkt: integers only go up to 2^53, darüber hinaus, dass die Integer-Eigenschaft (jede n eine deutliche m=n+1 so dass m-n=1 hat) ist nicht garantiert. Dies sollte jedoch kaum ein Problem darstellen: Sobald wir dieses Limit erreicht haben, haben wir es mit Binomialkoeffizienten zu tun, die Sie niemals verwenden sollten.

Answer 2

Der folgende Algorithmus hat eine Laufzeitkomplexität von O (1) gegeben eine lineare Nachschlagetabelle von logarithmisch-factorials mit Raum-Komplexität O (n).

Begrenzung n und k auf den Bereich [0, 1000] macht Sinn, da binomial(1000, 500) bereits Number.MAX_VALUE gefährlich nahe ist. Wir benötigen daher eine Nachschlagetabelle der Größe 1000.

Auf einer modernen JavaScript-Engine hat eine kompakte Anordnung von n Zahlen eine Größe von n * 8 Bytes. Eine vollständige Nachschlagetabelle würde somit 8 Kilobyte Speicher benötigen. Wenn wir unsere Eingabe auf den Bereich [0, 100] beschränken, würde die Tabelle nur 800 Bytes belegen.

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

Erklärung

mit dem ursprünglichen iterativen Algorithmus starten wir zuerst das Produkt mit einer Summe von Logarithmen ersetzen:

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

Unsere Schleife jetzt fasst über k Begriffe. Wenn wir die Summe neu anordnen, können wir leicht sehen, dass wir über aufeinanderfolgende Logarithmen log(1) + log(2) + ... + log(k) usw. summieren, die wir durch eine sum_of_logs(k) ersetzen können, die tatsächlich mit log(n!) identisch ist. Vorberechnen dieser Werte und Speichern dieser Werte in unserer Nachschlagetabelle logf führt dann zu dem obigen Einliner-Algorithmus.

Berechnen der Verweistabelle:

I empfehlen Vorberechnen die Lookup-Tabelle mit einer höheren Genauigkeit und die erhaltenen Elemente zu 64 Bit schwimmt. Wenn Sie nicht, dass wenig zusätzliche Präzision brauchen oder wollen diesen Code auf der Client-Seite ausgeführt werden, verwenden Sie diese:

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

Numerische Präzision:

durch log-factorials verwenden, vermeiden wir Präzision Probleme bei der Lagerung von Rohfaktorien.

Wir konnten sogar Stirling's approximation für log(n!) statt einer Lookup-Tabelle verwenden und immer noch 12 signifikante Zahlen für obige Berechnung in beide Laufzeit und Speicherkomplexität 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