javascript — Эффективное вычисление n выберите k в Node.js

Эффективное вычисление n выберите k в Node.js

Никогда не вычисляйте факториалы, они растут слишком быстро. Вместо этого вычислите результат, который вы хотите. В этом случае вам нужны биномиальные числа, которые имеют невероятно простую геометрическую конструкцию: вы можете построить треугольник Паскаля так , как вам нужно, и сделать это с помощью простой арифметики.

Начните с [1] и [1,1]. Следующая строка имеет [1] в начале, [1 1] в середине и [1] в конце: [1,2,1]. Следующая строка: [1] в начале, сумма первых двух слагаемых в пятне 2, сумма следующих двух слагаемых в пятой точке и [1] в конце: [1,3,3,1]. Следующая строка: [1], затем 1 3 = 4, затем 3 3 = 6, затем 3 1 = 4, затем [1] в конце, и так далее, и так далее. Как видите, нет факториалов, логарифмов и даже умножений: просто супер быстрое сложение с чистыми целыми числами. Так просто, вы можете построить массивную таблицу поиска вручную.

И ты должен.

Никогда не вычисляйте в коде то, что вы можете вычислить вручную, а просто включайте в качестве констант для немедленного поиска; в этом случае выписать таблицу, где число элементов примерно равно n = 20, абсолютно тривиально, и тогда вы можете просто использовать это как свою «начальную LUT» и, возможно, даже никогда не получить доступ к старшим строкам.

Но, если они вам нужны, или даже больше, то, потому что вы не можете создать бесконечную таблицу поиска, вы идете на компромисс: вы начинаете с заранее заданного 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,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 {amp}gt;= binomials.length) { let s = binomials.length; let nextRow = []; nextRow[0] = 1; for(let i=1, prev=s-1; i{amp}lt;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-битные числа, мы можем получить до n = 35 всего за 2380 байтов.

Таким образом, поиск выполняется быстро: либо O (постоянная) для ранее вычисленных значений, (n * (n 1)) / 2 шага, если у нас вообще нет LUT (в больших обозначениях O, это будет O (n²), но нотация Big O почти никогда не является правильной мерой сложности), и где-то посередине для нужных нам терминов, которых еще нет в LUT. Запустите некоторые тесты для вашего приложения, которые скажут вам, насколько большим должен быть ваш первоначальный LUT, просто жестким кодом, который (серьезно. Это константы, это именно те значения, которые должны быть жестко запрограммированы), и сохраните генератор вокруг на всякий случай.

Однако помните, что вы находитесь на земле JavaScript, и вы ограничены числовым типом JavaScript: целые числа доходят только до 2 ^ 53 , за исключением того , что свойство integer (у каждого n есть отличное m=n 1 такое, что mn=1 ) не гарантируется. Это вряд ли когда-либо будет проблемой: как только мы достигнем этого предела, мы имеем дело с биномиальными коэффициентами, которые вы никогда не должны использовать.

Понравилась статья? Поделиться с друзьями:
JavaScript & TypeScript
Adblock
detector