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