У меня есть код с высокой степенью чувствительности на сервере Node.js, который должен учитывать комбинации. Из this SO answer, я использовал эту простую рекурсивную функцию для вычисления п выбрать к:Эффективное вычисление n выбирает k в Node.js
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
Результаты последовательно показали, что итерационный метод действительно около 3 до 4 раз быстрее, чем рекурсивный метод в Node.js (по крайней мере, на моей машине).
Это вероятно достаточно быстро для моих потребностей, но есть ли способ сделать это быстрее? Мой код должен вызывать эту функцию очень часто, иногда с довольно большими значениями n и k, поэтому чем быстрее, тем лучше.
EDIT
После запуска еще несколько тестов с le_m-х и решений Майка, оказывается, что в то время как значительно быстрее, чем итеративный метод я предложил метод Майка с использованием треугольника Паскаля, кажется, немного быстрее, чем журнал 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 раз быстрее, чем итеративный метод в моих тестах, и метод с использованием треугольника Паскаля был около 1,3 до 1,8 раза быстрее, чем логарифмический смотреть вверх метод.
Обратите внимание, что я последовал предложению le_m по предварительно вычисления логарифмов с более высокой точностью, используя mathjs, затем превращают их в регулярные JavaScript Number с (которые всегда double-precision 64 bit floats).
Меморандум может быть самым быстрым выбором, если пространство не является для вас проблемой. – Godfather
Из комментария, на который вы ссылались, и на странице [wikipedia] (https://en.wikipedia.org/wiki/Binomial_coefficient#Factorial_formula): 'if (k> n/2) return select (n, nk) ; '- что поможет, когда и' n' и 'k' большие, но дополнительная ветвь может замедлить общее выполнение. – Bergi
@ Godfather @NanoWizard, и если у вас нет места для моделирования результатов selecti, вы можете получить хороший прирост производительности за счет модификации факториалов. Вы даже можете использовать метод динамического программирования для вычисления факториала 'fact (n) = max_known_fact_value (n) * [i для evey int для max_known_fact_int (n) до n]', что сэкономит значительное время – gbtimmon