Estoy haciendo un programa para calcular todos los números primos hasta un número específico. He estado usando un temporizador para optimizar la función y puedo calcular primos hasta 20 millones en menos de 4 segundos. El problema es que una de las optimizaciones en realidad hizo que el programa fuera más lento, aunque hace menos cosas.
Función antigua (la más rápida):
function getPrimesOld(max) { const arr = [1]; function isPrime(i) { const s = Math.sqrt(i); for (const h of arr) { if (h === 1) continue; if (h > s) break; if (!(i % h)) return false; } return true; } for (let i = 2 ; i < max ; i += 2) { if (isPrime(i)) arr.push(i); if (i === 2) i--; } return arr; }Nueva función:
function getPrimes(max) { const arr = [2]; function isPrime(i) { const s = Math.sqrt(i); for (const h of arr) { if (h > s) break; if (!(i % h)) return false; } return true; } for (let i = 3 ; i < max ; i += 2) { if (isPrime(i)) arr.push(i); } return arr; }Ejecuté ambas funciones 10 veces y promedié el tiempo que les tomó, aquí están los resultados:
New function: 3544ms,3188ms,3513ms,3510ms,3511ms,3512ms,3503ms,3515ms,3513ms,3509ms (avg: 3481.8ms) Old function: 3368ms,3388ms,3363ms,3355ms,3359ms,3350ms,3354ms,3354ms,3353ms,3356ms (avg: 3360ms)(Para que quede claro, ejecutar la función antigua 10 veces primero en lugar de la nueva no afecta los resultados. La función antigua siempre promedia alrededor de 3,35 s y la nueva siempre promedia alrededor de 3,5 s)
¿Por qué la función anterior es más rápida que la nueva?
Me obsesioné un poco con esto, lo admito, pero no veo la degradación del rendimiento de la que hablas. Si bien la diferencia es extremadamente pequeña, su nuevo enfoque parece ser ligeramente más rápido (ejecutando la versión 94.0.4606.81 de Chrome (compilación oficial) (x86_64) en macOS Big Sur 11.6 (20G165) ).
Un resultado de muestra de la prueba a continuación:
Old Results: - Mean: 3744 ms - Median: 3735 ms New Results: - Mean: 3350 ms - Median: 3276 msMe gustaría ver lo que descubren otros lectores:
const debugElem = document.getElementById("debug"); debugElem.innerText = "Press Start to Begin"; function getPrimesOld(max) { const arr = [1]; function isPrime(i) { const s = Math.sqrt(i); for (const h of arr) { if (h === 1) continue; if (h > s) break; if (!(i % h)) return false; } return true; } for (let i = 2 ; i < max ; i += 2) { if (isPrime(i)) arr.push(i); if (i === 2) i--; } return arr; } function getPrimes(max) { const arr = [2]; function isPrime(i) { const s = Math.sqrt(i); for (const h of arr) { if (h > s) break; if (!(i % h)) return false; } return true; } for (let i = 3 ; i < max ; i += 2) { if (isPrime(i)) arr.push(i); } return arr; } async function testPrimes(fn) { await logMsg(`Running test for ${/function \w+/.exec(fn+"")}`); const stats = { times: [], }; async function runTest() { const start = performance.now(); await fn(20000000); const end = performance.now(); return end - start; } for (let i = 10; i--;) { const diff = await runTest(); await logMsg(`${i}... ${Math.round(diff)} ms`); stats.times.push(diff); } stats.times = stats.times.sort(); stats.avg = stats.times.reduce( (acc, d) => acc + d, 0 ) / stats.times.length; stats.mdn = (stats.times[4] + stats.times[5])/2; return stats; } function logMsg(msg) { return new Promise(resolve => { debugElem.innerText += msg + "\n"; // console.log(msg); // Due to JavaScript's single-threading, we need to introduce // a slight delay in order to update the UI. This only happens // AFTER a test has finished, so it won't affect the times // reported by the test setTimeout(resolve, 0); }); } document.getElementById("start").onclick = (async function() { debugElem.innerText = ""; const results = {}; results.old = await testPrimes(getPrimesOld); debugElem.innerText = ""; results.new = await testPrimes(getPrimes); debugElem.innerText = ""; logMsg("Old Results:"); logMsg(`- Mean: ${Math.round(results.old.avg)} ms`); logMsg(`- Median: ${Math.round(results.old.mdn)} ms`); logMsg("New Results:"); logMsg(`- Mean: ${Math.round(results.new.avg)} ms`); logMsg(`- Median: ${Math.round(results.new.mdn)} ms`); }); #debug { font-family: "Lucida Console", monospace, sans-serif; } <button id="start">Start</button> <div id="debug"></div>