Haskell ленивый Bytestring слова не ленивый?

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

Решение

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

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 тыс. Записей).

$ 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).
  • Если вам необходимо просмотреть список, используйте строгий кортеж на аккумуляторе для еще лучшей производительности.
Источник

map (fst.fromJust.readInt) cont

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

main = do
    cont <- getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $
               unfoldr (readInt . dropWhile isSpace) cont
Источник
Другие вопросы по тегам