在Haskell中读取大文件？

Question

在Haskell中读取大文件？

19

我一直在尝试使用Haskell读取大文件。

我需要使用自定义算法对其进行压缩，这是一个大学项目。一切都很顺利，直到我开始压缩大文件。

我从程序中找出了问题，并以“大文件你好”的形式展示出来：

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兆字节的RAM和30秒的CPU时间才能浏览一个区区5兆字节的文件？请问我做错了什么？为什么[word8]没有像ByteString文档所说的那样被缓存？该如何解决？

我尝试使用自己定义的尾递归函数来代替foldl、foldr或foldl'，并尝试使用seq来取消挂起的thunks，但目前还没有结果。

感谢任何帮助，因为我卡住了。

- Joel

1

@FUZxxl，这可能是一个简单的复现程序；如果我们还要处理他的压缩代码，那么理解该程序将更加困难。如果Joel真正想要的只是长度，最好使用stat(2)向操作系统询问并保存所有磁盘IO。 - sarnold

1

你为什么需要自己的fold呢？标准库中的那些应该可以很好地工作。由于惰性，尾递归并不总是Haskell中的正确选择。我认为你想要计算长度的方法是一个严格的左折叠，同时在累加器中也是严格的。你应该能够通过foldl'和可能的seq来实现这一点。 - Jason Dagit

1

@FUZxxl length 会导致内存泄漏。你必须将整个东西保留在内存中，因为在调用 length 之前它无法进行垃圾回收。 - Ezra

1

我建议您使用枚举器包而不是使用惰性IO。 - Jason Dagit

@Ezra：不对。试试类似 length [1..100000000] 这样的东西，它将在 O(1) 的时间内完成，因为 Haskell 可以在 length 迭代列表时垃圾回收字符串的开头。只有在之后再次使用列表时才会出现问题。 - fuz

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Kuklewicz · Accepted Answer

"seq x x" 这个结构总是没什么用的。如果设y=seq x x，然后强制使用y，这会强制执行x并返回x。这相当于y=x并强制使用y。因此，“seq forceEval forceEval”与“forceEval”没有什么区别。

你在使用fold时遇到的错误很常见。

你正在使用fold来计算输入中的字节数。对于这样的求和，你应该使用严格的左折叠，但是你手写的fold是懒惰的左折叠。由于(acc+1)没有被评估，所以它建立了500万个嵌套的应用程序: (((...(0+1)+1)+1)+1)+1)+1)...+1)。然后在打印时被强制执行，而评估尝试下降到500万个括号中。

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

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

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