Как заставить haskell не хранить целую строку байтов?

Question

Я пишу небольшую (относительно) заявку на haskell в академических целях.Я реализую сжатие Хаффмана, основанное на этом коде http://www.haskell.org/haskellwiki/Toy_compression_implementations.

Мой вариант этого кода здесь https://github.com/kravitz/har/blob/a5d221f227c27fd1c5587217a29a169a377521a6/huffman.hs, и он использует ленивые строки байтов.Когда я реализовал сжатие RLE, все было гладко, потому что он обрабатывал входной поток за один шаг.Но Хаффман обрабатывает его дважды, и в результате у меня в памяти сохраняется оценочная строка тестирования, что плохо для больших файлов (но для относительно небольших файлов она также выделяет слишком много места в куче).Это не только мое подозрение, потому что профилирование также показывает, что большая часть кучи съедается путем распределения строк.

Также я сериализую длину потока в файле, и это также может вызвать полную загрузку тестовой строки в памяти.Есть ли какой-нибудь простой способ сказать, что GHC будет любезен и пересмотреть поток несколько раз?

Answer 1

Вместо передачи строки байтов в кодировщик, вы можете передать что-то, что вычисляет строку байтов, а затем явно пересчитывать значение каждый раз, когда вам это нужно.

compress :: ST s ByteString -> ST s ByteString
compress makeInput = do
  len      <- (return $!) . ByteString.length =<< makeInput
  codebook <- (return $!) . makeCodebook      =<< makeInput
  return . encode len codebook                =<< makeInput

compressIO :: IO ByteString -> IO ByteString
compressIO m = stToIO (compress (unsafeIOToST m))

Параметр compress должен фактически вычислятьсяЗначение.Простое перенос значения на return не сработает.Кроме того, каждый вызов makeInput должен действительно оценивать свой результат, в противном случае при повторном вычислении ввода в памяти останется ленивая, не оцененная копия ввода.

Обычный подход, как сказал barsoap, это просто сжимать один блок за раз.

Answer 2

Обычный подход при сжатии (Хаффманна), когда невозможно обрабатывать входные данные дважды, один раз для сбора распределения вероятностей и один раз для фактического сжатия, состоит в том, чтобы разделить входные данные на блоки и сжатькаждый в отдельности.Хотя он все еще ест память, он только ест, максимально, постоянное количество.

Тем не менее, вы можете захотеть взглянуть на bytestring-mmap , хотя это не будет работать сстандартный ввод, сокеты и другие файловые дескрипторы, которые не поддерживаются файловой системой, которая поддерживает mmap.

Вы также можете перечитать байтовую строку из файла (опять же, при условии, что вы не получаете его от чего-либокак в трубе) после сбора распределения вероятностей, но это все равно заставит ваш код выручить, скажем, файлы размером 1 ТБ.