python - 概率解析器的内存使用

Question

我正在为范围串联语法编写 CKY 解析器。我想用一个树库作为文法，所以文法会很大。我写了一个原型(prototype) 1在 Python 中，当我模拟一个包含几十个句子的树库时，它似乎运行良好，但内存使用量是 Not Acceptable 。我尝试用 C++ 编写它，但到目前为止，这一直非常令人沮丧，因为我以前从未使用过 C++。这是一些数据(n 是语法所基于的句子数):

n    mem
9    173M
18   486M
36   836M

这种增长模式是最佳优先算法所期望的，但开销的数量是我关心的。根据 heapy 的内存使用量比这些数字小十倍，valgrind 报告了类似的东西。是什么导致了这种差异，我可以在 Python(或 Cython)中做些什么？也许是由于碎片化？或者可能是 python 字典的开销？

一些背景:两个重要的数据结构是将边映射到概率的议程，以及将非终结符和位置映射到边的字典图表。议程是用一个 heapdict(它在内部使用一个字典和一个 heapq 列表)实现的，图表用一个字典映射非终结符和位置到边缘。议程经常被插入和删除，图表只得到插入和查找。我用这样的元组表示边:

(("S", 111), ("NP", 010), ("VP", 100, 001))

字符串是语法中的非终结符标签，位置被编码为位掩码。当成分不连续时，可以有多个位置。所以这条边可以代表对“玛丽快乐吗”的分析，其中"is"和“快乐”都属于副总裁。图表字典由这条边的第一个元素索引，(“S”，111)在这个案例。在新版本中，我尝试转置此表示，希望它能因重用而节省内存:

(("S", "NP", "VP), (111, 100, 011))

我认为如果第一部分与不同的位置组合出现，Python 只会存储一次，尽管我不确定这是真的。在任何一种情况下，它似乎都没有任何区别。

所以基本上我想知道的是，是否值得继续我的 Python 实现，包括使用 Cython 和不同的数据结构，或者用 C++ 从头开始​​编写它是唯一可行的选择。

更新:经过一些改进后，我不再有内存使用问题。我正在开发优化的 Cython 版本。我会将赏金奖励给提高代码效率的最有用的建议。在 http://student.science.uva.nl/~acranenb/plcfrs_cython.html 有一个带注释的版本

1 https://github.com/andreasvc/disco-dop/-- 运行 test.py 来解析一些句子。需要 python 2.6，nltk和 heapdict

Answer 1

I figured that Python would store the first part only once if it would occur in combination with different positions

不一定:

>>> ("S", "NP", "VP") is ("S", "NP", "VP")
False

您可能想要 intern所有引用非终端的字符串，因为您似乎在 rcgrules.py 中创建了很多这些。如果你想intern一个元组，那么先把它变成一个字符串:

>>> intern("S NP VP") is intern(' '.join('S', 'NP', 'VP'))
True

否则，您将不得不“复制”元组而不是重新构造它们。

(如果您是 C++ 的新手，那么在其中重写这样的算法不太可能提供很大的内存优势。您必须首先评估各种哈希表实现并了解其容器中的复制行为。我发现 boost::unordered_map 有很多小的哈希表非常浪费。)