10

フィボナッチ数列のn番目の項を計算するための次の2つのHaskellプログラムは、パフォーマンス特性が大きく異なります。

fib1 n =
  case n of
    0 -> 1
    1 -> 1
    x -> (fib1 (x-1)) + (fib1 (x-2))

fib2 n = fibArr !! n where
  fibArr = 1:1:[a + b | (a, b) <- zip fibArr (tail fibArr)]

これらは数学的には非常に似ていfib2ますが、リスト表記を使用して中間結果をメモし、fib1明示的な再帰があります。中間結果がキャッシュされる可能性があるにもかかわらず、fib1実行時間はの場合でも問題になりfib1 25、再帰的なステップが常に評価されることを示唆しています。参照透過性はHaskellのパフォーマンスに何か貢献しますか？できるかどうかを事前に知るにはどうすればよいですか？

これは私が心配していることのほんの一例です。怠惰に実行された関数型プログラミング言語のパフォーマンスについて推論することに固有の困難を克服することについての考えを聞きたいです。

要約： 私は3lectrologosの答えを受け入れています。なぜなら、コンパイラの最適化に関して、言語のパフォーマンスについてあまり推論しないという点は、Haskellでは非常に重要であるように思われるからです。と。コンパイラーの重要性は、怠惰で機能的な言語でのパフォーマンスに関する推論を、他のタイプのパフォーマンスに関する推論と区別する要因であると言いがちです。

補遺：この質問で起こっている人は誰でも、 JohanTibellの高性能Haskellについての話のスライドを見たいと思うかもしれません。

4

5 に答える 5

11

あなたの特定のフィボナッチの例では、なぜ2番目のものがより速く実行されるべきかを理解するのはそれほど難しいことではありません（f2が何であるかを指定していませんが）。

これは主にアルゴリズムの問​​題です。

  • fib1は純粋に再帰的なアルゴリズムを実装しており、（私が知る限り）Haskellには「暗黙のメモ化」のメカニズムがありません。
  • fib2は、明示的なメモ化を使用します（fibArrリストを使用して、以前に計算された値を格納します。

一般に、Haskellのような怠惰な言語のパフォーマンスを熱心な言語よりも仮定することははるかに困難です。それでも、（特に怠惰の）根本的なメカニズムを理解し、経験を積めば、パフォーマンスについていくつかの「予測」を行うことができます。

参照透過性は、（少なくとも）2つの方法で（潜在的に）パフォーマンスを向上させます。

  • まず、（プログラマーとして）同じ関数への2つの呼び出しが常に同じものを返すことを確認できるため、さまざまな場合にこれを利用してパフォーマンスを向上させることができます。
  • 第二に（そしてもっと重要なことですが）、Haskellコンパイラーは上記の事実を確信でき、これにより、不純な言語では有効にできない多くの最適化が可能になる可能性があります（コンパイラーを作成したことがあるか、コンパイラーの最適化の経験がある場合）おそらくこれの重要性を認識しています）。

Haskellのデザイン選択の背後にある理由（怠惰、純粋さ）についてもっと知りたい場合は、これを読むことをお勧めします。

于 2010-01-14T14:31:28.747 に答える
6

Haskellや怠惰な言語では、パフォーマンスについての推論は一般的に難しいですが、不可能ではありません。いくつかのテクニックは、ChrisOkasakiのPurelyFunction Data Structures（以前のバージョンでもオンラインで利用可能）でカバーされています。

パフォーマンスを確保するもう1つの方法は、注釈または継続渡しスタイルを使用して、評価順序を修正することです。そうすれば、物事がいつ評価されるかを制御できます。

あなたの例では、数値を「ボトムアップ」で計算し、前の2つの数値を各反復に渡すことができます。

fib n = fib_iter(1,1,n)
    where
      fib_iter(a,b,0) = a
      fib_iter(a,b,1) = a
      fib_iter(a,b,n) = fib_iter(a+b,a,n-1)

これにより、線形時間アルゴリズムが生成されます。

各結果が前のN個の結果に依存する動的計画法アルゴリズムがある場合は常に、この手法を使用できます。それ以外の場合は、配列またはまったく異なるものを使用する必要があります。

