optimization - 如何强制 haskell 不存储整个字节串？

Question

我出于学术目的在 haskell 上编写了一个(相对)小的应用程序。我正在基于此代码实现霍夫曼压缩 http://www.haskell.org/haskellwiki/Toy_compression_implementations .

此代码的变体在这里 https://github.com/kravitz/har/blob/a5d221f227c27fd1c5587217a29a169a377521a6/huffman.hs它使用惰性字节串。当我实现 RLE 压缩时，一切都很顺利，因为它一步处理输入流。但是霍夫曼处理了两次，结果我在内存中存储了一个评估的字节串，这对大文件来说是不好的(但对于相对较小的文件，它也在堆中分配了太多空间)。这不仅是我的怀疑，因为分析还显示大部分堆被 bytestring 分配占用。

另外，我在文件中序列化了一个流长度，它也可能导致在内存中加载完整的字节串。有什么简单的方法可以说 ghc be kindly 并多次重新评估流吗？

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 所说，通常的方法是一次只压缩一个 block 。