Làm thế nào để tăng tốc vòng lặp lồng nhau python?

Question

Tôi đang thực hiện một vòng lặp lồng nhau trong python được bao gồm bên dưới. Đây là cách tìm kiếm cơ bản thông qua chuỗi thời gian tài chính hiện tại và tìm kiếm các khoảng thời gian trong chuỗi thời gian phù hợp với các đặc điểm nhất định. Trong trường hợp này, có hai mảng riêng biệt, có kích thước bằng nhau, đại diện cho 'đóng' (nghĩa là giá của một nội dung) và 'khối lượng' (nghĩa là số tiền của tài sản được trao đổi trong khoảng thời gian này). Đối với mỗi khoảng thời gian, tôi muốn nhìn về phía trước ở tất cả các khoảng thời gian trong tương lai với độ dài từ 1 đến INTERVAL_LENGTH và xem có bất kỳ khoảng thời gian nào có đặc điểm phù hợp với tìm kiếm của tôi hay không (trong trường hợp này tỷ lệ của giá trị đóng lớn hơn 1,0001 và ít hơn hơn 1,5 và khối lượng tổng hợp lớn hơn 100).

Sự hiểu biết của tôi là một trong những lý do chính cho việc tăng tốc khi sử dụng NumPy là trình thông dịch không cần phải gõ-kiểm tra các toán hạng mỗi khi nó đánh giá một cái gì đó miễn là bạn đang hoạt động trên mảng toàn bộ (ví dụ numpy_array * 2), nhưng rõ ràng là đoạn code dưới đây không lợi dụng điều đó. Có cách nào để thay thế các vòng lặp nội bộ với một số loại chức năng cửa sổ mà có thể dẫn đến một tăng tốc, hoặc bất kỳ cách nào khác bằng cách sử dụng numpy/scipy để tăng tốc độ này lên đáng kể trong python bản địa?

Ngoài ra, có cách nào tốt hơn để làm điều này nói chung (ví dụ: sẽ nhanh hơn khi viết vòng lặp này trong C++ và sử dụng dệt)?

ARRAY_LENGTH = 500000 
INTERVAL_LENGTH = 15 
close = np.array(xrange(ARRAY_LENGTH)) 
volume = np.array(xrange(ARRAY_LENGTH)) 
close, volume = close.astype('float64'), volume.astype('float64') 

results = [] 
for i in xrange(len(close) - INTERVAL_LENGTH): 
    for j in xrange(i+1, i+INTERVAL_LENGTH): 
     ret = close[j]/close[i] 
     vol = sum(volume[i+1:j+1]) 
     if ret > 1.0001 and ret < 1.5 and vol > 100: 
      results.append([i, j, ret, vol]) 
print results 

Answer 1

Cập nhật: Phiên bản (gần như) hoàn toàn vectorized dưới đây trong "new_function2" ...

tôi sẽ thêm ý kiến ​​để giải thích mọi thứ trong một bit.

Tốc độ tăng tốc 50x và tăng tốc lớn hơn nếu bạn không đồng ý với đầu ra là mảng có nhiều mảng thay vì danh sách. Như là:

In [86]: %timeit new_function2(close, volume, INTERVAL_LENGTH) 
1 loops, best of 3: 1.15 s per loop 

Bạn có thể thay thế vòng lặp bên trong bằng một cuộc gọi đến np.cumsum() ...Xem hàm "new_function" của tôi bên dưới. Điều này cho phép một sự tăng tốc đáng kể ...

In [61]: %timeit new_function(close, volume, INTERVAL_LENGTH) 
1 loops, best of 3: 15.7 s per loop 

vs

In [62]: %timeit old_function(close, volume, INTERVAL_LENGTH) 
1 loops, best of 3: 53.1 s per loop 

Nó nên có thể để vectorize toàn bộ điều và tránh cho vòng hoàn toàn, mặc dù ... Hãy cho tôi một phút, và tôi ll thấy những gì tôi có thể làm ...

import numpy as np 

ARRAY_LENGTH = 500000 
INTERVAL_LENGTH = 15 
close = np.arange(ARRAY_LENGTH, dtype=np.float) 
volume = np.arange(ARRAY_LENGTH, dtype=np.float) 

def old_function(close, volume, INTERVAL_LENGTH): 
    results = [] 
    for i in xrange(len(close) - INTERVAL_LENGTH): 
     for j in xrange(i+1, i+INTERVAL_LENGTH): 
      ret = close[j]/close[i] 
      vol = sum(volume[i+1:j+1]) 
      if (ret > 1.0001) and (ret < 1.5) and (vol > 100): 
       results.append((i, j, ret, vol)) 
    return results 


