haskell - 使用 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 调用 - 然后从右到左评估它。因此，除了用于构建 Map 的 thunk 之外，整个文件内容都在内存中。

如果您根据事物列表构建 map ，始终使用严格的左折叠(好吧，如果列表很短，并且事物不大，则没关系)，除非语义需要右折叠(如果您使用非交换函数组合值，则可能是这种情况，但即使如此，通常最好使用左折叠并反转之前的列表构建 map )。

Data.Map(或Data.IntMap)是spine-strict的，仅此一点就使得在遍历整个列表之前不可能生成部分输出，所以这里不能使用 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< 之前就已被评估。/.

如果您的容器包足够新，您也可以

import Data.Map.Strict

并使用insertWith保留count(没有prime，Data.Map.Strict模块始终评估放入 map 中的值)。