opciones - haskell simbolos

Herramientas para analizar el rendimiento de un programa Haskell (4)

Mientras resuelvo algunos problemas del Proyecto Euler para aprender Haskell (por lo que actualmente soy un principiante), me encontré con el problema 13 . Escribí esta solución (ingenua):

--Get Number of Divisors of n numDivs :: Integer -> Integer numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2 --Generate a List of Triangular Values triaList :: [Integer] triaList = [foldr (+) 0 [1..n] | n <- [1..]] --The same recursive triaList2 = go 0 1 where go cs n = (cs+n):go (cs+n) (n+1) --Finds the first triangular Value with more than n Divisors sol :: Integer -> Integer sol n = head $ filter (/x -> numDivs(x)>n) triaList2

Esta solución para n = 500 (sol 500) es extremadamente lenta (funciona durante más de 2 horas), así que me pregunté cómo averiguar por qué esta solución es tan lenta. ¿Hay algún comando que me diga dónde se gasta la mayor parte del tiempo de cálculo para saber qué parte de mi programa haskell es lenta? Algo así como un simple generador de perfiles.

Para dejarlo en claro, no estoy pidiendo una solución más rápida sino una forma de encontrar esta solución. ¿Cómo comenzarías si no tuvieras conocimiento de Haskell?

Traté de escribir dos funciones de triaList pero no encontré ninguna manera de probar cuál es más rápido, así que ahí es donde comienzan mis problemas.

Gracias

cómo saber por qué esta solución es tan lenta. ¿Hay algún comando que me diga dónde se gasta la mayor parte del tiempo de cálculo para saber qué parte de mi programa haskell es lenta?

¡Precisamente! GHC proporciona muchas herramientas excelentes, que incluyen:

Un tutorial sobre el uso de perfiles de tiempo y espacio es parte de Real World Haskell .

Estadísticas de GC

En primer lugar, asegúrese de estar compilando con ghc -O2. Y puedes asegurarte de que sea un GHC moderno (por ejemplo, GHC 6.12.x)

Lo primero que podemos hacer es verificar que la recolección de basura no sea el problema. Ejecute su programa con + RTS -s

$ time ./A +RTS -s ./A +RTS -s 749700 9,961,432,992 bytes allocated in the heap 2,463,072 bytes copied during GC 29,200 bytes maximum residency (1 sample(s)) 187,336 bytes maximum slop **2 MB** total memory in use (0 MB lost due to fragmentation) Generation 0: 19002 collections, 0 parallel, 0.11s, 0.15s elapsed Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 13.15s ( 13.32s elapsed) GC time 0.11s ( 0.15s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 13.26s ( 13.47s elapsed) %GC time **0.8%** (1.1% elapsed) Alloc rate 757,764,753 bytes per MUT second Productivity 99.2% of total user, 97.6% of total elapsed ./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total

Lo cual ya nos da mucha información: solo tienes un montón de 2M y GC ocupa el 0.8% del tiempo. Entonces, no hay necesidad de preocuparse de que la asignación sea el problema.

Perfiles de tiempo

Obtener un perfil de tiempo para su programa es sencillo: compilar con -prof -auto-all

$ ghc -O2 --make A.hs -prof -auto-all [1 of 1] Compiling Main ( A.hs, A.o ) Linking A ...

Y, para N = 200:

$ time ./A +RTS -p 749700 ./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total

que crea un archivo, A.prof, que contiene:

Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final) A +RTS -p -RTS total time = 13.18 secs (659 ticks @ 20 ms) total alloc = 4,904,116,696 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc numDivs Main 100.0 100.0

Indicando que todo su tiempo se gasta en numDivs, y también es la fuente de todas sus asignaciones.

Heap Profiles

También puede obtener un desglose de esas asignaciones ejecutando + RTS -p -hy, que crea A.hp, que puede ver convirtiéndolo en un archivo de postscript (hp2ps -c A.hp), generando:

lo cual nos dice que no hay nada de malo en el uso de tu memoria: se está asignando en un espacio constante.

Entonces su problema es la complejidad algorítmica de numDivs:

toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

Arregle eso, que es el 100% de su tiempo de ejecución, y todo lo demás es fácil.

