¿Cuál es la forma más rápida de obtener copias múltiples de un árbol en python?

Question

En mi programa python necesito varias copias de un árbol. Inicialmente, uso Deepcopy desde el módulo de copia, que resulta ser muy lento. Luego escribo mi propio código para copiar un árbol, el código atraviesa el árbol que se está copiando y crea un nuevo nodo en cada nodo que se visita. Luego, Llamo a esta subrutina varias veces para obtener varias copias. Esta solución es mucho más rápida (~ 40 veces más rápida) que la copia en profundidad.

Solución 2: Entonces creo que, atravesar un árbol necesita tiempo T, hacer n copias, el tiempo requerido es nT; pero si creo n nuevos nodos para cada nodo que se está copiando, solo necesito atravesar el árbol que se está copiando una vez, aunque en cada nodo, se copian varios nodos. ¿Será esto más rápido? El resultado es: no mucho.

Todavía la operación de copia es el cuello de botella de mi programa. ¿Hay alguna forma más rápida de hacer eso? ¡Gracias! Estadísticas: utilizando la función copy_tree personalizada;

ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 10.406 10.406 <string>:1(<module>) 
     1 0.002 0.002 10.406 10.406 C:\Python27\sdk.py:1431(algorithm1) 
     26 0.005 0.000 4.602 0.177 C:\Python27\sdk.py:1310(engage) 
    1342 0.005 0.000 4.208 0.003 C:\Python27\lib\idlelib\rpc.py:594(__call__) 
    1342 0.007 0.000 4.203 0.003 C:\Python27\lib\idlelib\rpc.py:208(remotecall) 
    1342 0.017 0.000 3.992 0.003 C:\Python27\lib\idlelib\rpc.py:238(asyncreturn) 
    1342 0.005 0.000 3.972 0.003 C:\Python27\lib\idlelib\rpc.py:279(getresponse) 
    1342 0.033 0.000 3.961 0.003 C:\Python27\lib\idlelib\rpc.py:295(_getresponse) 
    411/26 0.202 0.000 3.930 0.151 C:\Python27\sdk.py:1227(NodeEngage) 
    1338 0.014 0.000 3.909 0.003 C:\Python27\lib\threading.py:235(wait) 
    5356 3.877 0.001 3.877 0.001 {method 'acquire' of 'thread.lock' objects} 
     27 0.001 0.000 3.798 0.141 C:\Python27\sdk.py:888(pick_best_group) 
     378 0.003 0.000 3.797 0.010 C:\Python27\sdk.py:862(group_info) 
46947/378 0.155 0.000 3.786 0.010 C:\Python27\sdk.py:833(core_possibilities) 
    27490 0.114 0.000 3.547 0.000 C:\Python27\sdk.py:779(find_cores) 
    46569 1.046 0.000 3.424 0.000 C:\Python27\sdk.py:798(find_a_true_core) 
    280274 0.873 0.000 1.464 0.000 C:\Python27\sdk.py:213(next) 
     27 0.002 0.000 1.393 0.052 C:\Python27\sdk.py:1008(s) 
    28196 0.016 0.000 1.070 0.000 C:\Python27\sdk.py:1000(copy_tree) 

............................. Comparar con deepcopy enfoque

ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 191.193 191.193 <string>:1(<module>) 
     1 0.002 0.002 191.193 191.193 C:\Python27\sdk.py:1431(algorithm1) 
     26 0.006 0.000 185.611 7.139 C:\Python27\sdk.py:1310(engage) 
    411/26 1.200 0.003 185.013 7.116 C:\Python27\sdk.py:1227(NodeEngage) 
30033397/28196 56.608 0.000 177.885 0.006 C:\Python27\lib\copy.py:145(deepcopy) 
3340177/28196 15.354 0.000 177.741 0.006 C:\Python27\lib\copy.py:283(_deepcopy_inst) 
6680354/28196 23.276 0.000 177.261 0.006 C:\Python27\lib\copy.py:253(_deepcopy_dict) 
3340177/150307 22.345 0.000 171.525 0.001 C:\Python27\lib\copy.py:234(_deepcopy_tuple) 
13360708 23.793 0.000 23.793 0.000 {hasattr} 
13614747 12.483 0.000 15.349 0.000 C:\Python27\lib\copy.py:267(_keep_alive) 
    1342 0.005 0.000 7.281 0.005 C:\Python27\lib\idlelib\rpc.py:594(__call__) 
    1342 0.008 0.000 7.276 0.005 C:\Python27\lib\idlelib\rpc.py:208(remotecall) 
    1342 0.019 0.000 7.039 0.005 C:\Python27\lib\idlelib\rpc.py:238(asyncreturn) 
    1342 0.005 0.000 7.018 0.005 C:\Python27\lib\idlelib\rpc.py:279(getresponse) 
    1342 0.035 0.000 7.006 0.005 C:\Python27\lib\idlelib\rpc.py:295(_getresponse) 
43649486 6.971 0.000 6.971 0.000 {method 'get' of 'dict' objects} 
    1341 0.015 0.000 6.950 0.005 C:\Python27\lib\threading.py:235(wait) 
    5365 6.917 0.001 6.917 0.001 {method 'acquire' of 'thread.lock' objects} 
    6680354 5.325 0.000 5.325 0.000 {method 'iteritems' of 'dict' objects} 
57037048 4.854 0.000 4.854 0.000 {id} 

@ThomasH: esta es la función de copia, que es muy simple y personalizada. Ver mi comentario a Ross por el contenido de los nodos del árbol

def r_copy_tree(node_to_copy, dad_info): 
    new_node = node(dad_info) 

    for (a,son_to_copy) in node_to_copy.sons.items(): 
     new_node.sons[a]=r_copy_tree(son_to_copy,(new_node,a)) 

    return new_node 

def copy_tree(root): 
    return r_copy_tree(root,(None,None)) 

Answer 1

Al tratar de mejorar el rendimiento casi siempre se debe comenzar con profiling de datos y luego optimizar en base a lo que se ve allí. Comience usando cProfile.run para ejecutar su código de copia de árbol de nivel superior, luego use la clase pstats.Stats para inspeccionar los datos de creación de perfiles y vea dónde debe enfocar realmente su optimización. Recomiendo comenzar por sorting your stats por cumulative vez.