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

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

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

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

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

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

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

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

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

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

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

Это должно сработать

Я думаю, что хорошее решение - это комбинация ответов Мене и 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