3

我有以下 Haskell 程序来计算一串整数的最大和子串：

{-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -O2 #-}
import Data.Functor
import Data.Maybe 
import Data.ByteString.Lazy.Char8 (getContents,lines,readInt,words)
import Prelude hiding (getContents,words,lines)

main = do
    cont <- words <$> getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $ map (fst.fromJust.readInt) cont

opt (!c,!m) x = (max 0 (c+x),max m (c+x))

这个程序的问题在于它将整个文件读入内存。对应的没有BytesString的程序就没有这个问题：

{-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -O2 #-}
import Data.Functor
import Data.Maybe 

main = do
    cont <- words <$> getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $ map read cont
opt (!c,!m) x = (max 0 (c+x),max m (c+x))

它只使用少量的恒定内存，但当然速度非常慢（大约慢 25 倍）。

该问题仅发生在读取非常大行的程序中。如果输入分布在多条小行上，ByteString 将按预期执行。

有没有办法解决？

4

2 回答 2

6

使用惰性元组是次优的。最好重写为：

main = do
    cont <- words <$> getContents
    putStrLn $ show $ sndT $ foldl opt (T 0 0) $ map (fst.fromJust.readInt) cont

sndT :: T -> Int
sndT (T _ m) = m

opt (T c m) x = T (max 0 (c+x)) (max m (c+x))

data T = T {-# UNPACK #-} !Int  {-# UNPACK #-}!Int

所以你得到了一个严格的、未装箱的累加器。然而，你最好把整个事情写成一个增量的左折叠。这就是为什么readInt在其第二个参数中返回剩余输入的原因。不需要总和。地图 。词管道。

您提交的版本泄漏空间。在一个大文件上运行，它使用与文件大小成比例的堆（在 640k 条目上）。

$ time ./A +RTS -p -s -K50M < input.txt.2
346882
     326,337,136 bytes allocated in the heap
     302,321,732 bytes copied during GC
      82,617,772 bytes maximum residency (8 sample(s))
       1,466,500 bytes maximum slop
             149 MB total memory in use (0 MB lost due to fragmentation)

  %GC     time      63.8%  (63.9% elapsed)

因此，正如您所说，它保留了文件。

在此处输入图像描述

那么什么是保留记忆呢？一个线索是带有 的 foldl opt。你传递给它一个惰性元组。并且对它的累加器foldl很懒惰。

因此，您只是在构建一长串未经评估的+操作。bang 模式opt没有任何区别，因为foldl从不评估它的累加器。只有当你最终检查结果时，整个事情才会崩溃。

这是经典的空间泄漏。所以：

  • 使用 foldl' - 在累加器中是严格的
  • 完全避免中间列表（使用 readInt + 展开器）。
  • 如果您必须遍历列表，请在累加器上使用严格的元组以获得更好的性能。
于 2013-09-02T10:40:09.877 回答
1

map (fst.fromJust.readInt) cont

这不应该是

main = do
    cont <- getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $
               unfoldr (readInt . dropWhile isSpace) cont
于 2013-09-02T10:49:49.860 回答