¿Se mejoran los consejos simples para el rendimiento de Haskell (en problemas de ProjectEuler)?

Question

Soy nuevo en la programación y el aprendizaje de Haskell leyendo y resolviendo problemas de Project Euler. Por supuesto, lo más importante que uno puede hacer para mejorar el rendimiento en estos problemas es usar un mejor algoritmo. Sin embargo, es claro para mí que hay otras formas simples y fáciles de implementar para mejorar el rendimiento. Una búsqueda superficial criado this question y this question, que dan los siguientes consejos:

• uso de las banderas de GHC -O2 y -fllvm.
• Utilice el tipo Int, en lugar de Entero, porque está desagrupado (o incluso entero en lugar de Int64). Esto requiere escribir las funciones, sin dejar que el compilador decida sobre la marcha.
• Use rem, no mod, para las pruebas de división.
• Use Schwartzian transformations cuando corresponda.
• Uso de un acumulador en funciones recursivas (una optimización de recursión de cola, creo).
• memoization

(Una respuesta también menciona trabajador/transformación envoltorio, pero que parece bastante avanzada.)

de interrogación (?): ¿Qué otras optimizaciones sencilla se puede hacer en Haskell para mejorar el rendimiento en los problemas de estilo Proyecto Euler? ¿Hay alguna otra idea o característica específica de Haskell (o ¿específica de la programación funcional?) Que pueda usarse para ayudar a acelerar las soluciones a los problemas del Proyecto Euler? Por el contrario, ¿qué debería uno tener cuidado? ¿Cuáles son algunas cosas comunes pero ineficientes que deben evitarse?

Answer 1

Hay un fairly large section of the Haskell wiki sobre el rendimiento.

Un problema bastante común es muy poco (o demasiado) rigor (esto está cubierto por las secciones enumeradas en la sección General techniques de la página de rendimiento anterior). Demasiada pereza hace que se acumule una gran cantidad de thunks, demasiado rigor puede causar que se evalúe demasiado.

Estas consideraciones son especialmente importantes cuando se escriben funciones recursivas de cola (es decir, aquellas con un acumulador); Y, en esa nota, dependiendo de cómo se usa la función, una función recursiva de cola es a veces menos eficiente en Haskell que la función equivalente no cola recursiva, incluso con las anotaciones de rigor óptimas.

Además, como se demostró en this recent question, compartir puede hacer una gran diferencia en el rendimiento (en muchos casos, esto se puede considerar una forma de memorización).

Answer 2

Una sugerencia fácil es usar hlint que es un programa que verifica su código fuente y hace sugerencias para mejorar la sintaxis. Esto puede no aumentar la velocidad porque lo más probable es que ya lo haya hecho el compilador o la evaluación diferida. Pero podría ayudar al compilador en algunos casos. Además, te convertirá en un mejor programador de Haskell ya que aprenderás mejores formas de hacer las cosas, y podría ser más fácil entender tu programa y analizarlo.

ejemplos tomados de http://community.haskell.org/~ndm/darcs/hlint/hlint.htm tales como:

darcs-2.1.2\src\CommandLine.lhs:94:1: Error: Use concatMap 
Found: 
    concat $ map escapeC s 
Why not: 
    concatMap escapeC s 

y

darcs-2.1.2\src\Darcs\Patch\Test.lhs:306:1: Error: Use a more efficient monadic variant 
Found: 
    mapM (delete_line (fn2fp f) line) old 
Why not: 
    mapM_ (delete_line (fn2fp f) line) old 

creo que los mayores incrementos se puede hacer en problemas Proyecto Euler es comprender el problema y eliminar cálculos innecesarios. Incluso si no comprende todo, puede hacer algunas correcciones pequeñas que harán que su programa corra el doble de velocidad. Digamos que estás buscando números primos de hasta 1.000.000, entonces por supuesto puedes hacer filter isPrime [1..1000000]. Pero si piensas un poco, entonces puedes darte cuenta de que así, ni siquiera el número anterior es primo, allí has ​​eliminado (aproximadamente) la mitad del trabajo. En su lugar haciendo [1,2] ++ filter isPrime [3,5..999999]

Answer 3

Aquí están algunas buenas diapositivas de Johan Tibell que con frecuencia me refiero a:

Haskell Performance Patterns

Answer 4

Proyecto Euler es principalmente acerca de la búsqueda de soluciones algorítmicas inteligentes a los problemas. Una vez que tiene el algoritmo correcto, la microoptimización rara vez es un problema, ya que incluso una implementación directa o interpretada (por ejemplo, Python o Ruby) debe funcionar bien dentro de las limitaciones de velocidad. La técnica principal que necesita es comprender la evaluación lenta para evitar las acumulaciones de thunk.