于 2010-01-14T15:46:03.513 に答える
5

fib2の実装ではメモ化を使用しますが、fib2を呼び出すたびに、「全体」の結果が再構築されます。ghciの時間とサイズのプロファイリングをオンにします。

Prelude> :set +s

「間」の呼び出しでメモ化を行っていた場合、後続の呼び出しはより高速になり、メモリを使用しません。fib2 20000を2回呼び出して、自分の目で確かめてください。

比較すると、正確な数学的単位元を定義する、より慣用的なバージョンは次のとおりです。

-- the infinite list of all fibs numbers.
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

memoFib n = fibs !! n

ご覧のとおり、実際にはメモ化を使用してください。memoFib 20000を2回実行すると、最初にかかった時間とスペースが表示され、2回目の呼び出しは瞬時に行われ、メモリは使用されません。コメントのような魔法や暗黙のメモ化はほのめかされていないかもしれません。

さて、あなたの最初の質問について：Haskellのパフォーマンスについての最適化と推論...

私は自分自身をHaskellの専門家とは呼びません。私は、Haskellを3年間しか使用しておらず、そのうち2年間は職場で使用していますが、最適化して、そのパフォーマンスについてある程度推論する方法を理解する必要がありました。

他の投稿で言及されているように、怠惰はあなたの友人であり、あなたがパフォーマンスを得るのを助けることができますが、あなたは何が怠惰に評価され、何が厳密に評価されるかを制御する必要があります。

foldlとfoldrのこの比較を確認してください

foldlは、実際には値を計算するための「方法」を格納します。つまり、遅延します。場合によっては、「無限の」フィブのように、怠惰な時間とスペースを節約できます。無限の「フィブ」はそれらすべてを生成するわけではありませんが、その方法を知っています。値が必要になることがわかっている場合は、「厳密に」言えばそれを取得することもできます...ここで、厳密性の注釈が有用であり、制御を取り戻すことができます。

私は何度も読んだことを思い出します。Lispでは、consingを「最小化」する必要があります。

厳密に評価されるものとそれを強制する方法を理解することは重要ですが、メモリに対してどれだけの「トラッシング」を行うかを理解することも重要です。Haskellは不変であることを忘れないでください。つまり、「変数」を更新すると、実際には変更を加えたコピーが作成されます。（:)は（++）とは逆にメモリをコピーしないため、（:)を付加するよりも（++）を付加する方がはるかに効率的です。大きなアトミックブロックが更新されるたびに（単一の文字であっても）、「更新された」バージョンを表すためにブロック全体をコピーする必要があります。データを構造化して更新する方法は、パフォーマンスに大きな影響を与える可能性があります。ghcプロファイラーはあなたの友達であり、あなたがこれらを見つけるのを助けます。確かにガベージコレクターは高速ですが、何もしないほうが高速です。

乾杯

于 2010-01-15T04:22:18.047 に答える
2

メモ化の問題とは別に、fib1は末尾呼び出し以外の再帰も使用します。末尾呼び出しの再帰は、単純なgotoに自動的にリファクタリングされ、非常にうまく機能しますが、結果を計算するためにfib1の各インスタンスからのスタックフレームが必要なため、fib1の再帰をこの方法で最適化することはできません。fib1を書き直して現在の合計を引数として渡すと、最後の加算のためにスタックフレームを保持する必要がなく、末尾呼び出しが可能になり、パフォーマンスが大幅に向上します。もちろん、メモ化された例ほどではありません:)

于 2010-01-19T03:35:48.230 に答える
1

割り当ては関数型言語の主要なコストであるため、パフォーマンスを理解する上で重要なのは、オブジェクトがいつ割り当てられるか、オブジェクトがどれだけ長く存続するか、いつ死ぬか、いつ回収されるかを理解することです。この情報を取得するには、ヒーププロファイラーが必要です。これは不可欠なツールであり、幸いなことにGHCには優れたツールが付属しています。

詳細については、ColinRuncimanの論文を参照してください。

于 2010-01-15T05:42:40.233 に答える