12

Project Eulerの問題を読んで作業することで、Haskellのプログラミングと学習を行うのは初めてです。もちろん、これらの問題のパフォーマンスを向上させるためにできる最も重要なことは、より優れたアルゴリズムを使用することです。ただし、パフォーマンスを改善するためのシンプルで簡単に実装できる方法が他にもあることは明らかです。大まかに検索すると、この質問とこの質問が表示され、次のヒントが得られます。

  • ghc フラグ -O2 および -fllvm を使用します。
  • ボックス化されていないため、Integer の代わりに Int 型を使用します (または Int64 の代わりに Integer を使用することもできます)。これには、関数を入力する必要があり、コンパイラーがその場で決定することはできません。
  • 分割テストには mod ではなく rem を使用します。
  • 必要に応じてシュワルツ変換を使用します。
  • 再帰関数でアキュムレータを使用する (末尾再帰の最適化だと思います)。
  • メモ化（？）

(1 つの回答では、ワーカー/ラッパーの変換についても言及されていますが、それはかなり進んでいるようです。)

質問:プロジェクト オイラー スタイルの問題のパフォーマンスを向上させるために、Haskell で行うことができる他の簡単な最適化は何ですか? Project Eulerの問題の解決をスピードアップするために使用できる、Haskell固有の(または関数型プログラミング固有の)アイデアや機能は他にありますか? 逆に気をつけるべきことは？避けるべき一般的だが非効率的なことは何ですか?

4

4 に答える 4

15

以下は、私がよく参照する Johan Tibell による優れたスライドです。

Haskell パフォーマンス パターン

于 2012-07-14T12:37:12.870 に答える
7

簡単な提案の 1 つhlintは、ソース コードをチェックし、構文の改善を提案するプログラムである which を使用することです。ほとんどの場合、コンパイラまたは遅延評価によって既に行われているため、これは速度を向上させない可能性があります。ただし、場合によってはコンパイラに役立つ場合があります。さらに、物事を行うためのより良い方法を学ぶことができるため、より優れた 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

プロジェクト オイラーの問題でできる最大の改善は、問題を理解し、不要な計算を削除することだと思います。すべてを理解していなくても、プログラムを 2 倍の速度で実行できる小さな修正を行うことができます。1.000.000 までの素数を探しているとしましょう。もちろんfilter isPrime [1..1000000]. しかし、少し考えてみると、上記の偶数は素数ではなく、(約) 半分の作業が削除されたことに気付くことができます。代わりに[1,2] ++ filter isPrime [3,5..999999]

于 2012-07-14T12:30:32.190 に答える
5

Haskell wiki には、パフォーマンスに関するかなり大きなセクションがあります。

かなり一般的な問題の 1 つは、厳しさが少なすぎる (または厳しすぎる) ことです (これは、上記のパフォーマンス ページの一般的なテクニックセクションに記載されているセクションで説明されています)。怠惰すぎると大量のサンクが蓄積され、厳密すぎると評価されすぎます。

これらの考慮事項は、末尾再帰関数 (つまり、アキュムレータを使用する関数) を記述する場合に特に重要です。また、関数の使用方法によっては、末尾再帰関数は、Haskell では同等の非末尾再帰関数よりも効率が悪い場合があります。

また、この最近の質問で示されているように、共有はパフォーマンスに大きな違いをもたらす可能性があります (多くの場合、これは一種のメモ化と見なすことができます)。

于 2012-07-14T07:38:51.783 に答える
3

Project Euler の主な目的は、問題に対する巧妙なアルゴリズムの解決策を見つけることです。適切なアルゴリズムがあれば、マイクロ最適化が問題になることはめったにありません。なぜなら、直接的または解釈された (Python や Ruby などの) 実装でさえ、速度の制約内で適切に実行されるはずだからです。必要な主なテクニックは、サンクの蓄積を避けるために遅延評価を理解することです。

于 2012-07-15T03:59:54.400 に答える