Обработка очень большого текстового файла с ленивыми текстами и байтами

Я пытаюсь обработать очень большой текстовый файл в формате Юникод (6 ГБ +). Я хочу рассчитать частоту каждого уникального слова. Я использую строгий Data.Map для отслеживания отсчетов каждого слова, когда я пересекаю файл. Процесс занимает слишком много времени и слишком много памяти (20 ГБ +). Я подозреваю, что карта огромна, но я не уверен, что она должна достигать 5-кратного размера файла! Код показан ниже. Обратите внимание, что я попробовал следующее:

• Использование Data.HashMap.Strict вместо Data.Map.Strict. Data.Map, кажется, работает лучше с точки зрения более медленного увеличения потребления памяти.

• Чтение файлов с помощью ленивого ByteString вместо ленивого Text. И затем я закодирую его в Text, сделав некоторую обработку, а затем верните его обратно в ByteString для 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"
  

Что не так с моим подходом? Какой лучший способ выполнить то, что я пытаюсь сделать с точки зрения времени и производительности памяти?

Ответы

Ответ 1

Ожидается использование этой памяти. Data.Map.Map потребляет около 6N слов памяти + размер ключей и значений (данные взяты из этот отличный пост Johan Tibell). Значение lazy Text занимает 7 слов + 2 * N байтов (округлено до кратного машинного слова размер), a Word16 занимает два слова (заголовок + полезная нагрузка). Будем считать 64-битную машину, поэтому размер слова будет 8 байтов. Мы также предположим, что средняя строка на входе составляет 8 символов.

Учитывая все это, окончательной формулой для использования памяти является 6*N + 7*N + 2*N + 2*N words.

В худшем случае все слова будут разными, и из них будет (6 * 1024^3)/8 ~= 800 * 10^6. При подключении в формулу выше мы получаем наихудший размер карты ок. 102 GiB, что, по-видимому, согласуется с экспериментальными результатами. Решение этого уравнения в обратном направлении говорит нам, что ваш файл содержит около 200*10^6 разных слов.

Что касается альтернативных подходов к этой проблеме, рассмотрите использование trie (как было предложено Дж. Абрахамсоном в комментариях) или приблизительный метод, например count- минимальный эскиз.

Ответ 2

В мире традиционной обработки данных эта проблема была бы решена путем сортировки (извне на диске или магнитной ленте, если это необходимо), а затем сканирования отсортированного файла для подсчета сгруппированных прогонов слов. Конечно, вы могли бы сделать частичное сокращение на ранних этапах сортировки, чтобы сохранить некоторое пространство и время.