在一定条件下快速计算numpy数组各元素间差异的方法

Question

给定一个numpy数组，我试图找出每个元素对的差异，条件是差异应该小于1000000，大于-1000000

pairWiseDiff = np.array([])
for ts in timestamps:
    diffTime = timestamps - ts
    individualTimeDiff = diffTime[np.logical_and(diffTime<1000000.0, diffTime>-1000000.0)]
    pairWiseDiff = np.append(pairWiseDiff, individualTimeDiff)

此脚本适用于输入数组长度小于40000的用例。但是，我想得到长度为150000的数组的结果，上面的脚本非常慢。在

提高速度的建议？在

Answer 1

假设timestamps是1d。滥用(a-b) = -(b-a)和{}。在

def filterDiff(ts, d, f = lambda x: np.absolute(x)):
    i, j = np.triu_indices(ts.size, 1)
    diffs = ts[i] - ts[j]
    mask = f(diffs) < d  
    out = np.zeros((ts.size, ts.size))
    out[i[mask], j[mask]] = diffs[mask]
    out[j[mask], i[mask]] = -diffs[mask]
    return out

编辑：对于n-d数组

^{pr2}$

编辑2:对于内存问题，您可能需要将diffs和mask计算组合起来。您可以使用mem来一次尽可能多地放入内存中。在

^{3}$

根据mask的稀疏程度、处理异常的方式或正在进行的后续计算，您可能希望跳过生成out（就像我对内存节省版本所做的那样）和return i[mask], j[mask], diffs[mask]。也可以将out改为^{}或{a2}对象。在

这将减少从O(n^2)到O(n*(n-1)/2)的计算次数，并消除许多for循环。在

Answer 2

如果时间戳中只有1000个元素，那么当您避免不必要的计算和避免np.append(pairWiseDiff, diffTime)时，您就可以获得系数1000的加速。runA是您的代码，runB避免{}，而{}避免不必要的计算。在

run A:      1 loop,  best of 3: 1.64 s per loop
run B:    100 loops, best of 3: 7.5 ms per loop
run C:    100 loops, best of 3: 6.8 ms per loop

问题是，您是否真的需要N*N = reshape(N,N)-数组pairWiseDiff，因为您需要并从timestamps获得的所有信息都是由以下内容提供的：

^{pr2}$

这里我比较了3个代码：

^{3}$

Answer 3

您可以将pairWiseDiff的计算数量减少到一半以下。时间戳有N个元素，pairWiseDiff有N*N个元素。考虑pairWiseDiff：第一行是零，其他元素是对角对称的，不需要计算两次。所以从N*N元素中，你只需要计算(N*N - N)/2。在

在我的解决方案中，pairWiseDiff仍然有N*N个元素。你可以用新的三对角数组来改进它。也许for循环可以用numpy.roll公司和/或数字切片. 在

import numpy as np
timestamps = np.array([0,1,2,3,4,5,6,7,8,9])+10
N = len(timestamps)
pairWiseDiff = np.zeros((N,N))

for n in range(1,N):
    pairWiseDiff[n,n:N] = timestamps[n:N] - timestamps[0:N-n]
    print(n,timestamps[n:N])

pairWiseDiff