12

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

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

(一个答案还提到了工人/包装器转换,但这似乎相当先进。)

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

4

4 回答 4

15

以下是我经常参考的 Johan Tibell 的一些不错的幻灯片:

Haskell 性能模式

于 2012-07-14T12:37:12.870 回答
7

一个简单的建议是使用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]

于 2012-07-14T12:30:32.190 回答
5

Haskell wiki中有相当大的部分是关于性能的。

一个相当普遍的问题是太少(或太多)严格性(上面性能页面的通用技术部分中列出的部分涵盖了这一点)。懒惰太多会导致大量的thunk被积累,太严格会导致评估太多。

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

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

于 2012-07-14T07:38:51.783 回答
3

欧拉计划主要是为了找到解决问题的聪明算法解决方案。一旦你有了正确的算法,微优化就不会成为问题,因为即使是简单的或解释的(例如 Python 或 Ruby)实现也应该在速度限制内运行良好。您需要的主要技术是了解惰性评估,这样您就可以避免 thunk 堆积。

于 2012-07-15T03:59:54.400 回答