哈斯克尔懒字不懒？
哈斯克尔懒字不懒？
提问于 2013-09-02 10:26:11
我有以下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将按预期执行。
有办法绕过这件事吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-09-02 10:40:09
使用惰性元组有次优。最好将其改写为：
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在其第二个参数中返回其余输入的原因。不需要这笔钱。地图。文字管道。
您提交的版本泄露了空间。在大型文件上运行，它使用与文件大小成比例的堆(在640 k项上)。
$ 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)所以，正如您所说，它正在保留该文件。
那么，什么是保留记忆呢？一条线索是opt的折页。你给它一个懒散的元组。foldl是在其累加器中懒惰。
因此，您只需构建一长串未评估的+操作。opt上的砰砰模式没有什么区别，因为foldl从不计算它的累加器。只有当你在最后检查结果的时候，整个事情才会崩溃。
这是典型的太空泄漏。所以：
- 使用foldl‘--它在累加器中是严格的
- 完全避免中间列表(使用readInt + unfoldr)。
- 如果必须遍历列表，请在累加器上使用严格的元组以获得更好的性能。
Stack Overflow用户
发布于 2013-09-02 10:49:49
map (fst.fromJust.readInt) cont
这不应该是
main = do
cont <- getContents
putStrLn $ show $ snd $ foldl opt (0,0) $
unfoldr (readInt . dropWhile isSpace) cont页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18570937
复制相关文章
相似问题
腾讯云开发者
