Python：在不使用“setrecursionlimit”的情况下酸洗高度递归对象

Question

当尝试 pickle 高度递归的树对象时，我收到了 RuntimeError: Maximum recursion Deleep Exeded 。就像这里的提问者一样。

他通过使用 sys.setrecursionlimit 设置更高的递归限制来解决他的问题。但我不想这样做：我认为这更像是一种解决方法，而不是解决方案。因为我希望能够对我的树进行 pickle，即使它们有 10,000 个节点。 （目前它在 200 左右失败。）

（此外，每个平台的真正递归限制都是不同的，我真的很想避免打开这个蠕虫罐。）

有什么方法可以从根本上解决这个问题吗？如果只有 pickle 模块使用循环而不是递归来 pickle，我就不会遇到这个问题。也许有人知道如何在不重写 pickle 模块的情况下导致类似的事情发生？

任何其他想法如何解决这个问题将不胜感激。

Answer 1

我想大多数人从未使用过如此深度的递归结构。由于最简单的序列化实现是递归的，因此您只会看到它们。

如果我是你，我不会在这里使用公开的递归数据结构。相反，我会对每个节点进行编号，并使用链接表来有效地将数字转换为具有该编号的节点。每个节点都将通过该表使用数字引用其他节点（例如其子节点）。一个简单的属性将使语法变得简单。除了这些属性之外，无需更改处理树遍历的代码。节点构造函数必须分配一个数字并将其自身放入链接表中，这也很简单。

链接表可能只是一个节点列表，其中列表中的索引用作节点号； Python 列表似乎可以通过索引进行有效访问。如果插入速度很重要，我会预先分配一个足够长的列表，其中填充 None；它不会占用太多空间。如果节点存储自己的编号，则该结构将可以在两个方向上廉价地遍历。

如您所见，对这样一棵树进行酸洗和反酸洗在任何深度都是微不足道的。

Answer 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

另请注意，此结构可以轻松包含循环并且仍然可以简单地序列化。

Answer 3

只是不要使用递归。
创建一个具有开放节点的堆栈（列表/队列）并对其进行处理。

像这样的东西（伪代码）

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

应该可以做到

Answer 4

我认为一个好的解决方案是梅内和 9000 的答案的结合。鉴于节点具有全局唯一的 ID（也许可以以某种方式使用内存地址），您可以执行此操作。诚然，这是一个草率的伪实现，但如果封装在树类中，通过一些抽象，它可能会非常简单。

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