Максимальная глубина рекурсии при использовании Pickle / cPickle

Question

Фон: я строю три для представления словаря, используя минимальный алгоритм построения. Список ввода представляет собой строки 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 раз глубины дерева для некоторого n? Или это может быть вызвано чем-то еще, о чем я не знаю?

Обновление: Установка глубины рекурсии на 3000 не помогла, поэтому этот проспект не выглядит многообещающим.

Обновление 2: Вы, ребята, были правы; Я был близорук в предположении, что рассол будет использовать небольшую глубину вложения из-за ограничений рекурсии по умолчанию. 10000 сделали свое дело.

Answer 1

С документы :

Попытка выбрать высокорекурсивную структуру данных может превысить максимальную глубину рекурсии, в этом случае будет вызвано RuntimeError. Вы можете осторожно поднять этот лимит с помощью sys.setrecursionlimit().

Хотя ваша временная реализация может быть простой, она использует рекурсию и может привести к проблемам при преобразовании в постоянную структуру данных.

Я бы порекомендовал продолжить повышение предела рекурсии, чтобы увидеть, существует ли верхняя граница для данных, с которыми вы работаете, и используемой вами реализации.

Кроме того, вы можете попытаться изменить реализацию дерева на «менее рекурсивную», если это возможно, или написать дополнительную реализацию , которая имеет встроенную постоянство данных (используйте pickles и полки в вашей реализации). Надеюсь, что это поможет

Answer 2

Рассол должен рекурсивно пройтись по вашему дереву. Если Pickle использует только 5 уровней вызовов функций для выполнения работы, то для вашей глубины 638 потребуется уровень, превышающий 3000.

Попробуйте гораздо большее число, предел рекурсии действительно только для того, чтобы защитить пользователей от необходимости ждать слишком долго, если рекурсия падает в бесконечную дыру.

Pickle хорошо обрабатывает циклы, так что это не имеет значения, даже если у вашего дерева есть цикл там

Answer 3

Размер стека также должен быть увеличен с помощью resource.setrlimit, чтобы предотвратить ошибку segfault

Если вы используете только sys.setrecursionlimit, вы все равно можете использовать segfault, если достигнете максимального размера стека, разрешенного ядром 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 и как ее увеличить?

Максимальное значение по умолчанию для меня - 8 МБ.

Протестировано на Ubuntu 16.10, Python 2.7.12.

Answer 4

Дважды проверьте, что ваша структура действительно ациклична.

Вы можете попытаться увеличить лимит еще дальше. Существует жесткий максимум, зависящий от платформы, но попытка 50000 была бы разумной.

Кроме того, попробуйте выбрать небольшую версию вашего проекта. Если рассол умирает, хотя он хранит только пару трехбуквенных слов, то вы знаете, что есть какая-то фундаментальная проблема с вашим деревом, а не рассол. Но если это происходит только тогда, когда вы пытаетесь сохранить 10 тыс. Слов, то это может быть связано с ограничением платформы в рассоле.

Answer 5

Мои потребности были несколько немедленными, поэтому я решил эту проблему, сохранив свой словарь в формате .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.