Tăng tốc một vòng lặp cứng nhắc trong python?

Question

Xét đoạn mã sau sử dụng mảng NumPy đó là rất chậm:

# Intersection of an octree and a trajectory 
def intersection(octree, trajectory): 
    # Initialize numpy arrays 
    ox = octree.get("x") 
    oy = octree.get("y") 
    oz = octree.get("z") 
    oe = octree.get("extent")/2 
    tx = trajectory.get("x") 
    ty = trajectory.get("y") 
    tz = trajectory.get("z") 
    result = np.zeros(np.size(ox)) 
    # Loop over elements 
    for i in range(0, np.size(tx)): 
     for j in range(0, np.size(ox)): 
      if (tx[i] > ox[j]-oe[j] and 
       tx[i] < ox[j]+oe[j] and 
       ty[i] > oy[j]-oe[j] and 
       ty[i] < oy[j]+oe[j] and 
       tz[i] > oz[j]-oe[j] and 
       tz[i] < oz[j]+oe[j]): 
       result[j] += 1 
    # Finalize 
    return result 

Làm thế nào để viết lại các chức năng để tăng tốc độ tính toán? (np.size(tx) == 10000 và np.size(ox) == 100000)

Answer 1

Bạn phân bổ 10.000 danh sách kích thước 100000. Điều đầu tiên cần làm là nên ngừng sử dụng range cho j vòng lặp lồng nhau và sử dụng phiên bản phát xrange để thay thế. Điều này sẽ giúp bạn tiết kiệm thời gian và không gian phân bổ tất cả các danh sách đó.

Người tiếp theo sẽ được sử dụng hoạt động vectorized:

for i in xrange(0, np.size(tx)): 
    index = (ox-oe < tx[i]) & (ox+oe > tx[i]) & (oy-oe < ty[i]) & (oy+oe > ty[i]) & (oz-oe < tz[i]) & (oz+oe > tz[i]) 
    result[index] += 1 

Answer 2

Bạn đang có khả năng để có được kết quả tốt bằng cách chạy mã này dưới PyPy: http://pypy.org/ (hướng dẫn tích hợp NumPy của chúng tôi tại https://bitbucket.org/pypy/numpy)

Answer 3

Tôi nghĩ rằng điều này sẽ cho kết quả tương tự cho vòng lặp kép và nhanh hơn:

for j in xrange(np.size(ox)): 
    result[j] += sum(abs(tx-ox[j])<oe[j] & abs(ty-oy[j])<oe[j] & abs(tz-oz[j])<oe[j]) 

Để nhận được điều này: 1) sắp xếp lại các vòng lặp (ví dụ, hoán đổi t hem) hợp lệ vì không có gì thay đổi trong vòng lặp; 2) kéo result[j] bên ngoài vòng lặp i; 3) chuyển đổi tất cả các t>ox-oe and t<ox+oe thành abs(t-ox)<oe (mặc dù điều này có thể không phải là một tăng tốc lớn, nhưng nó dễ đọc hơn).

Vì bạn không có mã runnable, và tôi không muốn xây dựng một thử nghiệm cho điều này, tôi không chắc chắn 100% này là chính xác.