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