gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 03:22:17 25 4
gpt4 key购买 nike

在我的 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 代码时使用更少的内存?或者以其他方式将此结构嵌入到可执行文件中?

最佳答案

也许您可以将 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中找到。 .

关于haskell - TemplateHaskell 编译时的内存使用情况,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32489464/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com