12

我一直RuntimeError: maximum recursion depth exceeded在尝试腌制一个高度递归的树对象。很像这里的这个提问者。

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

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

有没有办法从根本上解决这个问题？如果只有 pickle 模块会使用循环而不是递归进行腌制，我就不会遇到这个问题。也许有人知道我如何在不重写 pickle 模块的情况下导致这样的事情发生？

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

4

4 回答 4

3

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

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

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

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

于 2010-06-05T02:52:24.303 回答
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

还要注意，这个结构可以很容易地包含循环并且仍然可以简单地序列化。

于 2010-06-15T23:47:33.563 回答
1

我认为一个好的解决方案是结合梅内和 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
于 2010-08-27T21:40:07.700 回答
1

只是不要使用递归。使用开放节点创建一个堆栈（列表/队列）并处理它。

像这样的东西（伪代码）

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

应该这样做

于 2010-07-09T12:51:52.990 回答