Python：在不使用`setr​​ecursionlimit`的情况下腌制高递归对象

Question

当试图腌制高递归树对象时，我已经得到RuntimeError: maximum recursion depth exceeded。很像this asker here。

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

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

有什么办法在解决这个基本水平？如果只有pickle模块会使用循环代替递归，我不会有这个问题。也许有人有一个想法，我怎么会导致这样的事情发生，而不重写泡菜模块？

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

Answer 1

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

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

链接表可能只是一个节点列表，其中列表中的索引用作节点编号; Python列表似乎有索引的高效访问。如果插入的速度很重要，我会预先分配一个足够长的列表，填充无。它不会占用太多空间。如果节点存储自己的数字，这个结构将在两个方向上便宜地遍历。如你所见，酸洗和取出这样的树在任何深度都是微不足道的。

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