なぜ[x | x < - [1..10]]メソッドがHaskellで遅いのですか？

Question

なぜこのようなものがハスケルで非常に遅く走るのですか？

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a] 

print $ length test 

実行するための唯一の程度10^8数字がありますが、それは瞬く間に行われるべきであるが、それは永遠に、ほとんど墜落し実行しているように思えます。

Answer 1

これはghciまたはコンパイルされたプログラムで実行していますか？それは大きな違いをもたらします。

ghciの場合、ghciは後で使用する場合のために計算された値testを保持します。通常、これは良い考えですが、この場合はtestがとにかく再計算するのに安い巨大な値ではありません。どのくらい巨大ですか？初心者は10^8要素のリストです（64ビットシステムでは）、リストあたりの要素数は24バイトなので、すでに2.4Gです。次に、値そのものの領域使用があります。値はすべて[1..100]から取られていると考えるかもしれないので、それらは共有され、合計で無視できる量のスペースを使用する必要があります。しかし、リスト内の値は実際にはxという形式になります。a、b、c、d、lengthは、リスト内の値を調べることはありません。したがって、各要素は、a、b、cおよびdを参照するクロージャとして表現されます。これは少なくとも8 *（4 + 1）= 40バイトを要し、合計6.4Gになります。

ガーベッジコレクタは、6.4Gのデータを割り当てたときにガーベッジコレクタがかなり多くのコピーを実行しなければならず、すべてが永続的に生きています。それは実際にはリストやその長さを計算するのではなく、時間がかかります。

あなたがプログラムに

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a] 

main = print $ length test 

をコンパイルする場合、testは、その長さは明らかにそれを再び使用する予定はありませんされると、計算されているとして、ライブに保持する必要はありません。だからGCにはほとんど何もすることができず、プログラムは数秒で実行されます（の〜10^8リストノードの割り当てと計算には妥当です）。

Answer 2

あなたはループを10^8回実行しているだけでなく、10^8個の要素でリストを作成しています。 lengthを使用しているので、Haskellはリスト全体を実際に評価してその長さを返す必要があります。リストの各要素は1語を取ります。これは32ビットでも64ビットでも構いません。 32ビット（4バイト）という楽観的な仮定では、400 MB（約381.5 MiB）のメモリを割り当てたばかりです。 64ビットの場合、割り当てたメモリは800 MB（約763 MiB）です。あなたのシステム上で何が起こっているかに応じて、スワップファイル/スワップパーティションをヒットさせるには、あまりにも多くのRAMをチャンクに割り当てます。

他の微妙なことが起こっている場合、私はそれらを認識していませんが、メモリ使用量がこれがなぜとても遅いのかについての最初の疑念です。