首页 文章

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

提问于
浏览 次
47

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

问题：我希望能够将我的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倍？或者这可能是由我不知道的其他东西引起的？

Update: 将递归深度设置为3000并且看起来很有希望 .

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

python recursion tree pickle depth

5 回答

  • 4

    来自the docs：

    尝试挑选高度递归的数据结构可能超过最大递归深度，在这种情况下将引发RuntimeError . 您可以使用sys.setrecursionlimit（）小心地提高此限制 .

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

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

    除此之外，您可以尝试将树实现更改为"less recursive"（如果可能），或者编写内置数据持久性的 an additional implementation （在实现中使用pickles和shelves） . 希望有所帮助

    回复于
  • 9

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

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

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

    回复于
  • 3

    Stack size must also be increased with resource.setrlimit to prevent segfault

    如果仅使用 sys.setrecursionlimit ，如果达到Linux内核允许的最大堆栈大小，仍然可以进行段错误 .

    可以使用 resource.setrlimit 增加此值，如下所述：Setting stacksize in a python script

    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)

    另见：What is the maximum recursion depth in Python, and how to increase it?

    我的默认最大值是8Mb .

    在Ubuntu 16.10，Python 2.7.12上测试过 .

    回复于
  • 0

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

    您可以尝试进一步提高限额 . 平台依赖于最大硬盘，但尝试50000是合理的 .

    也尝试腌制你的trie的一个简单的小版本 . 如果泡菜死了，即使它只存储了几个三个字母的单词，那么你知道你的trie有一些根本问题，而不是泡菜 . 但是如果它只在你尝试存储10k字时发生，那么它可能是pickle中平台限制的错误 .

    回复于
  • 34

    我的需求有些直接，所以我通过以.txt格式保存字典来解决这个问题 . 唯一的事情是当你再次加载文件时，你必须将它转换回字典 .

    import json

# Saving the dictionary
with open('filename.txt', 'w') as file_handle:
    file_handle.write(str(dictionary))

# Importing the .txt file
with open('filename.txt', 'r') as file_handle:
    f = '"' + file_handle.read() + '"'

# From .txt file to dictionary
dictionary = eval(json.loads(f))

    如果这不起作用，您可以尝试使用json格式导出字典 .

    回复于

相关问题