在我的python程序中,我需要树的多个副本。最初,我使用复制模块的深层复制,结果非常慢。然后我编写自己的代码来复制树,代码遍历被复制的树,并在每个正在访问的节点上创建一个新节点。然后 我多次调用这个子例程来获得多个副本。这个解决方案比深度拷贝快得多(〜40倍)。解决方法2:然后我想,遍历一棵树需要时间T,使n个副本,所需的时间是nT;但是如果为每个正在复制的节点创建n个新节点,我只需要遍历一次要复制的树,尽管在每个节点上复制了多个节点。这会更快吗?结果证明是:并不多。什么是在Python中获取树的多个副本的最快方法?
复制操作仍然是我的程序的瓶颈。有没有更快的方法来做到这一点?谢谢! 统计信息 - 使用自定义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)
.............................与deepcopy的方法比较
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:这是复制功能,非常简单和自定义。见我的罗斯评论为树节点
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))
顺便说一句,为什么你需要树的多个副本? – dyoo
它们将被安装在更大的树上。 – justin
+1非常好的话题,感谢您提出。 - 即使使用自定义的copy_tree,您为什么认为复制仍然是瓶颈?你的统计数据显示它在整个运行时间的约10%。你可以显示copy_tree的实现吗? – ThomasH