Semplici suggerimenti per aumentare le prestazioni Haskell (su problemi ProjectEuler)?

Question

Sono nuovo alla programmazione e all'apprendimento di Haskell leggendo e lavorando con i problemi di Project Euler. Naturalmente, la cosa più importante che si può fare per migliorare le prestazioni su questi problemi è usare un algoritmo migliore. Tuttavia, mi è chiaro che esistono altri modi semplici e facili da implementare per migliorare le prestazioni. Una ricerca sommaria allevato this question, e this question, che danno i seguenti suggerimenti:

• Utilizzare le bandiere ghc -O2 e -fllvm.
• Utilizzare il tipo Int, invece di Integer, perché è unbox (o anche intero anziché Int64). Ciò richiede di digitare le funzioni, non lasciare che il compilatore decida al volo.
• Utilizzare rem, non mod, per il test di divisione.
• Utilizzare Schwartzian transformations quando appropriato.
• Utilizzo di un accumulatore in funzioni ricorsive (un'ottimizzazione della ricorsione in coda, credo).
• Memoizzazione

(Una risposta menziona anche lavoratore/involucro trasformazione, ma che sembra abbastanza avanzata.)

domanda (?): Quali altri semplici ottimizzazioni si può fare in Haskell per migliorare le prestazioni sui problemi in stile Project Euler? Esistono altre idee o caratteristiche specifiche di Haskell (o specifiche di programmazione funzionale?) Che potrebbero essere utilizzate per velocizzare le soluzioni ai problemi di Project Euler? Viceversa, a cosa si dovrebbe prestare attenzione? Quali sono alcune cose comuni ma inefficienti da evitare?

Answer 1

C'è un fairly large section of the Haskell wiki sulle prestazioni.

Un problema abbastanza comune è la rigidità troppo piccola (o troppo) (questo è coperto dalle sezioni elencate nella sezione General techniques della pagina delle prestazioni sopra). Troppa pigrizia causa l'accumulo di un gran numero di thunk, troppo rigore può causare troppo da valutare.

Queste considerazioni sono particolarmente importanti quando si scrivono le funzioni ricorsive della coda (ad esempio quelle con un accumulatore); E, su quella nota, a seconda di come viene utilizzata la funzione, una funzione ricorsiva della coda è a volte meno efficiente in Haskell rispetto alla funzione non ricorsiva della coda equivalente, anche con le annotazioni di rigore ottimali.

Inoltre, come dimostrato da this recent question, la condivisione può fare un'enorme differenza per le prestazioni (in molti casi, questa può essere considerata una forma di memo).

Answer 2

Un suggerimento semplice è quello di utilizzare hlint che è un programma che controlla il codice sorgente e suggerisce suggerimenti per migliorare la sintassi saggia. Questo potrebbe non aumentare la velocità perché molto probabilmente è già fatto dal compilatore o dalla valutazione pigra. Ma lo potrebbe aiutare il compilatore in alcuni casi. Inoltre ti renderà un programmatore Haskell migliore dal momento che imparerai modi migliori per fare le cose, e potrebbe essere più facile capire il tuo programma e analizzarlo.

esempi tratti da http://community.haskell.org/~ndm/darcs/hlint/hlint.htm come ad esempio:

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

e

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 

penso che gli incrementi maggiori si possono fare in problemi Project Euler è quello di capire il problema e rimuovere calcoli inutili. Anche se non capisci tutto, puoi fare alcune piccole correzioni che faranno funzionare il tuo programma il doppio della velocità. Supponiamo che tu stia cercando numeri primi fino a 1.000.000, quindi ovviamente puoi fare filter isPrime [1..1000000]. Ma se ci pensi un po ', puoi rendertene conto bene, nessun numero pari sopra è un numero primo, ci hai rimosso (circa) metà del lavoro. Invece facendo [1,2] ++ filter isPrime [3,5..999999]

Answer 3

Ecco alcuni buoni diapositive di Johan Tibell che spesso si riferiscono a:

Haskell Performance Patterns

Answer 4

Project Euler è per lo più sulla ricerca di soluzioni algoritmiche intelligenti ai problemi. Una volta ottenuto l'algoritmo corretto, la micro-ottimizzazione è raramente un problema, dal momento che anche un'implementazione diretta o interpretata (ad es. Python o Ruby) dovrebbe funzionare bene entro i limiti di velocità. La tecnica principale di cui hai bisogno è la comprensione della valutazione pigra, in modo da evitare accumuli di thunk.