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

Question

在第一次看到 Haskell 四年后再次回到它。我总是对它的表现力感到惊讶，并对我无法预测空间/时间表现感到困惑。

作为热身，我开始翻译我用 C++ 编写的一个小玩具程序。这是关于拼字游戏中的“作弊”。你输入你的游戏，它会输出你可能玩的单词，单独使用你的字母或在板上划一个字母。

整个事情都围绕着启动时预加载的字典展开。然后，这些单词及其字谜词将作为列表存储在 map 中。键是排序字母的字符串。一个例子会说得更清楚:

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

C++ 版本一次读取字典约 320000 个单词，总共大约需要 200 毫秒。生成的数据结构是存储在 array<99991, vector<string>> 中的 HashMap ，占用约 12 MB 内存。

Haskell 版本在大约 5 秒内读取相同的字典，并且程序堆大小激增至 400 MB!我将 Data.Map 中的值类型从 [String] 更改为 [ByteString] 以节省一些内存，这使程序内存消耗降至大约 290 MB。这仍然是我的 C++ 版本的 24 倍。尽管 Data.Map 是一棵树而不是一个数组，但这不仅仅是“开销”。

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

整个模块在此处可见:(已弃用的链接)

我想我的问题与 Data.Map 增量构建的方式有关，在其自身的先前版本上增长？还是数据结构本身？还是其他什么？

我会尝试其他解决方案，例如 Data.HashMap ，或用 Data.Map 填充 fromListWith 。尽管如此，我还是想对这里发生的事情有一些了解。非常感谢您的见解!

<小时/>

简短回答:

使用 Data.Map.Strict，强制评估值元素，并将键存储为 ByteString，也创造了将内存占用量除以 3 的奇迹。结果是 100Meg，仅比标准 std::multimap<std::string, std::string> 大两倍对于相同的数据集，用 C++ 编写。虽然没有加速。 Git 已更新。

非常感谢所有贡献者，这里有有趣的 Material !

Answer 1

您所犯的一个错误尚未被指出，那就是您将 B.pack word 形式的未评估的 thunk 存储在作为 Map 中的值的列表中。这意味着在构建 Map 期间，您基本上以低效的字符串格式保留整个输入文件，而输入文件中每个字符占用 24 个字节。使用 Data.Map.Strict API 在这里没有什么区别，因为该 API 中的函数仅强制 Map 的元素为弱头范式，这对于列表意味着仅评估最外层构造函数是否是 [] 或 (:)，并且不评估列表的任何元素。

您可以进行的另一项改进是使用 ShortByteString最新版本的 bytestring 中提供了这种类型(GHC 7.8 附带的版本已经足够新了)。这是专门为在存储许多短字节串时最大限度地减少内存使用而设计的，其代价是 ShortByteString 上的大多数操作都需要一个副本。

András Ková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% 以上的空间使用量。