Cách nhanh nhất để lấy nhiều bản sao của một cây trong python là gì?

Question

Trong chương trình python của tôi, tôi cần nhiều bản sao của một cây. Ban đầu, tôi sử dụng bản in sâu từ mô-đun sao chép, điều này hóa ra rất chậm. Sau đó, tôi viết mã của riêng mình để sao chép một cây, mã đi qua cây đang được sao chép và tạo một nút mới tại mỗi nút được truy cập. Sau đó, Tôi gọi các chương trình con này nhiều lần để nhận nhiều bản sao. Giải pháp này nhanh hơn nhiều (~ 40 lần) so với độ sâu.

Giải pháp 2: Sau đó, tôi nghĩ rằng, đi qua một cây cần thời gian T, tạo n bản sao, thời gian bắt buộc là nT; nhưng nếu tôi tạo n nút mới cho mỗi nút được sao chép, tôi chỉ cần duyệt qua cây đang được sao chép một lần, mặc dù ở mỗi nút, bạn sao chép nhiều nút. Điều này sẽ nhanh hơn? Kết quả hóa ra là: không nhiều.

Vẫn hoạt động sao chép là nút cổ chai của chương trình của tôi. Có cách nào nhanh hơn để làm điều đó không? Cảm ơn! Thống kê - sử dụng chức năng copy_tree tùy chỉnh;

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) 

............................. Hãy so sánh với cách tiếp cận 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: đây là chức năng sao chép, rất đơn giản và tùy chỉnh. Xem bình luận của tôi để Ross về nội dung của các nút cây

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

Khi cố gắng để cải thiện hiệu suất mà bạn nên hầu như luôn luôn bắt đầu với profiling dữ liệu và sau đó tối ưu hóa dựa trên những gì bạn nhìn thấy ở đó. Bắt đầu bằng cách sử dụng cProfile.run để chạy mã sao chép cây cấp cao nhất của bạn, sau đó sử dụng lớp pstats.Stats để kiểm tra dữ liệu lược tả và xem nơi bạn thực sự nên tập trung tối ưu hóa của mình. Tôi khuyên bạn nên bắt đầu bằng sorting your stats bởi cumulative thời gian.