10

我正在尝试处理一个非常大的 unicode 文本文件（6GB+）。我想要的是计算每个唯一单词的频率。当我遍历文件时，我使用严格Data.Map来跟踪每个单词的计数。该过程需要太多时间和太多内存（20GB+）。我怀疑地图很大，但我不确定它应该达到文件大小的 5 倍！代码如下所示。请注意，我尝试了以下方法：

  • 使用Data.HashMap.Strict而不是Data.Map.Strict. Data.Map似乎在较慢的内存消耗增长率方面表现更好。

  • ByteString使用惰性而不是惰性读取文件Text。然后我将其编码为 Text 进行一些处理，然后将其编码回ByteStringfor 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 占用两个字（标头 + 有效负载）。我们将假设一台 64 位机器，因此字长为 8 个字节。我们还将假设输入中的平均字符串长度为 8 个字符。

考虑到这一切，内存使用的最终公式是6*N + 7*N + 2*N + 2*N单词。

在最坏的情况下，所有的词都会不同，并且会有关于(6 * 1024^3)/8 ~= 800 * 10^6它们的。将其插入上面的公式中，我们得到最坏情况下的地图大小约为。102 GiB，这似乎与实验结果一致。反向求解这个方程告诉我们您的文件包含大约200*10^6不同的单词。

至于解决此问题的替代方法，请考虑使用 trie（如 J.Abrahamson 在评论中所建议的那样）或近似方法，例如count-min sketch。

于 2013-11-05T08:34:32.303 回答
0

在传统数据处理的世界中，这个问题可以通过排序（如果需要，可以在外部磁盘或磁带上）来完成，然后扫描排序的文件以计算组合在一起的单词运行次数。当然，您可以在排序的早期阶段进行一些部分缩减，以节省一些空间和时间。

于 2013-11-13T06:07:29.263 回答