Python: травление высокорекурсивных объектов без использования `setrecursionlimit`

Ответ 1

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

Если бы я был вами, я бы не использовал здесь открыто рекурсивную структуру данных. Вместо этого я буду указывать каждый node и использовать таблицу ссылок, которая эффективно переводит число в node с этим номером. Каждый node будет ссылаться на другие узлы (например, его дочерние элементы) через эту таблицу, используя числа. Простое свойство сделало бы это синтаксически простым. Помимо этих свойств, код, связанный с обходом дерева, не изменится. Конструктор node должен будет выделить число и поместить себя в таблицу ссылок, что тоже тривиально.

Таблица ссылок может быть просто списком узлов, где индекс в списке служит номером node; Кажется, что списки Python имеют эффективный доступ по индексу. Если скорость вставки важна, я бы выделил достаточно длинный список, заполненный None; это не займет слишком много места. Если узлы сохранили свои собственные номера, эта структура была бы недорогой в обоих направлениях.

Как вы видите, травление и раскалывание такого дерева было бы тривиально на любой глубине.

Ответ 2

Чтобы упростить понимание, здесь приведен полный пример с единственной ссылкой, чтобы упростить его:

class Node(object):
  linker = [] # one list for all Node instances
  def __init__(self, payload):
    self.payload = payload
    self.__next = None
    self.__index = len(self.linker)
    self.linker.append(self)
  #
  def getNext(self):
    if self.__next is not None:
      return self.linker[self.__next]
  #
  def setNext(self, another):
    if another is not None:
      self.__next = another.__index
    else:
      self.__next = None
  #
  next = property(getNext, setNext)
  #
  def __str__(self):
    return repr(self.payload)


a = Node("One")
b = Node("Two")
c = Node("Three")

b.next = c
a.next = b

# prints "One" "Two" "Three"
print a, a.next, a.next.next

Также обратите внимание, что эта структура может легко содержать циклы и по-прежнему сериализоваться.

Ответ 3

Просто не используйте рекурсию. Создайте стек (список/очередь) с открытыми узлами и обработайте это.

Что-то вроде этого (псевдокод)

stack.add(root)
while not list.empty:
    current = stack.pop
    // process current
    for each child of current:
        stack.add(child)

Это должно сделать это

Ответ 4

Я думаю, что хорошим решением является сочетание Mene и 9000 ответов. Учитывая, что узлы имеют глобально уникальные идентификаторы (возможно, каким-то образом адреса памяти могут использоваться как таковые), вы можете это сделать. Конечно, это небрежная псевдо-реализация, но с небольшим количеством абстракции, если она инкапсулирована в древовидный класс, это может быть очень просто.

def all_nodes(node): # walk the tree and get return all nodes as a list
    if node:
        nodes = []
        for child in node.children:
            for sub_child in all_nodes(child):
                nodes.append(sub_child)
        return nodes
    return []


class Node(object):
    def __init__(self, children, id):
        self.children = children
        self.id = id

    def __getstate__(self): #when pickling translate children into IDs
        tmp = self.__dict__.copy()
        children_ids = []
        for child in tmp['children']:
            children_ids.append(child.id)
        tmp['children_ids'] = children_ids
        return tmp


lookup = dict()


for node in all_nodes(rootNode): # put all nodes into a dictionary
    lookup[node.id] = node
#then pickle the dictionary
#then you can unpickle it and walk the dictionary
for id, node in lookup:
    del node.children
    node.children = []
    for child in node.children_ids:
        node.children.append(lookup[child])
#and three should now be rebuilt