Чтение большого файла в haskell? - PullRequest
Новая
       41

Чтение большого файла в haskell?

18 голосов
/ 23 марта 2011

Я пытался прочитать большой файл в haskell.

Мне нужно сжать его, используя специальный алгоритм для университетского проекта.Все работает нормально, пока я не начну сжимать большие файлы.

Я извлек то, что пошло не так, из моей программы, и я выставляю это здесь в виде "Hello big file": 

import System
import qualified Data.ByteString.Lazy as BL
import Data.Word

fold_tailrec :: (a -> b -> a) -> a -> [b] -> a
fold_tailrec _ acc [] =
    acc
fold_tailrec foldFun acc (x : xs) =
    fold_tailrec foldFun (foldFun acc x) xs

fold_tailrec' :: (a -> b -> a) -> a -> [b] -> a
fold_tailrec' _ acc [] =
    acc
fold_tailrec' foldFun acc (x : xs) =
    let forceEval = fold_tailrec' foldFun (foldFun acc x) xs in
    seq forceEval forceEval

main :: IO ()
main =
    do
        args <- System.getArgs
        let filename = head args
        byteString <- BL.readFile filename
        let wordsList = BL.unpack byteString
        -- wordsList is supposed to be lazy (bufferized)
        let bytesCount = fold_tailrec (\acc word -> acc + 1) 0 wordsList
        print ("Total bytes in " ++ filename ++ ": " 
               ++ (show bytesCount))

Я называю этот файл Test.hs, затем делаю следующее: 

$ ls -l toto
-rwxrwxrwx 1 root root 5455108 2011-03-23 19:08 toto
$ ghc --make -O Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
$ ./Test toto
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
$ ./Test toto +RTS -K50M -RTS
Stack space overflow: current size 50000000 bytes.
Use `+RTS -Ksize -RTS' to increase it.
$ ./Test toto +RTS -K500M -RTS
"Total bytes in toto: 5455108"
$ time ./Test toto +RTS -K500M -RTS
"Total bytes in toto: 5455108"

real    0m33.453s
user    0m8.917s
sys 0m10.433s

Может кто-нибудь объяснить, почему мне нужно 500 мегабайт ОЗУ и 30 секунд ЦП, чтобы просмотреть несчастный файл 5 мегабайт?Пожалуйста, что я делаю не так?Почему [word8] не буферизуется, как указано в документации ByteString.И как это исправить?

Я попытался определить свой собственный рекурсивный сгиб хвоста вместо сгибов, сгибов или сгибов.Я также попытался разморозить Thunks с помощью seq.Я пока не получил никакого результата.

Спасибо за любую помощь, потому что я застрял.

1 Ответ

34 голосов
/ 23 марта 2011

Конструкция "seq xx" всегда бесполезна.Если y = seq xx и я форсирую y, то эта сила возвращает x.Это эквивалентно y = x и форсированию y.Таким образом, «seq forceEval forceEval» не делает ничего, кроме «forceEval».

Ошибка при использовании сгиба является обычной.

Вы используете сгиб, чтобы выполнить подсчетбайты на входе.Вы должны использовать строгий левый сгиб для такой суммы, но ваш рукописный сгиб - ленивый левый сгиб.(Acc + 1) не оценивается, поэтому он создает 5 миллионов вложенных приложений: (((... (0 + 1) +1) +1) +1) +1) +1) ... + 1).Затем происходит принудительная печать, и оценка пытается опуститься до 5 миллионов скобок.

Таким образом, ожидающий стек имеет одну запись для каждого Word8.Для коротких входов он достигает конца и видит 0. Для длинных входов он исчерпывает пространство стека с GHC, потому что создатели и большинство пользователей GHC думают, что попытка выделить 5 миллионов кадров стека обычно является ошибкой проектирования программистом.*

Я предсказываю, что вы можете использовать "seq", чтобы исправить это: 

fold_tailrec' foldFun acc (x : xs) =
    let acc' = foldFun acc x
    in seq acc' (fold_tailrec' foldFun acc' xs)
...