如何加速python嵌套循环？

Question

我正在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

Answer 1

更新:(几乎)完全矢量化版本下面的"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)