10

非常に大きな Unicode テキスト ファイル (6 GB 以上) を処理しようとしています。私が欲しいのは、それぞれのユニークな単語の頻度を数えることです。Data.Mapファイルをトラバースするときに、各単語のカウントを追跡するために strict を使用します。プロセスに時間がかかりすぎ、メモリが多すぎます (20 GB 以上)。マップが巨大であると思われますが、ファイルのサイズの 5 倍に達するかどうかはわかりません! コードを以下に示します。私は次のことを試したことに注意してください:

  • Data.HashMap.Strictの代わりに使用しData.Map.Strictます。Data.Mapメモリ消費の増加率が遅いという点でパフォーマンスが向上しているようです。

  • ByteStringlazyの代わりに lazyを使用してファイルを読み取りますText。そして、それを Text にエンコードして何らかの処理を行ってからByteString、 forにエンコードし直しIOます。

    import Data.Text.Lazy (Text(..), cons, pack, append)
    import qualified Data.Text.Lazy as T
    import qualified Data.Text.Lazy.IO as TI
    import Data.Map.Strict hiding (foldr, map, foldl')
    import System.Environment
    import System.IO
    import Data.Word
    
    dictionate :: [Text] -> Map Text Word16
    dictionate = fromListWith (+) . (`zip` [1,1..])
    
    main = do
        [file,out] <- getArgs
        h <- openFile file ReadMode
        hO <- openFile out WriteMode
        mapM_ (flip hSetEncoding utf8) [h,hO]
        txt <- TI.hGetContents h
        TI.hPutStr hO . T.unlines . 
          map (uncurry ((. cons '\t' . pack . show) . append)) . 
          toList . dictionate . T.words $ txt
        hFlush hO
        mapM_ hClose [h,hO]
        print "success"
    

私のアプローチの何が問題になっていますか?時間とメモリのパフォーマンスに関して、私がやろうとしていることを達成するための最良の方法は何ですか?

4

2 に答える 2

7

このメモリ使用量は予想されます。Data.Map.Map約 6N ワードのメモリ + キーと値のサイズを消費します ( Johan Tibell によるこの優れた投稿から取得したデータ)。遅延 Text値は 7ワード+ 2*N バイト(マシン ワード サイズの倍数に丸められる) を使用し、aWord16 は 2 ワード(ヘッダー + ペイロード) を使用します。64 ビット マシンを想定しているため、ワード サイズは 8 バイトになります。また、入力の平均的な文字列の長さは 8 文字であると仮定します。

これらすべてを考慮に入れると、メモリ使用量の最終的な式は6*N + 7*N + 2*N + 2*N単語になります。

最悪の場合、すべての単語が異なり、約 2 個の単語が存在することになり(6 * 1024^3)/8 ~= 800 * 10^6ます。これを上記の式に代入すると、最悪の場合のマップ サイズは約 1 になります。102 GiBであり、実験結果と一致しているようです。この方程式を逆方向に解くと、ファイルには200*10^6さまざまな単語が含まれていることがわかります。

この問題に対する別のアプローチとして、トライ (コメントで J.Abrahamson によって提案されている) またはcount-min sketchなどの近似法を使用することを検討してください。

于 2013-11-05T08:34:32.303 に答える
0

従来のデータ処理の世界では、この問題は (必要に応じてディスクまたは磁気テープの外部で) 並べ替えを行い、並べ替えられたファイルをスキャンしてグループ化された一連の単語をカウントすることで解決されていました。もちろん、並べ替えの初期段階で部分的な削減を行って、スペースと時間を節約することもできます。

于 2013-11-13T06:07:29.263 に答える