什麼是在Python中獲取樹的多個副本的最快方法？

Question

在我的python程序中，我需要樹的多個副本。最初，我使用複製模塊的深層複製，結果非常慢。然後我編寫自己的代碼來複制樹，代碼遍歷被複制的樹，並在每個正在訪問的節點上創建一個新節點。然後 我多次調用這個子例程來獲得多個副本。這個解決方案比深度拷貝快得多（〜40倍）。解決方法2：然後我想，遍歷一棵樹需要時間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) 

.............................與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)) 

Answer 1

的內容當試圖提高性能，你應該總是先從profiling數據，然後根據你看到有什麼優化。首先使用cProfile.run運行頂級樹形複製代碼，然後使用pstats.Stats類來檢查概要分析數據，並查看應該將重點放在何處。我建議由sorting your stats開始cumulative時間。