Как ускорить вложенный цикл Python? - PullRequest
Новая
       15

Как ускорить вложенный цикл Python?

10 голосов
/ 18 июня 2010

Я выполняю вложенный цикл в Python, который включен ниже. Это служит основным способом поиска в существующих финансовых временных рядах и поиска периодов во временных рядах, которые соответствуют определенным характеристикам. В этом случае есть два отдельных, одинакового размера массива, представляющих «закрытие» (то есть цену актива) и «объем» (то есть сумму актива, который был обменен за период). Для каждого периода времени я хотел бы посмотреть на все будущие интервалы с длинами от 1 до INTERVAL_LENGTH и посмотреть, имеют ли какие-либо из этих интервалов характеристики, соответствующие моему поиску (в этом случае отношение значений закрытия больше, чем 1,0001 и менее чем 1,5, а суммарный объем больше 100).

Насколько я понимаю, одной из основных причин ускорения использования NumPy является то, что интерпретатору не нужно проверять операнды каждый раз, когда он что-то вычисляет, пока вы работаете с массивом в целом (например, numpy_array * 2), но, очевидно, код ниже не использует это преимущество. Есть ли способ заменить внутренний цикл какой-нибудь оконной функцией, которая может привести к ускорению, или каким-либо другим способом, использующим numpy / scipy, чтобы существенно ускорить это в нативном питоне?

В качестве альтернативы, есть ли лучший способ сделать это в целом (например, будет ли намного быстрее написать этот цикл в C ++ и использовать weave)? 

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 ]

7 голосов
/ 18 июня 2010

Обновление: (почти) полностью векторизованная версия ниже в "new_function2" ...

Я добавлю комментарии, чтобы немного объяснить вещи.

Это дает ~ 50-кратное ускорение, и большее ускорение возможно, если у вас все в порядке с выводом в виде пустых массивов вместо списков.Как есть: 

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

против 

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)
3 голосов
/ 18 июня 2010

Одним ускорением будет удаление части 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) всегда быстрее.

Правка - реализация (это не проверено): 

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
1 голос
/ 18 июня 2010

Почему бы вам не попытаться сгенерировать результат в виде одного списка (намного быстрее, чем добавление или расширение), например: 

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
          ]
...