Python: Pikowanie wysoce rekurencyjnych obiektów bez użycia `setrecursionlimit`

Question

Otrzymuję RuntimeError: maximum recursion depth exceeded podczas próby wybrania wysoce rekursywnego obiektu drzewa. Podobnie jak this asker here.

Rozwiązał on swój problem, ustawiając wyższy limit rekurencji z sys.setrecursionlimit. Ale nie chcę tego robić. Myślę, że to raczej rozwiązanie, niż rozwiązanie. Ponieważ chcę mieć możliwość wybrania drzewek, nawet jeśli mają one 10.000 węzłów. (Obecnie nie na poziomie około 200.)

(także prawdziwe ograniczenie rekursji każdej platformie jest inna, a ja naprawdę chciałbym uniknąć otwierając tę ​​puszkę Pandory.)

Czy istnieje jakiś sposób, aby rozwiązać ten problem w podstawowy poziom? Gdyby tylko moduł piklowania wybrałby pętlę zamiast rekursji, nie miałbym tego problemu. Może ktoś ma pomysł, w jaki sposób mogę spowodować, że coś takiego się stanie, bez przepisywania modułu pikle?

Każdy inny pomysł na rozwiązanie tego problemu zostanie doceniony.

Answer 1

Przypuszczam, że większość ludzi nigdy nie używa struktur rekursywnych o takiej głębokości. Ponieważ najprostsze implementacje serializacji są rekurencyjne, zobaczysz je tylko.

Gdybym był tobą, nie używałbym tu otwartej struktury danych rekursywnych. Zamiast tego numerowałem każdy węzeł i korzystałem z tabeli linków, która skutecznie tłumaczy liczbę do węzła o tej liczbie. Każdy węzeł będzie odwoływał się do innych węzłów (na przykład jego dzieci) za pośrednictwem tej tabeli, używając liczb. Prosta właściwość uczyniłaby to syntaktycznie łatwym. Poza tymi właściwościami, żaden kod zajmujący się przemytem drzewa nie musiałby się zmieniać. Konstruktor węzła będzie musiał przydzielić numer i umieścić go w tabeli łącza, co również jest trywialne.

Tabela linków może być po prostu listą węzłów, gdzie indeks do listy służy jako numer węzła; Listy Pythona wydają się mieć sprawny dostęp przez indeks. Jeśli szybkość wstawiania jest ważna, przygotowałbym wystarczająco długą listę wypełnioną Brakiem; nie zajęłoby to zbyt wiele miejsca. Jeśli węzły przechowują swoje własne liczby, struktura ta byłaby taniej przejezdna w obu kierunkach.

Jak widać, wytrawianie i rozpakowywanie takiego drzewa byłoby banalne na każdej głębokości.

Answer 2

Aby ułatwić zrozumienie, tu jest pełna przykładów, tylko jeden link, aby go uprościć:

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 

Należy również pamiętać, że ta struktura może łatwo zawierać cykle i nadal serializacji wyraźnie.

Answer 3

Po prostu nie używaj rekursji. Utwórz stos (listę/kolejkę) z otwartymi węzłami i przetwórz to.

Coś w tym (pseudo kod)

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

To powinno zrobić to

Answer 4

Myślę, że dobrym rozwiązaniem jest połączenie Mene i 9000 za odpowiedzi. Biorąc pod uwagę, że węzły mają globalnie unikalne identyfikatory (może w jakiś sposób adresy pamięci mogą być używane jako takie), możesz to zrobić. Jest to niechlujna pseudo-implementacja, ale z odrobiną abstrakcji, jeśli jest zawarta w klasie drzewa, może być bardzo prosta.

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