3

以下程序在计算 250 MB 文件中的不同行长度时使用 100+ MB RAM。如何修复它以使用更少的 RAM？我想我滥用了惰性 IOfoldr和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

遍历构造 thunk 的整个行列表 - 当时甚至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

这样这些行就可以在读入后立即被垃圾收集，并且不会在值中建立任何thunk。这样你就不需要一次在内存中超过一行文件，甚至不需要完全在内存中，因为length在它被记录到Map.

如果您的containers包裹足够新，您还可以

import Data.Map.Strict

并离开count使用insertWith（没有素数，Data.Map.Strict模块总是评估放入地图的值）。

于 2012-12-24T19:52:54.277 回答
0

降低最大驻留率的一种方法是使用IntMap而不是，它是键数据结构Map的专用版本。这是一个简单的改变：MapInt

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 回答