Haskell性能的简单提示会增加(关于ProjectEuler问题)？

Question

通过阅读和解决Project Euler问题,我是编程和学习Haskell的新手.当然,改善这些问题的性能最重要的是使用更好的算法.但是,我很清楚,还有其他简单易行的方法可以提高性能.粗略搜索提出了这个问题,这个问题给出了以下提示:

• 使用ghc标志-O2和-fllvm.
• 使用Int类型而不是Integer类型,因为它是未装箱的(甚至是Integer而不是Int64).这需要键入函数,而不是让编译器即时决定.
• 使用rem而不是mod进行分区测试.
• 适当时使用Schwartzian变换.
• 在递归函数中使用累加器(尾递归优化,我相信).
• 记忆(？)

(一个答案也提到了工人/包装器转换,但这看起来相当先进.)

问题:在Haskell中可以进行哪些其他简单的优化来提高Project Euler风格问题的性能？是否有任何其他Haskell特定的(或特定于函数编程的？)想法或特性可用于帮助加速Project Euler问题的解决方案？相反,应该注意什么？什么是常见但低效的事情要避免？

Answer 1

以下是Johan Tibell的一些很好的幻灯片,我经常提到:

Haskell性能模式

Answer 2

一个简单的建议是使用hlint哪个程序检查您的源代码并提出改进语法建议.这可能不会提高速度,因为很可能它已经由编译器或延迟评估完成.但在某些情况下,它可能有助于编译器.更进一步,它将使您成为更好的Haskell程序员,因为您将学习更好的方法来做事,并且可能更容易理解您的程序并进行分析.

例子来自http://community.haskell.org/~ndm/darcs/hlint/hlint.htm,例如:

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

和

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

我认为你在Project Euler问题上可以做的最大的增长是理解问题并删除不必要的计算.即使你不了解所有内容,你也可以做一些小的修复,这将使你的程序运行速度提高两倍.假设您正在寻找高达1.000.000的素数,那么您当然可以做到filter isPrime [1..1000000].但是如果你想一点,那么你就能意识到这一点,上面的偶数都不是一个素数,你已经删除了(约)一半的工作.相反做[1,2] ++ filter isPrime [3,5..999999]

Answer 3

关于性能,Haskell维基有一个相当大的部分.

一个相当常见的问题是太少(或太多)严格(这由上面的性能页面的常规技术部分中列出的部分涵盖).太多的懒惰导致大量的thunk积累,太严格会导致太多的评估.

在编写尾递归函数(即带累加器的函数)时,这些考虑因素尤其重要; 并且,在该注释中,根据函数的使用方式,尾随递归函数在Haskell中的效率有时低于等效的非尾递归函数,即使使用最优严格注释也是如此.

此外,正如最近的这个问题所证明的那样,共享会对性能产生巨大影响(在许多情况下,这可以被视为一种记忆形式).