3

次のプログラムは、250 MB のファイルでさまざまな行の長さをカウントするときに、100 MB 以上の RAM を使用します。RAM の使用量を減らすにはどうすればよいですか? foldr怠惰なIOと値の怠惰を誤用したと思いData.Mapます。

import Control.Applicative
import qualified Data.Map as M
import Data.List

main = do
  content <- readFile "output.csv"
  print $ (foldr count M.empty . map length . lines) content

count a b = M.insertWith (+) a 1 b
4

2 に答える 2

5

最初の大きな間違い

main = do
  content <- readFile "output.csv"
  print $ (foldr count M.empty . map length . lines) content

count a b = M.insertWith (+) a 1 b

使用してfoldrいます。それはフォームの式を構築します

length firstLine `count` length secondLine `count` ... `count` length lastLine `count` M.empty

サンクを構成する行のリスト全体をトラバースします-その時点ではlength、怠惰のために呼び出しを評価することすらありません-その後、右から左に評価されます。したがって、ファイルの内容全体がメモリ内にあり、Map.

もののリストからマップを構築する場合は、セマンティクスが右の折りたたみを必要としない限り、常に厳密な左の折りたたみを使用します (リストが短く、物事が大きくない場合は問題ありません)。非可換関数を使用して値を結合する場合、その場合もあるかもしれませんが、その場合でもreverse、マップを作成する前に左折畳みとリストを使用する方が望ましい場合がよくあります)。

Data.Maps (またはData.IntMaps) はスパイン厳密であり、それだけでは、リスト全体がトラバースされる前に部分的な出力を生成することが不可能になるため、foldrここでは の強みを使用できません。

次の（可能性のある）問題は、マッピング先の値を に配置するときに評価しないことです（これも怠惰です）。そのMapため、特に頻繁に発生する行の長さがある場合、その値は巨大なサンクになります。

((...((1+1)+1)...+1)+1)

成功する

main = do
  content <- readFile "output.csv"
  print $ (foldl' count M.empty . map length . lines) content

count mp a = M.insertWith' (+) a 1 mp

行が読み込まれるとすぐにガベージ コレクションが実行され、値にサンクが蓄積されないようにします。そうすれば、一度に複数行のファイルをメモリに格納する必要はなく、ファイル全体をメモリに格納する必要もありません。lengthこれは、 が に記録される前に評価されるためですMap。

containersパッケージが十分に新しい場合は、次のこともできます

import Data.Map.Strict

そのままcount使用しますinsertWith(プライムを使用しない場合、Data.Map.Strictモジュールはマップに入れられた値を常に評価します)。

于 2012-12-24T19:52:54.277 に答える
0

最大レジデンシーを下げる 1 つの方法は、キーのデータ構造の特殊なバージョンである のIntMap代わりに使用することです。それは簡単な変更です:MapMapInt

import Control.Applicative
import qualified Data.IntMap as I
import Data.List

main = do
  content <- readFile "output.csv"
  print $ (foldr count I.empty . map length . lines) content

count a b = I.insertWith (+) a 1 b

最大レジデンシーを使用してこのバージョンをあなたのバージョンと比較すると/usr/share/dict/words、約 100MB から 60MB になりました。これも最適化フラグがないことに注意してください。それらをクランクすると、最大居住者数がさらに改善される可能性が非常に高くなります。

于 2012-12-24T19:25:25.433 に答える