使用Writer monad写入文件时如何避免内存问题？

Question

我正在构建一些中等大小的DIMACS文件,但是使用下面使用的方法,与生成的文件大小相比,内存使用量相当大,而在我需要生成的一些较大文件上,我会out of memory遇到问题.

import Control.Monad.State.Strict
import Control.Monad.Writer.Strict
import qualified Data.ByteString.Lazy.Char8 as B
import Control.Monad
import qualified Text.Show.ByteString as BS
import Data.List

main = printDIMACS "test.cnf" test

test = do
  xs <- freshs 100000
  forM_ (zip xs (tail xs))
    (\(x,y) -> addAll [[negate x, negate y],[x,y]])

type Var = Int
type Clause = [Var]

data DIMACSS = DS{
  nextFresh :: Int,
  numClauses :: Int
} deriving (Show)

type DIMACSM a = StateT DIMACSS (Writer B.ByteString) a

freshs :: Int -> DIMACSM [Var] 
freshs i = do
  next <- gets nextFresh
  let toRet = [next..next+i-1]
  modify (\s -> s{nextFresh = next+i}) 
  return toRet

fresh :: DIMACSM Int
fresh = do
  i <- gets nextFresh
  modify (\s -> s{nextFresh = i+1}) 
  return i

addAll :: [Clause] -> DIMACSM ()
addAll c = do
  tell 
    (B.concat . 
    intersperse (B.pack " 0\n") . 
    map (B.unwords . map BS.show) $ c)
  tell (B.pack " 0\n")
  modify (\s -> s{numClauses = numClauses s + length c})

add h = addAll [h]

printDIMACS :: FilePath -> DIMACSM a -> IO ()
printDIMACS file f = do
  writeFile file ""
  appendFile file (concat ["p cnf ", show i, " ", show j, "\n"])
  B.appendFile file b
   where
     (s,b) = runWriter (execStateT f (DS 1 0))
     i = nextFresh s - 1
     j = numClauses s

我想保留monadic的条款,因为它非常方便,但我需要克服记忆问题.如何优化上述程序,使其不会占用太多内存？

Answer 1

如果你想要良好的内存行为,你需要确保在生成它们时写出子句,而不是在内存中收集它们并将它们转储,如使用延迟或更明确的方法,如管道,枚举器,管道等等.

这种方法的主要障碍是DIMACS格式需要标题中的子句和变量的数量.这可以防止幼稚实现充分懒惰.有两种可能性:

务实的是将条款首先写入临时位置.之后,数字已知,因此您将它们写入实际文件并附加临时文件的内容.

如果子句的生成没有副作用(除了你的DIMACSMmonad 提供的效果)并且足够快,那么更漂亮的方法是可能的:运行两次,首先扔掉子句,只计算数字,打印标题行,运行发电机再次; 现在打印条款.

_{(这来自我实施SAT-Britney的经验,我采用了第二种方法,因为它更符合其他要求.)}

此外,在你的代码中,addAll不够懒惰:c即使在写出(在MonadWriter某种意义上)条款之后,列表也需要保留.这是另一个空间泄漏.我建议你实现add原始操作然后addAll = mapM_ add.