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

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

10 голосов
/ 26 мая 2010

Я получаю RuntimeError: maximum recursion depth exceeded при попытке засечь высокорекурсивный объект дерева. Очень похоже на этот вопрос здесь .

Он решил свою проблему, установив предел рекурсии выше с sys.setrecursionlimit. Но я не хочу этого делать: я думаю, что это скорее обходной путь, чем решение. Потому что я хочу иметь возможность мариновать мои деревья, даже если в них 10 000 узлов. (В настоящее время он терпит неудачу на уровне около 200.)

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

Есть ли способ решить это на фундаментальном уровне? Если бы только модуль pickle обрабатывал цикл вместо рекурсии, у меня не было бы этой проблемы. Может быть, у кого-то есть идея, как я могу сделать что-то подобное, не переписывая модуль pickle?

Будут оценены любые другие идеи, как я могу решить эту проблему.

Ответы [ 4 ]

2 голосов
/ 16 июня 2010

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

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

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

2 голосов
/ 05 июня 2010

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

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

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

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

1 голос
/ 28 августа 2010

Я думаю, что хорошее решение - это сочетание ответов Мене и 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
1 голос
/ 09 июля 2010

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

Примерно так (псевдокод) 

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

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

...