非常に大きなテキストファイルをレイジーテキストとバイトストリングで処理する

Question

非常に大きなユニコードテキストファイル（6GB +）を処理しようとしています。私が望むのは、それぞれのユニークな単語の頻度を数えることです。私は厳密なData.Mapを使用して、ファイルを横断するごとに各単語の数を記録します。 処理に時間がかかり過ぎ、メモリー（20GB以上）が多すぎます。私はマップが巨大だと思うが、私はそれがファイルのサイズの5倍に達するはずがわからない！ コードを以下に示します。

• Data.HashMap.Strictの代わりData.Map.Strictを使用して：私は次のことを試してみましたのでご注意ください。 Data.Mapは、メモリ消費の増加速度が遅いという点でより優れているようです。

• lazy Textの代わりにlazy ByteStringを使用してファイルを読み込みます。そして、それをテキストにエンコードして何らかの処理を行い、次にのByteStringにエンコードします。私のアプローチと間違って何

  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" 
  

？時間とメモリのパフォーマンスに関して私がしようとしていることを達成する最良の方法は何ですか？

Answer 1

このメモリの使用が想定されています。 Data.Map.Mapは約6Nワードのメモリ+キーのサイズ&の値（データはthis excellent post by Johan Tibellから取得）を消費します。 怠惰Text値takes up 7 words + 2*N bytes（マシンのワードサイズの倍数に丸められた）とWord16takes up two words（ヘッダー+ペイロード）です。私たちは64ビットマシンを想定しているので、ワードサイズは8バイトになります。また、入力の平均文字列は8文字と仮定します。

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

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

この問題の代替方法としては、トライ（コメントでJ.Abrahamsonの示唆）または近似方法（count-min sketchなど）の使用を検討してください。

Answer 2

従来のデータ処理の世界では、この問題はソート（必要に応じてディスクやマグネットの外部で）し、ソートされたファイルをスキャンしてグループ化された単語の数をカウントしていました。もちろん、ソートの初期段階では、スペースと時間を節約するために、部分的な削減を行うことができます。