Optimizaciones

Esta expresión es un buen candidato para la optimización de fusión de flujo , así que lo reescribiré para usar Data.Vector , así:

numDivs n = fromIntegral $ 2 + (U.length $ U.filter (/x -> fromIntegral n `rem` x == 0) $ (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))

Que debería fusionarse en un solo bucle sin asignaciones de montón innecesarias. Es decir, tendrá una mejor complejidad (por factores constantes) que la versión de la lista. Puede usar la herramienta ghc-core (para usuarios avanzados) para inspeccionar el código intermedio después de la optimización.

Probando esto, ghc -O2 --hacer Z.hs

$ time ./Z 749700 ./Z 3.73s user 0.01s system 99% cpu 3.753 total

Por lo tanto, redujo el tiempo de ejecución para N = 150 por 3.5x, sin cambiar el algoritmo en sí.

Conclusión

Tu problema es numDivs. Es el 100% de tu tiempo de ejecución y tiene una complejidad terrible. Piensa en numDivs, y cómo, por ejemplo, para cada N estás generando [2 .. n div 2 + 1] N veces. Intente recordar eso, ya que los valores no cambian.

Para medir cuál de sus funciones es más rápida, considere usar el criterio , que proporcionará información estadísticamente sólida sobre las mejoras de sub-microsegundos en el tiempo de ejecución.

Addenda

Como numDivs es el 100% de su tiempo de ejecución, tocar otras partes del programa no hará mucha diferencia, sin embargo, para fines pedagógicos, también podemos reescribir aquellos que usan la fusión de flujo.

También podemos reescribir trialList y confiar en la fusión para convertirlo en el bucle que escribe a mano en trialList2, que es una función de "prefix scan" (también conocida como scanl):

triaList = U.scanl (+) 0 (U.enumFrom 1 top) where top = 10^6

Del mismo modo para sol:

sol :: Int -> Int sol n = U.head $ U.filter (/x -> numDivs x > n) triaList

Con el mismo tiempo de ejecución general, pero un código un poco más limpio.

La respuesta de Dons es excelente sin ser un spoiler al dar una solución directa al problema.
Aquí quiero sugerir una pequeña tool que escribí recientemente. Le ahorra tiempo para escribir anotaciones SCC a mano cuando desea un perfil más detallado que el ghc -prof -auto-all predeterminado. ¡Además de eso es colorido!

Aquí hay un ejemplo con el código que dio (*), el verde está bien, el rojo es lento:

Todo el tiempo entra en crear la lista de divisores. Esto sugiere algunas cosas que puede hacer:
1. Haga que el filtrado n rem x == 0 más rápido, pero dado que es una función incorporada, probablemente ya sea rápido.
2. Crea una lista más corta. Ya has hecho algo en esa dirección al marcar solo hasta n quot 2 .
3. Deseche completamente la generación de listas y use algunos cálculos matemáticos para obtener una solución más rápida. Esta es la forma habitual de resolver problemas de Euler.

(*) Lo obtuve poniendo su código en un archivo llamado eu13.hs , agregando una función main = print $ sol 90 . Luego ejecuta visual-prof -px eu13.hs eu13 y el resultado está en eu13.hs.html .

Nota relacionada con Haskell: triaList2 es, por supuesto, más rápido que triaList porque este último realiza muchos cálculos innecesarios. Tomará un tiempo cuadrático calcular n primeros elementos de triaList , pero lineales para triaList2 . Existe otra forma elegante (y eficiente) de definir una lista infinita de números de triángulos:

triaList = 1 : zipWith (+) triaList [2..]

Nota relacionada con las matemáticas: no es necesario verificar todos los divisores hasta n / 2, es suficiente verificar el sqrt (n).

Puede ejecutar su programa con indicadores para habilitar el perfil de tiempo. Algo como esto:

./program +RTS -P -sprogram.stats -RTS

Eso debería ejecutar el programa y producir un archivo llamado program.stats que tendrá la cantidad de tiempo invertido en cada función. Puede encontrar más información sobre la creación de perfiles con GHC en la guía del usuario de GHC. Para la evaluación comparativa, está la biblioteca Criterion. Descubrí que this publicación de blog tiene una introducción útil.