Haskell lazy Ошибочные слова не ленивы?

Question

У меня есть следующая программа на 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)) 

Он использует только малую постоянную величину памяти, но, конечно, это мучительно медленно (примерно 25x медленнее).

Проблема возникает только для программ, которые читают очень большие строки. Если ввод распределен по нескольким небольшим строкам, ByteString выполняет так, как ожидалось.

Есть ли способ обойти это?

Answer 1

Использование ленивых кортежей субоптимально. Это лучше переписать как:

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 возвращает оставшийся вход во 2-й параметр. Нет необходимости в сумме. карта . слова.

---

В версии, которую вы представили, просачивается пространство. Запустите большой файл, и он использует кучу, пропорциональную размеру файла (на 640 тыс. Записей).

$ 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 - lazy in its accumulator.

Итак, вы просто строите длинную цепочку необоснованных операций +. Модели удар по opt не имеют значения, так как foldl никогда не оценивает его аккумулятор. Только когда вы, наконец, проверите результат в конце, все это рухнет.

Это классическая утечка пространства. Итак:

• Использование foldl»- это строго в аккумуляторе
• Избегайте промежуточные списки полностью (использование readInt + unfoldr).
• Если вы должны пройти список, используйте строгий кортеж на аккумуляторе для повышения производительности.

Answer 2

map (fst.fromJust.readInt) cont

не должно это быть

main = do 
    cont <- getContents 
    putStrLn $ show $ snd $ foldl opt (0,0) $ 
       unfoldr (readInt . dropWhile isSpace) cont