在haskell中读取大文件？

Question

我一直在尝试在 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 MB RAM 和 30 秒的 CPU 才能浏览一个可怜的 5 MB 文件？请问我做错了什么？为什么 [word8] 没有按照 ByteString 文档所述进行缓冲。以及如何解决这个问题？

我尝试定义自己的尾递归折叠而不是foldl、foldr 或foldl'。 我也尝试用 seq 解冻 thunk。 到目前为止我还没有结果。

感谢您的任何帮助，因为我被困住了。

Answer 1

构造“seq x x”始终是无用的。如果 y = seq xx 并且我强制 y，则强制 x 然后返回 x。这相当于 y=x 并强制 y。因此，“seqforceEvalforceEval”只不过是“forceEval”。

使用折叠的错误是一种常见错误。

您正在使用折叠来执行输入中的字节计数。对于这样的总和，您应该使用严格的左折叠，但您的手写折叠是惰性左折叠。 (acc+1) 没有得到评估，因此它构建了 500 万个嵌套应用程序：(((...(0+1)+1)+1)+1)+1)+1)...+1 ）。然后在打印时强制执行，求值尝试下降到 500 万个括号。

因此，挂起堆栈对于每个 Word8 都有一个条目。对于短输入，它到达末尾并看到 0。对于长输入，它会耗尽 GHC 的堆栈空间，因为 GHC 的创建者和大多数用户认为尝试分配 500 万个堆栈帧通常是程序员的设计错误。

我预测你可以使用“seq”来解决这个问题：

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