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 回答