¿Cómo mejorar la eficiencia con la programación funcional?

Recientemente he estado revisando la guía Learn You a Haskell for Great Good y, como práctica, quería resolver el problema 5 del Proyecto Euler , que especifica:

¿Cuál es el número positivo más pequeño que es divisible por todos los números del 1 al 20?

Decidí escribir primero una función que determinara si un número dado es divisible por estos números:

divisable x = all (\y -> x `mod` y == 0)[1..20]

Luego calculé el más pequeño usando head:

sm = head [x | x <- [1..], divisable x]

Y finalmente escribió la línea para mostrar el resultado:

main = putStrLn $ show $ sm

Lamentablemente, esto tardó unos 30 segundos en terminar. Hacer lo mismo con los números del 1 al 10 produce un resultado casi de inmediato, pero de nuevo el resultado es mucho más pequeño que la solución del 1 al 20.

Lo resolví antes en C y allí el resultado para 1 a 20 también se calculó casi al instante. Esto me lleva a creer que no entiendo cómo interpretar este problema para Haskell. Miré a través de las soluciones de otras personas y encontré esto:

main = putStrLn $ show $ foldl1 lcm [1..20]

Es justo, esto utiliza una función incorporada, pero ¿por qué el resultado final es mucho más lento cuando lo hace usted mismo? Los tutoriales por ahí le dicen cómo usar Haskell, pero no veo mucha ayuda para transformar algoritmos en código rápido.

Primero debe asegurarse de tener un binario optimizado, antes de pensar que el idioma es el problema. Lea el capítulo Perfiles y optimización en Real Wolrd Haskell. Vale la pena señalar que, en la mayoría de los casos, la naturaleza de alto nivel del idioma le cuesta al menos parte del rendimiento.

Sin embargo, tenga en cuenta que la otra solución no es más rápida porque usa una función incorporada, sino simplemente porque utiliza un algoritmo mucho más rápido : para encontrar el mínimo común múltiplo de un conjunto de números, solo necesita encontrar unos pocos GCD. Compare esto con su solución, que recorre todos los números del 1 al foldl lcm [1..20]. Si prueba con 30, la diferencia entre los tiempos de ejecución será aún mayor.

Eche un vistazo a las complejidades: su algoritmo tiene O(ans*N)tiempo de ejecución, dónde ansestá la respuesta y Nes el número hasta el que está comprobando la divisibilidad (20 en su caso). Sin embargo , el
otro algoritmo ejecuta Ntiempos , y GCD tiene complejidad . Por lo tanto, el segundo algoritmo tiene complejidad . Puedes juzgar por ti mismo cuál es más rápido.lcmlcm(a,b) = a*b/gcd(a,b)O(log(max(a,b)))O(N*log(ans))

Entonces, para resumir:
su problema es su algoritmo, no el idioma.

Tenga en cuenta que hay lenguajes especializados que son funcionales y se centran en programas matemáticos pesados, como Mathematica, que para problemas centrados en matemáticas es probablemente más rápido que casi cualquier otra cosa. Tiene una biblioteca de funciones muy optimizada y admite el paradigma funcional (es cierto que también admite la programación imperativa).

Mi primer pensamiento fue que solo los números divisibles por todos los primos <= 20 serán divisibles por todos los números menores que 20. Por lo tanto, solo necesita considerar números que sean múltiplos de 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 . Dicha solución verifica 1 / 9.699.690 tantos números como el enfoque de fuerza bruta. Pero su solución rápida de Haskell funciona mejor que eso.

Si entiendo la solución "rápida de Haskell", utiliza foldl1 para aplicar la función mcm (mínimo común múltiplo) a la lista de números del 1 al 20. Por lo tanto, aplicaría mcm 1 2, produciendo 2. Luego, mcm 2 3 produciendo 6 Luego mcm 6 4 dando 12, y así sucesivamente. De esta manera, la función mcm solo se llama 19 veces para obtener su respuesta. En la notación Big O, esas son operaciones O (n-1) para llegar a una solución.

Su solución de Haskell lenta pasa por los números del 1 al 20 para cada número del 1 a su solución. Si llamamos a la solución s, entonces la solución de Haskell lenta realiza operaciones O (s * n). Ya sabemos que s supera los 9 millones, lo que probablemente explica la lentitud. Incluso si todos los accesos directos y obtiene un promedio de la mitad de la lista de números 1-20, eso sigue siendo solo O (s * n / 2).

Llamar headno le ahorra hacer estos cálculos, deben hacerse para calcular la primera solución.

Gracias, esta fue una pregunta interesante. Realmente amplió mi conocimiento de Haskell. No podría responderlo si no hubiera estudiado algoritmos el otoño pasado.

Inicialmente no estaba planeando escribir una respuesta. Pero me dijeron que después de que otro usuario hiciera la extraña afirmación de que simplemente multiplicar los primeros primos era más costoso desde el punto de vista computacional que aplicarlo repetidamente lcm. Así que aquí están los dos algoritmos y algunos puntos de referencia:

Mi algoritmo:

Algoritmo de primera generación, dándome una lista infinita de primos.

isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)

toPrime :: Int -> Int
toPrime n 
    | isPrime n = n 
    | otherwise = toPrime (n + 1)

primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes

Ahora usando esa lista principal para calcular el resultado para algunos N:

solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)

Ahora, el otro algoritmo basado en mcm, que ciertamente es bastante conciso, principalmente porque implementé la primera generación desde cero (y no utilicé el algoritmo de comprensión de listas súper concisas debido a su bajo rendimiento), mientras que lcmsimplemente se importó del Prelude.

solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`

Ahora para los puntos de referencia, el código que usé para cada uno era simple: ( -prof -fprof-auto -O2entonces +RTS -p)

main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n

Para n = 100,000, solvePrime:

total time = 0.04 secs
total alloc = 108,327,328 bytes

vs solveLcm:

total time = 0.12 secs
total alloc = 117,842,152 bytes

Para n = 1,000,000, solvePrime:

total time = 1.21 secs
total alloc = 8,846,768,456 bytes

vs solveLcm:

total time = 9.10 secs
total alloc = 8,963,508,416 bytes

Para n = 3,000,000, solvePrime:

total time = 8.99 secs
total alloc = 74,790,070,088 bytes

vs solveLcm:

total time = 86.42 secs
total alloc = 75,145,302,416 bytes

Creo que los resultados hablan por sí mismos.

El generador de perfiles indica que la generación principal ocupa un porcentaje cada vez menor del tiempo de ejecución a medida que naumenta. Por lo tanto, no es el cuello de botella, por lo que podemos ignorarlo por ahora.

Esto significa que realmente estamos comparando llamadas lcmdonde un argumento va de 1 a n, y el otro va geométricamente de 1 a ans. Para llamar *con la misma situación y el beneficio adicional de omitir todos los números no primos (asintóticamente de forma gratuita, debido a la naturaleza más cara de *).

Y es bien sabido que *es más rápido que lcm, ya que lcmrequiere aplicaciones repetidas de mod, y modes asintóticamente más lento ( O(n^2)vs ~O(n^1.5)).

Entonces, los resultados anteriores y el breve análisis del algoritmo deberían hacer muy obvio qué algoritmo es más rápido.