ハスケルボトムアップDP空間リーク

Question

謝罪これがあまりにも具体的な場合は、私はここに新しいと妥当なものが正確ではない。私は何時間もこの問題に対して頭を打つことを何もしてこなかった。次のコードは、私の競合プログラミング問題の実装です。

これは、DPテーブルの各行を以前の解決策の折り目を使って生成するボトムアップの動的プログラミングソリューションのように機能するということです。理論的には、GHCはテーブルのすべての古い行を最適化できるはずです。しかし、約l = 2000とlength f = 5000で適度に大きな入力にこのプログラムを実行している、私はこれを取得：ピーク時にメモリの878メガバイトを使用しています

> time ./E < E.in 
0 
1.98user 0.12system 0:02.10elapsed 99%CPU (0avgtext+0avgdata 878488maxresident)k 
0inputs+0outputs (0major+219024minor)pagefaults 0swaps 

！私が生成しているテーブルはたったの10,000行で、理論的には一度に1行しか必要ありません！これは何らかの形のサンクの漏れまたは他のスペースリークであることは明らかです。プロファイリングでは、runが実行時間とメモリの合計の99％を消費していることがわかります。さらに調査すると、その98％がzipWithコールにあったことが示されました。

> time ./E < E.in 
0 
1.39user 0.08system 0:01.48elapsed 99%CPU (0avgtext+0avgdata 531400maxresident)k 
0inputs+0outputs (0major+132239minor)pagefaults 0swaps 

メモリだけで70％の実行時間、および60％です：興味深いことに、私のカスタムでzipWith minへの呼び出しを置き換えるzipMin機能が大幅に改善を生成します！私はこの仕事をするためにあらゆる種類の試みをしました。私は(++)が一般的に悪い考えであることを知っているので、runのリストをData.Sequence.Seq Intと置き換えました。遅くなり、より多くのメモリを使用しました。私はハスケルで特に経験はありませんが、ここで私の気分は終わりです。私はこの問題に対する答えがまだあることを確信していますが、私はそれを見つけることができるようにハスケルにはあま​​りにも新しいです。

あなたが提供できるヘルプは非常に高く評価されています。私は間違ったやり方、将来の診断方法、そしてそれを修正する方法を正確に説明することが大好きです。

ありがとうございます。

EDIT：スティーブンの優秀な助言に従い、アンボクシングと私のリストを交換した後

はパフォーマンスがあるベクトル...ええと... signficantlyが向上：

> time ./E < E.in 
0 
0.01user 0.00system 0:00.02elapsed 80%CPU (0avgtext+0avgdata 5000maxresident)k 
24inputs+0outputs (0major+512minor)pagefaults 0swaps 

Answer 1

をので、使用してfoldl'あなたはアキュムレータがWHNFにあることを保証しています。 WHNFにリストを入れると、リストの最初の要素だけが評価されます。リストの残りの部分はサンクとして存在し、サンドとして前後に折り返し呼び出されます。リストの複数のポジションに一度に関心がある（つまり、zipWithにその一部をドロップしている）ので、リストの大部分は以前の反復から保護されています。

ここで必要な構造はボックス化されていないベクトルです。ボックス化されていないベクトルは、すべてが最大限に厳格であり、はるかに少ないメモリで実行されることを保証します。