在数组中查找“close”的元素

下面是一个迭代偏移量的解决方案,同时缩小候选集,直到没有剩余值为止:

import numpy as np

def f_pp(A, maxgap):
    d0 = np.diff(A)
    d = d0.copy()
    IDX = []
    k = 1
    idx, = np.where(d <= maxgap)
    vidx = idx[d[idx] > 0]
    while vidx.size:
        IDX.append(vidx[:, None] + (0, k))
        if idx[-1] + k + 1 == A.size:
            idx = idx[:-1]
        d[idx] = d[idx] + d0[idx+k]
        k += 1
        idx = idx[d[idx] <= maxgap]
        vidx = idx[d[idx] > 0]
    return np.concatenate(IDX, axis=0)

data = np.cumsum(np.random.exponential(size=10000)).repeat(np.random.randint(1, 20, (10000,)))

pairs = f_pp(data, 1)
#pairs = set(map(tuple, pairs))

from timeit import timeit
kwds = dict(globals=globals(), number=100)
print(data.size, 'points', pairs.shape[0], 'close pairs')
print('pp', timeit("f_pp(data, 1)", **kwds)*10, 'ms')

样本运行:

99963 points 1020651 close pairs
pp 43.00256529124454 ms

对数组进行切片是一种非常有效的方法。由于对数据进行了排序,您可以计算差异并将其拆分:

d=np.diff(x)
ind=np.where(d>5)[0]
pieces=np.split(x,ind)

在这里 pieces 是一个列表,在该列表中,您可以在循环中对每个元素使用自己的代码。

最好的算法高度依赖于我不知道的数据的性质。例如,另一种可能是编写嵌套循环:

pairs=[]
for i in range(x.size):
    j=i+1
    while x[j]-x[i]<=5 and j<x.size:
        pairs.append([i,j])
        j+=1

如果你想让它更聪明,你可以通过编辑外循环来在 j 撞到一个缺口。