如何以空间和时间有效的方式填充Data.Map

Question

在第一次看到它之后四年回到Haskell.我总是对表现力感到惊讶,并且因为我无法预测空间/时间表现而感到困惑.

作为一个热身,我开始翻译我用C++编写的一个小玩具程序.这是关于Scrabble的"作弊".您输入您的游戏,它会输出您可能会玩的单词,单独使用您的信件或通过在董事会上交叉信件.

整个事情围绕着一个在启动时预加载的字典.然后将这些单词与其字谜一起存储为地图中的列表.键是排序字母的字符串.一个例子会说得更清楚:

Key : "AEHPS"  Value : ["HEAPS","PHASE","SHAPE"]

C++版本一次一个地读取字典的~320000个单词,总共大约200ms.生成的数据结构是存储在a中的哈希映射array<99991, vector<string>>,占用大约12兆字节的内存.

Haskell版本在大约5秒内读取相同的字典,程序堆大小膨胀到400兆字节!我在改变的值类型Data.Map从[String]以[ByteString]节省一些内存,并带来了程序内存消耗下降到大约290兆字节.这仍然是我的C++版本的24倍.这不仅仅是"开销",即使Data.Map是树而不是数组.

所以我认为我做错了什么.

整个模块在这里可见:(不建议使用的链接)

我想我的麻烦与Data.Map逐步建立的方式有关,在以前的版本中增长？或者与数据结构本身？或者是其他东西 ？

我会尝试其他的解决方案,如Data.HashMap,或填补了Data.Map用fromListWith.不过,我想对这里发生的事情有所了解.非常感谢任何见解!

---

简短回答:

使用Data.Map.Strict,强制评估值元素,并将键存储为ByteStrings也使得将内存占用量分成近3的奇迹.结果是100Meg,这只是std::multimap<std::string, std::string>C++ 标准的两倍.相同的数据集.虽然没有加速.Git已更新.

非常感谢所有贡献者,这里有一些有趣的内容!

Answer 1

您尚未指出的一个错误是您将表单B.pack word中未评估的thunk存储在Map中的值中.这意味着在构建Map期间,您将以低效的String格式保留整个输入文件,输入文件中每个字符的成本为24字节.使用Data.Map.StrictAPI在这里没有区别,因为该API中的函数仅强制Map的元素为弱头正常形式,对于列表而言,这意味着仅评估最外层构造函数是否,[]或者(:)不评估列表的任何元素.

你可以做的另一个改进是使用ShortByteString最近版本的bytestring中可用的类型(GHC 7.8附带的类型是足够新的).这是专门为存储许多短字节串时最小化内存使用而设计的,权衡是a上的大多数操作ShortByteString都需要副本.

AndrásKovács的Map示例代码看起来像这样:

{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Data.List
import qualified Data.Map.Strict as M
import qualified Data.ByteString.Char8 as B
import qualified Data.ByteString.Short as B (ShortByteString, toShort, fromShort)

shortPack = B.toShort . B.pack

main = do
  words <- lines <$> readFile "dict.txt"
  print $ M.size $
    M.fromListWith (++) $ map (\w -> let !x = shortPack w in (shortPack $ sort w, [x])) words

这些更改中的每一项都可以节省我测试中最大驻留时间的30%,总节省50%以上的空间.

Answer 2

编辑:删除错误的基准和评论,只留下一点建议.请参阅Reid Barton关于直接解决OP问题的答案.

如果您不需要在运行时更改字典,那么DAWG-s几乎是您可以获得的最具时空效率的解决方案(至少对于文字游戏而言).

例如,我们可以从您的字典中生成并序列化DAWG,它只占用295 Kb空间,并支持非常有效的查找和前缀匹配:

import qualified Data.DAWG.Packed as D -- from my "packed-dawg" package

main = do
  words <- lines <$> readFile "dict.txt"
  D.toFile "dict.dawg" $ D.fromList words -- serialize as "dict.dawg"