He estado jugando con Haskell y lo encuentro fascinante, especialmente la característica de evaluación perezosa que nos permite trabajar con listas (potencialmente) infinitas.
De aquí deriva la hermosa implementación de la Criba de Eratóstenes para obtener una lista infinita de números primos:
primes = sieve [2..] where sieve (x:xs) = x : sieve [i | i <- xs, i `mod` x /= 0]Todavía usando haskell puedo tener:
takeWhile (<1000) primeslo que me da los números primos hasta 1000 (n), o
take 1000 primeslo que me da los primeros 1000 números primos
Traté de implementar esto en Javascript, olvidando la posibilidad 'infinita' y esto es lo que se me ocurrió:
const sieve = list => { if (list.length === 0) return [] const first = list.shift() const filtered = list.filter(x => x % first !== 0) return [first, ...sieve(filtered)] } const getPrimes = n => { const list = new Array(n - 1).fill(null).map((x, i) => i + 2) return sieve(list) }Funciona perfectamente (si no alcanzo el tamaño máximo de la pila de llamadas), pero solo puedo obtener los números primos "hasta" n.
¿Cómo podría usar esto para implementar una función que en su lugar devolvería "los primeros n" números primos?
He intentado muchos enfoques y no pude hacerlo funcionar
Prima
¿Hay alguna forma en que pueda usar la optimización de llamadas de cola o algo más para evitar StackOverflows para Ns grandes?
Como sugirió @VLAZ, podemos hacer esto usando generadores:
function* removeMultiplesOf(x, iterator) { for (const i of iterator) if (i % x != 0) yield i; } function* eratosthenes(iterator) { const x = iterator.next().value; yield x; yield* eratosthenes(removeMultiplesOf(x, iterator)); } function* from(i) { while (true) yield i++; } function* take(n, iterator) { if (n <= 0) return; for (const x of iterator) { yield x; if (--n == 0) break; } } const primes = eratosthenes(from(2)); console.log(Array.from(take(1000, primes)));Por cierto, pensé que uno podría optimizar esto al no hacer la división repetidamente:
function* removeMultiplesOf(x, iterator) { let n = x; for (const i of iterator) { while (n < i) n += x; if (n != i) yield i; } }pero un punto de referencia rápido mostró que en realidad es tan rápido como la función simple.
Muy bien, después de trabajar todo el fin de semana en esto, creo que encontré mi mejor implementación.
Mi solución utiliza el almacenamiento en caché adecuado (usando el poder de los cierres) de los resultados anteriores, por lo que el rendimiento sigue mejorando cuanto más lo usa.
Para obtener los primeros N números primos, itero a través de getPrimesTill hasta que alcance una longitud suficiente... aquí hay un compromiso, que encontrará más números primos de los previstos la primera vez, pero no creo que pueda ser de otra manera. . Tal vez getPrimesTill(n + ++count * n * 5) se pueda optimizar aún más, pero creo que esto es más que suficiente.
Para poder manejar números muy grandes y evitar los desbordamientos de pila, implementé el algoritmo tamiz usando un bucle for, en lugar de la recursividad.
Aquí está el código:
function Primes() { let thePrimes = [] const shortCircuitPrimes = until => { const primesUntil = [] for (let i = 0; ; i++) { if (thePrimes[i] > until) { return primesUntil } primesUntil.push(thePrimes[i]) } } const sieveLoop = n => { const list = buildListFromLastPrime(n) const result = [] let copy = [...thePrimes, ...list] for (let i = 0; i < result.length; i++) { copy = copy.filter(x => x % result[i] !== 0) } for (let i = 0; ; i++) { const first = copy.shift() if (!first) return result result.push(first) copy = copy.filter(x => x % first !== 0) } } const buildListFromLastPrime = n => { const tpl = thePrimes.length const lastPrime = thePrimes[tpl - 1] const len = n - (lastPrime ? tpl + 1 : 1) return new Array(len).fill(null).map((x, i) => i + 2 + tpl) } const getPrimesTill = n => { const tpl = thePrimes.length const lastPrime = thePrimes[tpl - 1] if (lastPrime > n) { return shortCircuitPrimes(n) } const primes = sieveLoop(n) if (primes.length - thePrimes.length) { thePrimes = primes } return primes } const getFirstPrimes = n => { let count = 0 do { if (thePrimes.length >= n) { return thePrimes.slice(0, n) } getPrimesTill(n + ++count * n * 5) } while (true) } return { getPrimesTill, getFirstPrimes, thePrimes } } const { getPrimesTill, getFirstPrimes, thePrimes } = Primes()Creé un repositorio para él, con pruebas exhaustivas, cualquiera quiere probarlo.
https://github.com/andrepadez/prime-numbers-sieve-eratosthenes-javascript
Todo el conjunto de pruebas tarda unos 85 segundos en ejecutarse, ya que estoy probando con muchas combinaciones posibles y números muy grandes.
Además, todos los resultados esperados se obtuvieron de la implementación de Haskell, para no contaminar las pruebas.
Además, encontré este increíble video, donde el tipo implementa Lazy Evaluation y Infinite Lists usando TypeScript... Al final, construye el algoritmo Sieve en Javascript, que funciona exactamente como se esperaba en Haskell.