Así que estaba trabajando en una forma de generar primos de forma perezosa, y se me ocurrieron estas tres definiciones, que funcionan todas de manera equivalente, simplemente comprobando si cada nuevo entero tiene un factor entre todos los anteriores primos:Haskell style/efficiency
primes1 :: [Integer]
primes1 = mkPrimes id [2..]
where mkPrimes f (x:xs) =
if f (const True) x
then
let g h y = y `mod` x > 0 && h y in
x : mkPrimes (f . g) xs
else
mkPrimes f xs
primes2 :: [Integer]
primes2 = mkPrimes id (const True) [2..]
where mkPrimes f f_ (x:xs) =
if f_ x
then
let g h y = y `mod` x > 0 && h y in
x : mkPrimes (f . g) (f $ g $ const True) xs
else
mkPrimes f f_ xs
primes3 :: [Integer]
primes3 = mkPrimes [] [2..]
where mkPrimes ps (x:xs) =
if all (\p -> x `mod` p > 0) ps
then
x : mkPrimes (ps ++ [x]) xs
else
mkPrimes ps xs
Así que me parece primes2
deberían ser un poco más rápido que primes1
, ya que evita recomputing f_ = f (const True)
para cada entero (que que requiere un trabajo en el orden del número de números primos que lo he encontrado hasta ahora), y solo lo actualiza cuando enc ounter un nuevo primo.
Sólo a partir de pruebas no científicas (que se ejecuta en take 1000
ghci) parece primes3
corre más rápido que primes2
.
¿Debo tomar una lección de esto, y asumamos que si puedo representar una función como una operación en una matriz, que debería ponerlo en práctica en esta última forma de la eficiencia, o hay algo más en juego aquí ?
(como estoy seguro ya sabes) en 'primes3' aquí llamando' all' es una exageración enorme - tomar únicamente primos no superiores a 'sqrt' de' x' es suficiente - así se puede usar la misma lista de primos que se está construyendo - la función se convierte en filtro simple: 'primes4 = 2: filtro (\ x-> all ((/ = 0). (rem x)) $ takeWhile ((<= x). (^ 2)) primes4) [3,5 ..] ', ejecutando aproximadamente' O (n^1.45) 'empíricamente, en' n' primos producidos - * las tres * versiones en su pregunta se ven cuadráticas - no importa cómo construya sus funciones, todavía prueba con * todos * primos en lugar de solo aquellos debajo de 'sqrt x'. –