19

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

惨めな 5 メガバイトのファイルをブラウズするために、500 メガバイトの RAM と 30 秒の CPU が必要な理由を誰か説明してくれませんか? 私は何を間違っていますか？[word8] が ByteString のドキュメントに記載されているようにバッファリングされないのはなぜですか。そして、これを修正する方法は?

foldl、foldr、foldl' の代わりに、独自の末尾再帰フォールドを定義しようとしました。サンクもseqで解凍しようとしました。今のところ結果が出ていません。

行き詰まっているので、助けてくれてありがとう。

4

1 に答える 1

34

構文 "seq x x" は常に役に立ちません。y = seq xx で、y を強制する場合、これは x を強制し、x を返します。これは、y=x で y を強制することと同じです。したがって、「seq forceEval forceEval」は「forceEval」以上のことはしません。

折り畳みの使用に関するエラーは一般的なものです。

フォールドを使用して、入力のバイト数をカウントしています。そのような合計には厳密な左折を使用する必要がありますが、手書きの折畳みは怠惰な左折です。(acc+1) は評価されないため、500 万個のネストされたアプリケーションがビルドされます: (((...(0+1)+1)+1)+1)+1)+1)...+1 ）。すると印刷時に強制されて評価が500万かっこに落ちようとします。

したがって、保留中のスタックには、Word8 ごとに 1 つのエントリがあります。短い入力の場合、最後に到達して 0 と見なされます。長い入力の場合、GHC の作成者とほとんどのユーザーは、500 万のスタック フレームを割り当てようとするのは通常、プログラマーによる設計エラーであると考えているため、GHC のスタック スペースが不足します。

「seq」を使用してこれを修正できると予測します。

fold_tailrec' foldFun acc (x : xs) =
    let acc' = foldFun acc x
    in seq acc' (fold_tailrec' foldFun acc' xs)
于 2011-03-23T20:19:57.247 に答える