4

次のリストを GHCi にロードすると、リストの 33 番目の項目である 3524578 を計算した直後にプログラムが最終的に閉じるまで、リストの計算が遅くなります。

fibonacci :: (Integral a) => [a]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

最初の行を削除して次の行をロードすると、リストは非常に高速に計算され、GHCi は閉じません。

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

ポリモーフィック リストがリストよりもずっと遅いのはなぜIntegerですか? なぜGHCiは閉じるのですか?

4

2 に答える 2

3

最初のバージョンでは、値のように見えますが、実際には関数 (Haskell 自体よりも下位レベルの関数) を記述します。

これを理解するには、あなたの定義で可能な次のコードについて考えてみてください。

main = println (fibonacci !! 17 :: Int, fibonacci !! 19 :: Integer)

もちろん、17 と 19 は完全に任意です。ポイントは、最初のタプル要素が のリストとしてフィボナッチを計算する必要があるのIntに対し、2 番目のタプル要素は のリストであると仮定することですIntegers。おそらくご存じのとおり、Haskell には中途半端なリストはなくInt、Integerリストは[Int]or [Integer](またはまったく異なるもの) です。

そのため、Haskell のランタイム システムに関する深い知識がなくても、純粋な論理的根拠に基づいて結論を下すことができます。これはfibonacci、何かのリストでもリストでもリストでもなく、そのようなリストを作成するためのレシピに過ぎませんInt。Integer要求に応じて。

そうは言っても、次のようなことをしている限り：

take 10 fibonacci

それほど重要ではありません (フィボナッチは最大 10 要素まで 1 回だけ計算されます)。

しかし、あなたが言うとき

map (fibonacci !!) [1..10]

フィボナッチがすべてのインデックスに対して再計算される可能性があります。明らかに、インデックスが高くなるほど、これには時間がかかります。

于 2013-10-01T14:41:15.330 に答える
1

怪しいと思ったのでちょっと調べてみました。まず、次の 2 つのモジュールを作成しました。

-- fib0.hs
fibonacci :: (Integral a) => [a]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)
main = print $ take 10000 $ fibonacci

-- fib1.hs
main = print $ take 10000 $ fibonacci
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

次に、次のようにコンパイルしghc -O2 -prof -auto-all fib0.hs & ghc -O2 -prof -auto-all fib1.hsます。そして、それらを実行しました。これは両方の fib を実行し、フラグはファイル名 fib0/1.prof を生成します。このファイルには、プログラムに関する実行時情報が含まれています。これを行うと、両方ともまったく同じ時間がかかったことがわかりました。(正確には 0.70 秒 - お使いのマシンでは時間がかかる場合があります。それほど長く待つことができない場合は、10000 要素を減らしてください)。&;fib0 +RTS -p & fib1 +RTS -p+RTS -p

でコンパイルしたことに気付くでしょう-O2。これにより、最適化が「レベル」2に設定されます。レベル0、1、および2の3つがあります。デフォルトでは、GHCiは を使用しますO0。それで試してみましたghc -O0 -prof -auto-all fib0.hs & ghc -O0 -prof -auto-all fib1.hs(ghc のデフォルトは-O1であるため、レベル 0 を手動で設定する必要があります)。私がそれらを実行したとき、fib0はメモリ不足の例外でクラッシュし、fib0は問題なく完了しました（非常にゆっくりと減少take 10000しなければなりませんでしtake 100たが、これは明らかに予想されることです）。

これは正常な動作です。最適化は、悪いプログラミングの間違いを取り除きます - 単一の型を使用することが有益であるときに手動でポリモーフィズムを強制するなど - 必要でない限り、これを行わないでください!

詳細を知りたい場合は、試してみてくださいghc -O0 -f-ext-core fib0.hs & ghc -O0 -f-ext-core fib1.hs。これにより、両方のプログラムの「コア」ファイルが生成されます。コアは、オブジェクト ファイルの作成を開始する前の GHC コンパイルの最後の段階です。プレーンテキストの .hcr ファイルを生成します。これらは非常に読みにくいかもしれないので、重要なポイントをいくつか紹介します。

fib0.hcr には以下が含まれます。

...
base:GHCziNum.fromInteger @ ac zddNumazzzz
...

基本的に、fromIntegerシーケンス内の 0 と 1 から始まるすべての番号を呼び出します。なぜこれを行うのですか？「フィボナッチの型は任意の数値型でなければならない」と伝えました。0 と 1 をIntegers として作成し、 を使用fromIntegerして型の値を作成しますNum a => a(これが多相リテラルを作成する唯一の方法です)。非常に高価なサンクをfromInteger構築するためのこれらすべての呼び出し- したがって、メモリ不足の例外が発生します。

fib1.hcr を見てください。どこにも含まれていませんfromInteger。フィボナッチの型を推測するために GHC を残すと、 のみを使用できますInteger。つまり、サンクはありません。

最適化によってこの問題が解消されるのはなぜですか? GHC は、数値を出力するためにフィボナッチのみを使用していることに気付きました。このポリモーフィズムは必要ありません。だからそれはそれを最適化します！インライン化など、フィボナッチをはるかに高速にする他のことも行うことに注意してください。

于 2013-10-01T22:01:03.367 に答える