python - 在 python 中获取树的多个副本的最快方法是什么？

Question

在我的 python 程序中，我需要一棵树的多个副本。最初，我使用复制模块中的 deepcopy，结果发现它非常慢。然后我自己编写代码来复制一棵树，代码遍历被复制的树并在每个被访问的节点处创建一个新节点。然后我多次调用这个子程序来获得多个副本。这个解决方案比 deepcopy 快得多(快 40 倍)。

解法二:那我想，遍历一棵树需要时间T，做n份，需要的时间是nT；但是如果我为每个被复制的节点创建n个新节点，我只需要遍历被复制的树一次，虽然在每个节点，你复制多个节点。这样会更快吗？结果是:不多。

复制操作仍然是我程序的瓶颈。有没有更快的方法来做到这一点？谢谢!统计——使用自定义的copy_tree函数；

   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)

................................与深度复制方法比较

   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:这是复制功能，很简单，也很习惯。树节点的内容看我给Ross的评论

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

当尝试提高性能时，您几乎应该总是从 profiling 开始数据，然后根据您在那里看到的内容进行优化。从使用 cProfile.run 开始运行顶级树复制代码，然后使用 pstats.Stats类来检查分析数据，看看你应该真正关注优化的地方。我建议从 sorting your stats 开始按累计时间。