如何加速python嵌套循环？

Question

我在python中执行一个嵌套循环，如下所示。这是搜索现有金融时间序列并在时间序列中寻找符合某些特征的时段的基本方法。在这种情况下，有两个独立的、大小相同的数组，表示“成交”（即资产价格）和“成交量”（即在此期间交换的资产金额）。对于每一个时间段，我希望看到所有长度介于1和间隔长度之间的未来间隔，并查看这些间隔是否具有与我的搜索匹配的特征（在这种情况下，接近值的比率大于1.0001且小于1.5且总和大于100）。

我的理解是，在使用NumPy时速度加快的一个主要原因是，只要您对整个数组（例如NumPy数组*2）进行操作，解释器就不需要每次计算某个值时都键入check操作数，但显然下面的代码没有利用这一点。有没有一种方法可以将内部循环替换为某种可能导致加速的窗口函数，或者使用numpy/scipy在本机python中以任何其他方式来大幅加速？

P>可选的，是否有更好的方法来完成这一点（例如，在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

更新：（几乎）完全矢量化版本在下面的“新功能2”。。。

我会加上一些评论来解释一下。

它提供大约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

对

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)

Answer 2

一个加速将是删除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。

这并不能准确地回答你的问题，但我认为特别是在sum问题上，你应该看到这些变化带来了显著的加速。

编辑-您也不需要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

Answer 3

为什么不尝试将结果生成为单个列表（比追加或扩展快得多），例如：

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
          ]