tipos - Función factorial rápida en JavaScript
requisitos de javascript (30)
Buscando una implementación realmente rápida de la función factorial en JavaScript. Cualquier sugerencia?
Aquí está mi código
function factorial(num){
var result = num;
for(i=num;i>=2;i--){
result = result * (i-1);
}
return result;
}
Aquí está mi solución:
function fac(n){
return(n<2)?1:fac(n-1)*n;
}
Es la forma más simple (menos caracteres / líneas) que he encontrado, solo una función con una línea de código.
Editar:
Si realmente quiere guardar algunos caracteres, puede ir con una función de flecha (21 bytes) :
f=n=>(n<2)?1:f(n-1)*n
Aquí hay una implementación que calcula factoriales positivos y negativos. Es rápido y simple.
var factorial = function(n) {
return n > 1
? n * factorial(n - 1)
: n < 0
? n * factorial(n + 1)
: 1;
}
Aquí hay una solución:
function factorial(number) {
total = 1
while (number > 0) {
total *= number
number = number - 1
}
return total
}
Aquí hay uno que hice yo mismo, no use números mayores de 170 o menores de 2.
function factorial(x){
if((!(isNaN(Number(x)))) && (Number(x)<=170) && (Number(x)>=2)){
x=Number(x);for(i=x-(1);i>=1;--i){
x*=i;
}
}return x;
}
Aquí hay uno que usa las funciones de JavaScript más nuevas fill , map , map y constructor (y la sintaxis de la flecha fat):
Math.factorial = n => n === 0 ? 1 : Array(n).fill(null).map((e,i)=>i+1).reduce((p,c)=>p*c)
Editar: actualizado para manejar n === 0
Creo que la siguiente es la pieza de código más sostenible y eficiente de los comentarios anteriores. Puede usar esto en su arquitectura js de aplicación global ... y no se preocupe por escribirlo en múltiples espacios de nombres (ya que es una tarea que probablemente no necesita mucho aumento). He incluido 2 nombres de método (según la preferencia) pero ambos se pueden usar ya que son solo referencias.
Math.factorial = Math.fact = function(n) {
if (isNaN(n)||n<0) return undefined;
var f = 1; while (n > 1) {
f *= n--;
} return f;
};
Deberías usar un bucle.
Aquí hay dos versiones comparadas calculando el factorial de 100 por 10.000 veces.
Recursivo
function rFact(num)
{
if (num === 0)
{ return 1; }
else
{ return num * rFact( num - 1 ); }
}
Iterativo
function sFact(num)
{
var rval=1;
for (var i = 2; i <= num; i++)
rval = rval * i;
return rval;
}
En vivo en: http://jsfiddle.net/xMpTv/
Mis resultados muestran:
- Recursivo ~ 150 milisegundos
- Iterativo ~ 5 milisegundos ..
El bucle en caché debe ser el más rápido (al menos cuando se lo llama varias veces)
var factorial = (function() {
var x =[];
return function (num) {
if (x[num] >0) return x[num];
var rval=1;
for (var i = 2; i <= num; i++) {
rval = rval * i;
x[i] = rval;
}
return rval;
}
})();
El código para calcular factorial depende de sus requisitos.
- ¿Le preocupa el desbordamiento?
- ¿Qué rango de entradas tendrá?
- ¿Es más importante para ti minimizar el tamaño o el tiempo?
- ¿Qué vas a hacer con el factorial?
Con respecto a los puntos 1 y 4, a menudo es más útil tener una función para evaluar el registro del factorial directamente en lugar de tener una función para evaluar el factorial en sí mismo.
Aquí hay una publicación de blog que analiza estos problemas. Aquí hay un código de C # para calcular log factorial que sería trivial para portar a JavaScript. Pero puede no ser lo mejor para sus necesidades según sus respuestas a las preguntas anteriores.
Esta es la forma más simple que conozco para hacer una función factorial
function factorial(num) {
var result = 1;
for(var i = 2; i<= num; i++) {
result *= i;
}
return result;
}
Esta es una solución iterativa que usa menos espacio en la pila y guarda los valores previamente calculados de una manera auto-memorable:
Math.factorial = function(n){
if(this.factorials[n]){ // memoized
return this.factorials[n];
}
var total=1;
for(var i=n; i>0; i--){
total*=i;
}
this.factorials[n] = total; // save
return total;
};
Math.factorials={}; // store
También tenga en cuenta que estoy agregando esto al objeto Math que es un objeto literal por lo que no hay prototipo. En lugar de simplemente vincular estos a la función directamente.
Esta es una versión compacta basada en bucles
function factorial( _n )
{
var _p = 1 ;
while( _n > 0 ) { _p *= _n-- ; }
return _p ;
}
O puede anular el objeto matemático (versión recursiva):
Math.factorial = function( _x ) { return _x <= 1 ? 1 : _x * Math.factorial( --_x ) ; }
O une ambos enfoques ...
Esto devolverá el factorial de n
function f(n) {
var e = n;
if (e == 1 | e == 0) return 1;
while (n--) {
if (n < 1)
break;
e *= n;
}
return e
}
La tabla de búsqueda es la forma más fácil de hacerlo, si está trabajando con números naturales. Para calcular cualquier factorial en tiempo real, puede acelerarlo con un caché, guardando los números que ha calculado antes. Algo como:
factorial = (function() {
var cache = {},
fn = function(n) {
if (n === 0) {
return 1;
} else if (cache[n]) {
return cache[n];
}
return cache[n] = n * fn(n -1);
};
return fn;
})();
Puede precalcular algunos valores para acelerar aún más.
Me encontré con esta publicación. Inspirado por todas las contribuciones aquí, se me ocurrió mi propia versión, que tiene dos características que no he visto antes: 1) Una verificación para asegurar que el argumento sea un entero no negativo 2) Hacer que una unidad salga de la memoria caché y la función de hacerlo un bit de código autocontenido. Para divertirme, traté de hacerlo lo más compacto posible. Algunos pueden encontrarlo elegante, otros pueden pensar que es terriblemente oscuro. De todos modos, aquí está:
var fact;
(fact = function(n){
if ((n = parseInt(n)) < 0 || isNaN(n)) throw "Must be non-negative number";
var cache = fact.cache, i = cache.length - 1;
while (i < n) cache.push(cache[i++] * i);
return cache[n];
}).cache = [1];
Puede precompletar el caché o permitir que se llene a medida que pasan las llamadas. Pero el elemento inicial (de hecho (0) debe estar presente o se romperá.
Disfruta :)
Mira, el memorando, que toma cualquier función de argumento único y la memoriza. Resulta ser marginalmente más rápido que la solution de @ xPheRe, incluido el límite en el tamaño de la memoria caché y la comprobación asociada, porque uso el cortocircuito y así sucesivamente.
function memoize(func, max) {
max = max || 5000;
return (function() {
var cache = {};
var remaining = max;
function fn(n) {
return (cache[n] || (remaining-- >0 ? (cache[n]=func(n)) : func(n)));
}
return fn;
}());
}
function fact(n) {
return n<2 ? 1: n*fact(n-1);
}
// construct memoized version
var memfact = memoize(fact,170);
// xPheRe''s solution
var factorial = (function() {
var cache = {},
fn = function(n) {
if (n === 0) {
return 1;
} else if (cache[n]) {
return cache[n];
}
return cache[n] = n * fn(n -1);
};
return fn;
}());
Aproximadamente 25 veces más rápido en mi máquina en Chrome que en la versión recursiva, y 10% más rápido que en xPheRe.
Probablemente sea muy simple al principio y quizás a partir de este código corto lo configure mejor dependiendo de sus necesidades:
<body>
<button onclick="fact()">Open the Prompt</button>
<h2 id="output"></h2>
<script>
function fact(){
var enter=prompt("Enter You Factorial Number Bellow :","");
var Num_enter=Number(enter);
for (var i=1,FactNumber=1;i<=Num_enter;i++){
FactNumber=FactNumber*i;
}
if(Num_enter){
document.getElementById("output").textContent="the factorial of "+ Num_enter + " is: "+Num_enter+"!= "+ FactNumber;
}
}
</script>
</body>
Puedes buscar (1 ... 100)! en WolframAlpha para precalcular la secuencia factorial.
Los primeros 100 números son:
1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 51090942171709440000, 1124000727777607680000, 25852016738884976640000, 620448401733239439360000, 15511210043330985984000000, 403291461126605635584000000, 10888869450418352160768000000, 304888344611713860501504000000, 8841761993739701954543616000000, 265252859812191058636308480000000, 8222838654177922817725562880000000, 263130836933693530167218012160000000, 8683317618811886495518194401280000000, 295232799039604140847618609643520000000, 10333147966386144929666651337523200000000, 371993326789901217467999448150835200000000, 13763753091226345046315979581580902400000000, 523022617466601111760007224100074291200000000, 20397882081197443358640281739902897356800000000, 815915283247897734345611269596115894272000000000, 33452526613163807108170062053440751665152000000000, 1405006117752879898543142606244511569936384000000000, 60415263063373835637355132068513997507264512000000000, 2658271574788448768043625811014615890319638528000000000, 119622220865480194561963161495657715064383733760000000000, 5502622159812088949850305428800254892961651752960000000000, 258623241511168180642964355153611979969197632389120000000000, 12413915592536072670862289047373375038521486354677760000000000, 608281864034267560872252163321295376887552831379210240000000000, 30414093201713378043612608166064768844377641568960512000000000000, 1551118753287382280224243016469303211063259720016986112000000000000, 80658175170943878571660636856403766975289505440883277824000000000000, 4274883284060025564298013753389399649690343788366813724672000000000000, 230843697339241380472092742683027581083278564571807941132288000000000000, 12696403353658275925965100847566516959580321051449436762275840000000000000, 710998587804863451854045647463724949736497978881168458687447040000000000000, 40526919504877216755680601905432322134980384796226602145184481280000000000000, 2350561331282878571829474910515074683828862318181142924420699914240000000000000, 138683118545689835737939019720389406345902876772687432540821294940160000000000000, 8320987112741390144276341183223364380754172606361245952449277696409600000000000000, 507580213877224798800856812176625227226004528988036003099405939480985600000000000000, 31469973260387937525653122354950764088012280797258232192163168247821107200000000000000, 1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000, 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000, 8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000, 544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000, 36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000, 2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000, 171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000, 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000, 850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000, 61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000, 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000, 330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000, 24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000, 1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000, 145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000, 11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000, 894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000, 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000, 5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000, 475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000, 39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000, 3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000, 281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000, 24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000, 2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000, 185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000, 16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000, 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000, 135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000, 12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000, 1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000, 108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000, 10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000, 991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000, 96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000, 9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000, 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000, 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Si aún desea calcular los valores usted mismo, puede usar la memoization :
var f = [];
function factorial (n) {
if (n == 0 || n == 1)
return 1;
if (f[n] > 0)
return f[n];
return f[n] = factorial(n-1) * n;
}
Editar: 21.08.2014
Solución 2
Pensé que sería útil agregar un ejemplo funcional de la función factorial iterativa perezosa que utiliza números grandes para obtener resultados exactos con memoria y caché como comparación
var f = [new BigNumber("1"), new BigNumber("1")];
var i = 2;
function factorial(n)
{
if (typeof f[n] != ''undefined'')
return f[n];
var result = f[i-1];
for (; i <= n; i++)
f[i] = result = result.multiply(i.toString());
return result;
}
var cache = 100;
//due to memoization following line will cache first 100 elements
factorial(cache);
Supongo que usarías algún tipo de cierre para limitar la visibilidad del nombre de la variable.
Puedes usar
function factorial(n) {
return [...Array(n+1).keys()].slice(1).reduce( (a,b) => a * b, 1 );
}
Sigo pensando que la respuesta de Margus es la mejor. Sin embargo, si desea calcular los factoriales de los números dentro del rango 0 a 1 (es decir, la función gamma) también, entonces no puede usar ese enfoque porque la tabla de búsqueda deberá contener valores infinitos.
Sin embargo, puede aproximar los valores de los factoriales, y es bastante rápido, más rápido que recursivamente llamarse a sí mismo o al bucle al menos (especialmente cuando los valores comienzan a ser más grandes).
Un buen método de aproximación es el de Lanczos
Aquí hay una implementación en JavaScript (portada desde una calculadora que escribí hace meses):
function factorial(op) {
// Lanczos Approximation of the Gamma Function
// As described in Numerical Recipes in C (2nd ed. Cambridge University Press, 1992)
var z = op + 1;
var p = [1.000000000190015, 76.18009172947146, -86.50532032941677, 24.01409824083091, -1.231739572450155, 1.208650973866179E-3, -5.395239384953E-6];
var d1 = Math.sqrt(2 * Math.PI) / z;
var d2 = p[0];
for (var i = 1; i <= 6; ++i)
d2 += p[i] / (z + i);
var d3 = Math.pow((z + 5.5), (z + 0.5));
var d4 = Math.exp(-(z + 5.5));
d = d1 * d2 * d3 * d4;
return d;
}
Ahora puede hacer cosas interesantes como factorial(0.41) , etc. Sin embargo, la precisión puede ser un poco escasa, después de todo, es una aproximación del resultado.
Solo para completar, aquí hay una versión recursiva que permitiría la optimización de la cola de cola. No estoy seguro de si las optimizaciones de cola se realizan en JavaScript, aunque ..
function rFact(n, acc)
{
if (n == 0 || n == 1) return acc;
else return rFact(n-1, acc*n);
}
Para llamarlo:
rFact(x, 1);
Solo una línea con ES6
const factorial =(n) =>!(n > 1) ? 1 : factorial(n - 1) * n;
const factorial =(n) =>!(n > 1) ? 1 : factorial(n - 1) * n;
function print(value) {
document.querySelector(''.result'').innerHTML = value;
}
.result {
margin-left: 10px;
}
<input onkeyup="print(factorial(this.value))" type="number"/>
<span class="result">......</span>
Usando las características de ES6, puede escribir código en UNA línea y sin recurrencia :
var factorial=(n)=>Array.from({length:n},(v,k)=>k+1).reduce((a,b)=>a*b,1)
función recursiva corta y fácil (también podría hacerlo con un bucle, pero no creo que eso suponga ninguna diferencia en el rendimiento):
function factorial (n){
if (n==0 || n==1){
return 1;
}
return factorial(n-1)*n;
}
para una n muy grande, podrías usar la aproximación de Stirlings , pero eso solo te dará un valor aproximado.
EDITAR: un comentario sobre por qué estoy recibiendo un voto negativo por esto hubiera sido agradable ...
EDIT2: esta sería la tarea de usar un loop (que sería la mejor opción):
function factorial (n){
j = 1;
for(i=1;i<=n;i++){
j = j*i;
}
return j;
}
Creo que la mejor solución sería usar los valores en caché, como mencionó Margus y usar la aproximación de Stirlings para valores más grandes (se supone que tienes que ser realmente rápido y no tienes que ser tan exacto en números tan grandes).
function factorial(num){
var num=Number(num);
if (num < 0){
return "this is not a positive number";
}
else{
for (i=2 , f=1 ; i<=num;i++){
f=f*i;
}
return f;
}
}
// the function assumes that a number < 0 is null and factorial of any word is considerate as factorial of 0 //
console.log("-5! ="+factorial(-1));
console.log("something ="+factorial("something"));
console.log("15! ="+factorial(15));
console.log("20! ="+factorial(20));
// if you don''t want to update the Math object, use `var factorial = ...`
Math.factorial = (function() {
var f = function(n) {
if (n < 1) {return 1;} // no real error checking, could add type-check
return (f[n] > 0) ? f[n] : f[n] = n * f(n -1);
}
for (i = 0; i < 101; i++) {f(i);} // precalculate some values
return f;
}());
factorial(6); // 720, initially cached
factorial[6]; // 720, same thing, slightly faster access,
// but fails above current cache limit of 100
factorial(100); // 9.33262154439441e+157, called, but pulled from cache
factorial(142); // 2.6953641378881614e+245, called
factorial[141]; // 1.89814375907617e+243, now cached
Esto hace el almacenamiento en caché de los primeros 100 valores sobre la marcha, y no introduce una variable externa en el alcance de la memoria caché, almacenando los valores como propiedades del objeto de función en sí, lo que significa que si sabes factorial(n) ya ha sido calculado, simplemente puede referirse a él como factorial[n] , que es ligeramente más eficiente. La ejecución de estos primeros 100 valores llevará menos de milisegundos en los navegadores modernos.
function computeFactorialOfN(n) {
var output=1;
for(i=1; i<=n; i++){
output*=i;
} return output;
}
computeFactorialOfN(5);
function isNumeric(n) {
return !isNaN(parseFloat(n)) && isFinite(n)
}
Proporcionado por http://javascript.info/tutorial/number-math como una manera simple de evaluar si un objeto es un entero adecuado para el cálculo.
var factorials=[[1,2,6],3];
Un simple conjunto de factoriales con memoria que requieren cálculos redundantes, puede procesarse con "multiplicar por 1", o son un dígito que es una ecuación simple que no vale la pena procesar en vivo.
var factorial = (function(memo,n) {
this.memomize = (function(n) {
var ni=n-1;
if(factorials[1]<n) {
factorials[0][ni]=0;
for(var factorial_index=factorials[1]-1;factorials[1]<n;factorial_index++) {
factorials[0][factorials[1]]=factorials[0][factorial_index]*(factorials[1]+1);
factorials[1]++;
}
}
});
this.factorialize = (function(n) {
return (n<3)?n:(factorialize(n-1)*n);
});
if(isNumeric(n)) {
if(memo===true) {
this.memomize(n);
return factorials[0][n-1];
}
return this.factorialize(n);
}
return factorials;
});
Después de revisar las aportaciones de otros miembros (excluyendo el consejo de registro, aunque puedo implementarlo más adelante), seguí y redacté un guión que es bastante simple. Empecé con un simple ejemplo de OOP de JavaScript sin educación y construí una pequeña clase para manejar factoriales. Luego implementé mi versión de Memoization que se sugirió anteriormente. También implementé la factorización de taquigrafía, sin embargo hice un pequeño ajuste de error; Cambié el "n <2" a "n <3". "n <2" aún procesaría n = 2, lo que sería un desperdicio, porque iteraría para un 2 * 1 = 2; esto es un desperdicio en mi opinión. Lo cambié a "n <3"; porque si n es 1 o 2, simplemente devolverá n, si es 3 o más, se evaluará normalmente. Por supuesto, a medida que se aplican las reglas, coloqué mis funciones en orden descendente de ejecución supuesta. Agregué en la opción bool (true | false) para permitir una rápida alteración entre la ejecución memorable y normal (Nunca se sabe cuándo se quiere cambiar en su página sin necesidad de cambiar el "estilo") Como dije antes La variable de factores modificados se establece con las 3 posiciones de inicio, tomando 4 caracteres y minimizando los cálculos derrochadores. Todo, más allá de la tercera iteración, está manejando las matemáticas de doble dígito más. Me imagino que si usted es lo suficientemente estricto como para hacerlo, se ejecutaría en una tabla factorial (como se implementó).
¿Qué he planeado después de esto? almacenamiento local y | sesión para permitir un caché caso por caso de las iteraciones necesarias, esencialmente manejando el problema de "tabla" mencionado anteriormente. Esto también ahorraría masivamente espacio en la base de datos y el servidor. Sin embargo, si vas con localStorage, básicamente estarás absorbiendo espacio en la computadora de los usuarios simplemente para almacenar una lista de números y hacer que su pantalla MIRAR más rápido, sin embargo, durante un largo período de tiempo con una gran necesidad, esto sería lento. Estoy pensando en que sessionStorage (borrar después de que Tab se vaya) sería una ruta mucho mejor. ¿Posiblemente combinar esto con un servidor de equilibrio automático / caché local dependiente? El usuario A necesita X iteraciones. El usuario B necesita iteraciones Y X + Y / 2 = Cantidad necesaria localmente en caché. A continuación, solo detecte y juegue con las pruebas de tiempo de tiempo de carga y tiempo de ejecución en vivo para cada usuario hasta que se ajuste a la optimización para el sitio en sí. ¡Gracias!
Editar 3:
var f=[1,2,6];
var fc=3;
var factorial = (function(memo) {
this.memomize = (function(n) {
var ni=n-1;
if(fc<n) {
for(var fi=fc-1;fc<n;fi++) {
f[fc]=f[fi]*(fc+1);
fc++;
}
}
return f[ni];
});
this.factorialize = (function(n) {
return (n<3)?n:(factorialize(n-1)*n);
});
this.fractal = (function (functio) {
return function(n) {
if(isNumeric(n)) {
return functio(n);
}
return NaN;
}
});
if(memo===true) {
return this.fractal(memomize);
}
return this.fractal(factorialize);
});
Esta edición implementa otra sugerencia de pila y me permite llamar a la función como factorial (verdadera) (5), que fue uno de mis objetivos establecidos. : 3 También eliminé algunas asignaciones innecesarias, y eliminé algunos nombres de variables no públicas.