使用Data.Map计算不同的值会泄漏内存

Question

在250 MB文件中计算不同的行长度时,以下程序使用100+ MB RAM.如何修复它以减少使用RAM？我想我误用懒惰的IO,foldr以及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

Answer 1

第一个重大错误

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

遍历构成thunk的整个行列表 - 此时甚至不会length因为懒惰而评估调用 - 然后从右到左进行评估.所以整个文件内容除了用于构建的thunk之外还在内存中Map.

如果你从一系列事物中建立一个地图,总是使用一个严格的左边折叠(好吧,如果列表很短,而且事情不是很大,那没关系)除非语义要求正确折叠(如果你'使用非交换函数重新组合值,可能是这种情况,但即使这样,通常最好reverse在构建映射之前使用左折叠和列表).

Data.Maps(或Data.IntMaps)是严格的脊椎,单独使得在遍历整个列表之前不可能生成部分输出,因此foldr这里不能使用强项.

下一个(可能的)问题是(再次懒惰),当你把它们放入时,你不会评估映射到的值Map,所以如果有一个特别经常出现的行长度,那么这个值就变成了一个巨大的thunk

((...((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模块总是评估放入地图的值).