def new_function(close, volume, INTERVAL_LENGTH): 
    results = [] 
    for i in xrange(close.size - INTERVAL_LENGTH): 
     vol = volume[i+1:i+INTERVAL_LENGTH].cumsum() 
     ret = close[i+1:i+INTERVAL_LENGTH]/close[i] 

     filter = (ret > 1.0001) & (ret < 1.5) & (vol > 100) 
     j = np.arange(i+1, i+INTERVAL_LENGTH)[filter] 

     tmp_results = zip(j.size * [i], j, ret[filter], vol[filter]) 
     results.extend(tmp_results) 
    return results 

def new_function2(close, volume, INTERVAL_LENGTH): 
    vol, ret = [], [] 
    I, J = [], [] 
    for k in xrange(1, INTERVAL_LENGTH): 
     start = k 
     end = volume.size - INTERVAL_LENGTH + k 
     vol.append(volume[start:end]) 
     ret.append(close[start:end]) 
     J.append(np.arange(start, end)) 
     I.append(np.arange(volume.size - INTERVAL_LENGTH)) 

    vol = np.vstack(vol) 
    ret = np.vstack(ret) 
    J = np.vstack(J) 
    I = np.vstack(I) 

    vol = vol.cumsum(axis=0) 
    ret = ret/close[:-INTERVAL_LENGTH] 

    filter = (ret > 1.0001) & (ret < 1.5) & (vol > 100) 

    vol = vol[filter] 
    ret = ret[filter] 
    I = I[filter] 
    J = J[filter] 

    output = zip(I.flat,J.flat,ret.flat,vol.flat) 
    return output 

results = old_function(close, volume, INTERVAL_LENGTH) 
results2 = new_function(close, volume, INTERVAL_LENGTH) 
results3 = new_function(close, volume, INTERVAL_LENGTH) 

# Using sets to compare, as the output 
# is in a different order than the original function 
print set(results) == set(results2) 
print set(results) == set(results3) 

Answer 2

Một tăng tốc sẽ là để loại bỏ các phần sum, như trong việc thực hiện này nó tóm tắt một danh sách dài từ 2 đến INTERVAL_LENGTH. Thay vào đó, chỉ cần thêm volume[j+1] vào kết quả trước đó của vol từ lần lặp cuối cùng của vòng lặp. Vì vậy, bạn chỉ cần thêm hai số nguyên mỗi lần thay vì tổng hợp toàn bộ danh sách VÀ cắt nó mỗi lần. Ngoài ra, thay vì bắt đầu bằng cách thực hiện sum(volume[i+1:j+1]), chỉ cần thực hiện vol = volume[i+1] + volume[j+1], vì bạn biết trường hợp ban đầu ở đây sẽ luôn chỉ là hai chỉ mục.

Tăng tốc khác sẽ sử dụng .extend thay vì .append, khi triển khai trăn có extend chạy nhanh hơn đáng kể.

Bạn cũng có thể chia nhỏ câu lệnh if cuối cùng để chỉ thực hiện tính toán nhất định nếu được yêu cầu. Ví dụ: bạn biết if vol <= 100, bạn không cần phải tính ret.

Điều này không trả lời chính xác vấn đề của bạn, nhưng tôi nghĩ đặc biệt với vấn đề tổng hợp mà bạn sẽ thấy tăng tốc đáng kể với những thay đổi này.

Chỉnh sửa - bạn cũng không cần len, vì bạn biết cụ thể độ dài của danh sách đã có (trừ khi đó chỉ là ví dụ). Việc xác định số đó dưới dạng số thay vì len(something) luôn nhanh hơn.

Edit - thực hiện (điều này là chưa được kiểm tra):

ARRAY_LENGTH = 500000 
INTERVAL_LENGTH = 15 
close = np.array(xrange(ARRAY_LENGTH)) 
volume = np.array(xrange(ARRAY_LENGTH)) 
close, volume = close.astype('float64'), volume.astype('float64') 

results = [] 
ex = results.extend 
for i in xrange(ARRAY_LENGTH - INTERVAL_LENGTH): 
    vol = volume[i+1] 
    for j in xrange(i+1, i+INTERVAL_LENGTH): 
     vol += volume[j+1] 
     if vol > 100: 
      ret = close[j]/close[i] 
      if 1.0001 < ret < 1.5: 
       ex([i, j, ret, vol]) 
print results 

Answer 3

Tại sao bạn không cố gắng để tạo ra các kết quả như một danh sách duy nhất (nhanh hơn nhiều so với phụ thêm hoặc mở rộng), một cái gì đó như:

results = [ t for t in ((i, j, close[j]/close[i], sum(volume[i+1:j+1])) 
         for i in xrange(len(close)-INT_LEN) 
          for j in xrange(i+1, i+INT_LEN) 
         ) 
      if t[3] > 100 and 1.0001 < t[2] < 1.5 
      ]