Python: decapado de objetos altamente recursivos sin usar `setcursionlimit`

Question

He estado obteniendo RuntimeError: maximum recursion depth exceeded al intentar extraer un objeto de árbol altamente recursivo. Al igual que this asker here.

Resolvió su problema al establecer el límite de recursión más alto con sys.setrecursionlimit. Pero no quiero hacer eso: creo que es más una solución que una solución. Porque quiero ser capaz de encurtir mis árboles incluso si tienen 10,000 nodos en ellos. (En la actualidad falla en torno a 200.)

(también, cierto límite de recursividad de cada plataforma es diferente, y realmente me gustaría evitar abrir esta lata de gusanos.)

¿Hay alguna manera de resolver esto en el nivel fundamental? Si solo el módulo Pickle saltara usando un bucle en lugar de recursión, no habría tenido este problema. Tal vez alguien tenga una idea de cómo puedo hacer que algo como esto suceda, sin reescribir el módulo Pickle?

Cualquier otra idea de cómo puedo resolver este problema será apreciada.

Answer 1

Supongo que la mayoría de la gente nunca usa estructuras recursivas de tal profundidad. Como las implementaciones de serialización más sencillas son recursivas, solo las verá.

Si yo fuera usted, no usaría una estructura de datos abiertamente recursiva aquí. En cambio, enumeraba todos los nodos y utilizaba una tabla de enlaces que traduce de manera eficiente un número a un nodo con ese número. Cada nodo se referirá a otros nodos (por ejemplo, sus hijos) a través de esa tabla, usando números. Una propiedad simple haría esto sintácticamente fácil. Más allá de esas propiedades, ningún código relacionado con el cruce de árboles tendría que cambiar. El constructor de nodos tendrá que asignar un número y colocarse en la tabla de enlaces, lo que también es trivial.

La tabla de enlaces podría ser solo una lista de nodos, donde el índice en la lista sirve como el número de nodo; Las listas de Python parecen tener acceso eficiente por índice. Si la velocidad de las inserciones es importante, preasignaré una lista lo suficientemente larga con Ninguno; no tomaría demasiado espacio. Si los nodos almacenan sus propios números, esta estructura sería muy accesible en ambas direcciones.

Como ve, decapando y deshaciendo tal árbol sería trivial a cualquier profundidad.

Answer 2

Para hacer más fácil la comprensión, aquí hay un ejemplo completo, con un solo enlace a simplificarlo:

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 

También tenga en cuenta que esta estructura puede contener fácilmente ciclos y todavía serializar claramente.

Answer 3

Simplemente no utilice recursion. Haz una pila (lista/cola) con nodos abiertos y procesa esto.

Algo como esto (pseudo código)

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

Eso debería hacerlo

Answer 4

creo que una buena solución es una combinación de Mene de respuestas y de 9000. Dado que los nodos tienen identificadores globales únicos (tal vez de alguna manera las direcciones de memoria se pueden usar como tales) puede hacerlo. De acuerdo, esta es una pseudoimplementación descuidada, pero con un poco de abstracción si se encapsula en una clase de árbol, podría ser muy simple.

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