Python: Pickling oggetti altamente ricorsivi senza usare `setrecursionlimit`

Question

Mi sono trovato RuntimeError: maximum recursion depth exceeded quando provavo a decapare un oggetto ad albero ricorsivo. Molto simile a this asker here.

Ha risolto il problema impostando il limite di ricorsione più alto con sys.setrecursionlimit. Ma non voglio farlo: penso che sia più una soluzione alternativa che una soluzione. Perché voglio essere in grado di mettere sottoterra i miei alberi anche se contengono 10.000 nodi. (Attualmente non riesce a circa 200.)

(Inoltre, il limite di ricorsione vera di ogni piattaforma è diversa, e vorrei davvero evitare di aprire questo vaso di Pandora.)

Esiste un modo per risolvere questo a il livello fondamentale? Se solo il modulo pickle dovesse decapare usando un ciclo invece di ricorsione, non avrei avuto questo problema. Forse qualcuno ha un'idea di come possa accadere qualcosa del genere, senza riscrivere il modulo pickle?

Qualsiasi altra idea su come posso risolvere questo problema sarà apprezzata.

Answer 1

Suppongo che la maggior parte delle persone non utilizzi mai strutture ricorsive di tale profondità. Poiché le implementazioni di serializzazione più semplici sono ricorsive, le vedrai solo.

Se fossi in te, non utilizzerei qui una struttura di dati ricorsivamente aperta. Invece, numererei ogni nodo e userei una tabella di collegamenti che traduce efficientemente un numero in un nodo con quel numero. Ogni nodo farebbe riferimento ad altri nodi (ad esempio i suoi figli) tramite quella tabella, usando i numeri. Una proprietà semplice renderebbe questo sintatticamente facile. Al di là di queste proprietà, nessun codice riguardante l'attraversamento degli alberi dovrebbe cambiare. Il costruttore del nodo dovrà allocare un numero e inserirsi nella tabella dei collegamenti, anch'essa banale.

La tabella di collegamento potrebbe essere solo un elenco di nodi, in cui l'indice nell'elenco funge da numero di nodo; Gli elenchi Python sembrano avere un accesso efficiente per indice. Se la velocità degli inserti è importante, preallocherebbe una lista abbastanza lunga riempita con None; non ci vorrebbe troppo spazio. Se i nodi memorizzassero i propri numeri, questa struttura sarebbe economicamente attraversabile in entrambe le direzioni.

Come vedi, il decapaggio e il disfacimento di un tale albero sarebbe banale a qualsiasi profondità.

Answer 2

Per rendere più facile comprensione, ecco un esempio completo, con un solo link per semplificare:

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 

noti inoltre che questa struttura può facilmente contenere cicli e ancora serializzare chiaramente.

Answer 3

Non utilizzare la ricorsione. Crea uno stack (elenco/coda) con nodi aperti ed elaboralo.

Qualcosa di simile (pseudo codice)

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

che dovrebbe farlo

Answer 4

penso che una buona soluzione è una combinazione di Mene e di risposte 9000 di. Dato che i nodi hanno ID univoci globali (forse in qualche modo gli indirizzi di memoria possono essere usati come tali) puoi farlo. Ammessa questa è una pseudo-implementazione sciatta, ma con un po 'di astrazione se incapsulata in una classe di albero potrebbe essere molto semplice.

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