Достижение максимальной глубины рекурсии с использованием 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: Вы, ребята, были правы; Я был близоруким, полагая, что рассол будет использовать небольшую глубину вложенности из-за ограничений рекурсии по умолчанию. 10 000 сделали трюк.

Answer 1

От the docs:

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Рассол обрабатывает циклы ОК, так что это не имеет значения, даже если ваш Trie был цикл в там

Answer 4

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

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

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.