Как к вложенному циклу Python ускорения?
Я выполняю вложенный цикл в Python, который включен ниже. Это служит основным способом перерыть существующий финансовый временной ряд и искать периоды во временных рядах, которые соответствуют определенным характеристикам. В этом случае существует два отдельных, одинаково размерных, массива, представляющие 'завершение' (т.е. цена актива) и 'объем' (т.е. сумма актива, которым обменялись за период). В течение каждого периода вовремя я хотел бы ожидать во всех будущих интервалах с длинами между 1 и INTERVAL_LENGTH и видеть, имеет ли какой-либо из тех интервалов характеристики, которые соответствуют моему поиску (в этом случае, отношение близких значений больше, чем 1,0001, и меньше чем 1,5 и суммированный объем больше, чем 100).
Мое понимание - то, что одна из основных причин ускорения при использовании NumPy - то, что интерпретатору не нужны к проверке типа операнды каждый раз, когда это оценивает что-то, пока Вы воздействуете на массив в целом (например, numpy_array * 2), но очевидно код ниже не использует в своих интересах это. Существует ли способ заменить внутренний цикл некоторой функцией окна, которая могла привести к ускорению или какому-либо другому способу использовать numpy/scipy для ускорения этого существенно в собственном Python?
С другой стороны, существует ли лучший способ сделать это в целом (например, это будет намного быстрее, чтобы записать, что этот цикл в C++ и использовании переплетается)?
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
3 ответа
Обновление: (почти) полностью векторизованная версия ниже в "new_function2"...
Я добавлю комментарии, чтобы немного объяснить вещи.
Это дает ~ 50-кратное ускорение, и большее ускорение возможно, если вы согласны с выводом массивов numpy, а не списков. Как есть:
In [86]: %timeit new_function2(close, volume, INTERVAL_LENGTH)
1 loops, best of 3: 1.15 s per loop
Вы можете заменить внутренний цикл вызовом np.cumsum()... Смотрите мою функцию "new_function" ниже. Это дает значительное ускорение...
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
Должно быть возможно векторизировать все это и полностью избежать циклов, хотя... Дайте мне минутку, и я посмотрю, что я могу сделать...
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)
Одним из способов ускорения было бы удаление части sum, поскольку в данной реализации она суммирует список длины 2 через INTERVAL_LENGTH. Вместо этого просто добавьте volume[j+1] к предыдущему результату vol из последней итерации цикла. Таким образом, вы просто добавляете два целых числа каждый раз вместо того, чтобы суммировать весь список и нарезать его каждый раз. Также, вместо того, чтобы начинать с выполнения sum(volume[i+1:j+1]), просто выполните vol = volume[i+1] + volume[j+1], поскольку вы знаете, что в начальном случае здесь всегда будет только два индекса.
Еще одним ускорением было бы использование .extend вместо .append, поскольку в реализации python extend работает значительно быстрее.
Вы также можете разбить финальный оператор if так, чтобы выполнять определенные вычисления только при необходимости. Например, вы знаете, что if vol <= 100, вам не нужно вычислять ret.
Это не дает точного ответа на вашу проблему, но я думаю, особенно в случае с проблемой суммы, что вы должны увидеть значительное ускорение с этими изменениями.
Редактировать - вам также не нужно len, поскольку вы уже знаете конкретную длину списка (если только это не было сделано только для примера). Определение как числа, а не len(something) всегда быстрее.
Edit - implementation (это не проверено):
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
Почему бы вам не попробовать сгенерировать результат в виде единого списка (гораздо быстрее, чем добавление или расширение), что-то вроде:
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
]