haskell - TemplateHaskell 编译时的内存使用情况

Question

在我的 Haskell 项目之一的 RuzzSolver 中使用 TemplateHaskell 时，我遇到了内存消耗问题。 Sources of RuzzSolver are available on GitHub .

为了获得良好的性能，我将约 380000 个单词的字典加载到 Tree 结构中(来自容器包)。这大大加快了网格的求解速度，但加载本身需要一些时间(1 到 2 秒之间，具体取决于 CPU)。

我想在编译时使用 TemplateHaskell 直接创建结构。

因此我改造了字典加载:

-- Dictionary.hs, line 155
getDictionary :: String -> IO Dictionary
getDictionary dictionaryFilePath = do
    content <- readFile dictionaryFilePath
    return $ foldl (+++) [] (createTree <$> lines content)

进入这个函数:

-- Dictionary.hs, line 164
getDictionaryQ :: String -> Q Exp
getDictionaryQ dictionaryFilePath = do
    content <- runIO $ readFile dictionaryFilePath
    lift $ foldl (+++) [] (createTree <$> lines content)

view Dictionary.hs

它让我可以从:

-- ruzzSolver.hs, line 68
dictionary <- getDictionary "dictionary/ruzzdictionary.txt"

到:

-- ruzzSolver.hs, line 68
let dictionary = $(getDictionaryQ "dictionary/ruzzdictionary.txt")

view ruzzSolver.hs

它(应该)可以工作，但是编译需要太多内存!在我的 8 Gb PC 上，当 GHC 达到 12 GB 的消耗量时，我不得不停止它。将词典减少到 38000 个单词可以编译，但它仍然需要 3 到 4 GB。

有没有办法让 GHC 在编译这段 TemplateHaskell 代码时使用更少的内存？或者以其他方式将此结构嵌入到可执行文件中？

Answer 1

也许您可以将 trie 树“嵌入”到可执行文件中以节省加载和创建时间，但我预见到的一个问题是，与其他语言的数据结构相比，传统的 Haskell 数据结构非常臃肿。

此外，大多数容器都允许插入和删除，但看起来您的数据是常量，因此您只需要最终的数据结构。此外，您只会将它用于以下查询:

• 字典里有这个词吗？
• 而且，这个字符串是字典中某个单词的前缀吗？

你想要一个紧凑的字典表示，带有某种预先计算的索引来加快查找速度。

一些选项:

Option 1: Create a BerkeleyDB database.

这样的数据库允许大于和小于查询。

优点:没有数据库加载时间。

缺点:查询需要磁盘访问。虽然，一旦页面被操作系统读取，它们应该被缓存并且后续读取应该很快。

注意 - 我已经使用 Berkeley DB 在 perl 中编写了一个 boggle 求解器，因此这种方法非常可行。

与 BerkeleyDB 类似的是 CDB(常量数据库)，它也有一个 Haskell 包。但是，CDB 仅支持相等查询，因此它可能不适用于您的应用程序。

Option 2. Represent the dictionary simply as the sorted file of the words. Create a custom index to make queries efficient.

一个简单的索引可以是一个 26*26*26 的元素数组，指示每个三字母前缀在文件中的偏移量。这么小的索引就可以编进程序了。将字典加载为单个(严格的)ByteString。

在字节串中使用索引和二进制搜索来解决查询。 也许 ByteString 函数在这里会很好地工作，但作为最后的手段，您始终可以使用 Int 偏移量到加载的字典中作为“指针”，您可以四处移动以找到下一个单词的开头。

您可能能够将字典 ByteString 编译成可执行文件，但加载 4 MB 的数据应该不会花费太长时间 - 特别是如果它已经在操作系统缓存中。

更新:第二个想法的例子可以在here中找到。 .