使用Pickle/cPickle命中最大递归深度

Question

背景:我正在使用最小构造算法构建一个代表字典的trie.输入列表是4.3M utf-8字符串,按字典顺序排序.生成的图形是非循环的,最大深度为638个节点.我的脚本的第一行将递归限制设置为1100 sys.setrecursionlimit().

问题:我希望能够将我的trie序列化到磁盘,因此我可以将其加载到内存中而无需从头开始重建(大约22分钟).我曾经尝试都pickle.dump()和cPickle.dump(),用文本和二进制协议两种.每次,我得到一个如下所示的堆栈跟踪:

  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 649, in save_dict
    self._batch_setitems(obj.iteritems())
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 663, in _batch_setitems
    save(v)
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 286, in save
    f(self, obj) # Call unbound method with explicit self
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 725, in save_inst
    save(stuff)
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 286, in save
    f(self, obj) # Call unbound method with explicit self
  File "/System/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/pickle.py", line 648, in save_dict
    self.memoize(obj)
RuntimeError: maximum recursion depth exceeded

我的数据结构相对简单: trie包含对开始状态的引用,并定义了一些方法. dfa_state包含布尔字段,字符串字段和从标签到状态的字典映射.

我对内部工作原理并不十分熟悉pickle- 我的最大递归深度是否需要大于/等于某些n的trie深度的n倍？或者这可能是由我不知道的其他东西引起的？

更新: 将递归深度设置为3000没有帮助,因此这种途径看起来并不乐观.

更新2: 你们是对的; 由于默认的递归限制,我认为pickle会使用一个小的嵌套深度,因此我是短视的.10,000诀窍.

Answer 1

来自文档:

尝试挑选高度递归的数据结构可能会超过最大递归深度,在这种情况下会引发RuntimeError.你可以小心地提高这个限制sys.setrecursionlimit().

尽管您的trie实现可能很简单,但它使用递归,并且在转换为持久数据结构时可能会导致问题.

我的建议是继续提高递归限制,以查看您正在使用的数据是否存在上限以及您正在使用的trie实现.

除此之外,如果可能的话,您可以尝试将树实现更改为"更少递归",或者编写内置数据持久性的其他实现(在实现中使用pickles和shelf).希望有所帮助

Answer 2

Pickle确实需要递归地走你的特里.如果Pickle仅使用5级函数调用来完成工作,则深度638的trie将需要设置为超过3000的级别.

尝试一个更大的数字,递归限制实际上只是为了保护用户不必等待太长时间,如果递归落入一个无限的洞.

Pickle处理循环没问题,所以即使你的trie在那里有一个循环也没关系

Answer 3

还必须增加堆栈大小resource.setrlimit以防止段错误

如果您只使用sys.setrecursionlimit，如果达到 Linux 内核允许的最大堆栈大小，您仍然可以出现段错误。

这个值可以增加，resource.setrlimit正如在：在 python 脚本中设置堆栈大小

import pickle
import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()

max_rec = 0x100000

# May segfault without this line. 0x100 is a guess at the size of each stack frame.
resource.setrlimit(resource.RLIMIT_STACK, [0x100 * max_rec, resource.RLIM_INFINITY])
sys.setrecursionlimit(max_rec)

a = []
# 0x10 is to account for subfunctions called inside `pickle`.
for i in xrange(max_rec / 0x10):
    a = [a]
print pickle.dumps(a, -1)

另请参阅：Python 中的最大递归深度是多少，以及如何增加它？

我的默认最大值是 8Mb。

在 Ubuntu 16.10、Python 2.7.12 上测试。

Answer 4

仔细检查您的结构是否确实是非循环的。

您可以尝试进一步提高限制。有一个取决于平台的硬性最大值，但尝试 50000 是合理的。

还可以尝试对 trie 的一个非常小的版本进行腌制。如果 pickle 死掉了，即使它只存储了几个三个字母的单词，那么你就知道你的 trie 存在一些根本问题，而不是 pickle 。但如果它仅在您尝试存储 10k 个单词时发生，那么可能是 pickle 中的平台限制造成的。