Рекурсивная итерация python, превышающая предел для реализации дерева
Я динамически реализую дерево в python. Я определил класс, как показано ниже.
class nodeobject(): def __init__(self,presentnode=None,parent=None): self.currentNode = presentnode self.parentNode = parent self.childs = [] У меня есть функция, которая получает возможные дочерние элементы для каждого узла из пула
- Python: sys.excepthook и регистрация неперехваченных исключений через несколько модулей
- Сделать окно tkinter поверх всех остальных окон
- глобальный фрейм и стек
def findchildren(node, childs):` `# No need to write the whole function on how it gets childs
Теперь у меня есть рекурсивная функция, которая начинается с головного узла (без родителя) и рекурсивно перемещается по цепочке для каждого узла (базовый случай – последний узел, не имеющий детей)
def tree(dad,children): for child in children: childobject = nodeobject(child,dad) dad.childs.append(childobject) newchilds = findchildren(child, children) if len(newchilds) == 0: lastchild = nodeobject(newchilds,childobject) childobject.childs.append(lastchild) loopchild = copy.deepcopy(lastchild) while loopchild.parentNode != None: print "last child" result.append(loopchild.currentNode) # result global to store values loopchild = copy.deepcopy(loopchild.parentNode) else: tree(childobject,newchilds)
Деревообразование работает только для определенного количества входов. Как только пул становится больше, он приводит к тому, что «MAXIMUM REURSION DEPTH EXCEEDED»
Я попытался установить предел рекурсии с помощью set.recursionlimit (), и он не работает. Программа вылетает из строя. Я хочу реализовать стек для рекурсии, может кто-то помочь, я не пошел туда, где даже после длительного использования? Кроме того, есть ли другой способ исправить это, кроме стека?
2 Solutions collect form web for “Рекурсивная итерация python, превышающая предел для реализации дерева”
Когда вы пытаетесь изменить глубину рекурсии, ваша программа, вероятно, сработает, потому что вы превысили ограничение жесткой рекурсии, наложенное размером стека в вашей системе. Установка sys.recursionlimit () только делает Python менее строгим в отношении глубины, но это не влияет на то, что ваша платформа действительно будет поддерживать.
У Python есть довольно наивная реализация для рекурсии, что означает, что это полезно только тогда, когда вы можете гарантировать, что глубина рекурсии будет довольно низкой. Сначала проверьте, что ваше дерево действительно достаточно глубокое, чтобы взорвать стек; если в некоторых узлах есть дети, которые также являются их родителями / предками, этот код будет работать навсегда, пока он не исчерпает стек. Один из способов проверки – отслеживать все узлы, возвращаемые findchildren() и не повторять их.
Если ваши данные верны, и стек действительно недостаточно глубокий, вам придется перевести код в итеративную версию и вручную создать собственный стек. Вот ваш код с явным стеком (я не тестировал это, поэтому могут быть ошибки, но он должен дать вам представление о том, как это сделать):
def tree(dad, children): stack = [(dad, children)] while stack: dad, children = stack.pop() for index, child in enumerate(children): childobject = nodeobject(child,dad) dad.childs.append(childobject) newchilds = findchildren(child, children) if len(newchilds) == 0: lastchild = nodeobject(newchilds,childobject) childobject.childs.append(lastchild) loopchild = copy.deepcopy(lastchild) while loopchild.parentNode != None: print "last child" result.append(loopchild.currentNode) # result global to store values loopchild = copy.deepcopy(loopchild.parentNode) else: stack.append((dad, children[index:])) stack.append((childobject,newchilds)) break
Одна важная особенность, которую следует отметить, заключается в том, что мы должны нажимать дочерние элементы, которые еще не были обработаны в цикле for, обратно в стек, прежде чем мы нажимаем новые дочерние узлы.
@Peter Gibson делает хороший вывод о том, что вы, вероятно, не хотите делать глубокие копии своих узлов, но это не должно приводить к взрыву вашего стека (просто используйте много и много памяти без какой-либо выгоды, которую я вижу).
Я бы сказал, что этот блок кода является проблемой:
loopchild = copy.deepcopy(lastchild) while loopchild.parentNode != None: print "last child" result.append(loopchild.currentNode) # result global to store values loopchild = copy.deepcopy(loopchild.parentNode)
Вы проходите дерево до тех пор, пока не попадете на лист (ребенок без детей), а затем вы deepcopy каждого узла до начала.
deepcopy делает копию nodeobject вместе с копиями его parentNode и каждого дочернего childs . Это означает, что каждая deepcopy копия nodeobject является копией всего дерева вместе со всеми вашими данными !
Рассмотрим простое дерево, которое имеет 4 уровня глубины, например
A BC DEFG HIJKLMNO
Когда он deepcopy к первому листу H , он делает deepcopy узлов H , D , B и A – каждая из них является копией всего дерева и всех ваших данных. Таким образом, вы получаете 32 экземпляра для этой довольно простой структуры! Я вижу, как это быстро выходит из-под контроля.
Есть ли причина, по которой вы делаете копии каждого узла? Попробуйте заменить этот код на
loopchild = lastchild while loopchild.parentNode != None: print "last child" result.append(loopchild.currentNode) # result global to store values loopchild = loopchild.parentNode