使用列表被排序的事实来加速numpy关联程序

Question

我目前正在使用python和numpy计算两个列表之间的关联：data_0和data_1。每个列表包含分别排序的时间t0和t1。
我要计算0 < t1 - t0 < t_max所在的所有事件。你知道吗

 for time_0 in np.nditer(data_0):
        delta_time = np.subtract(data_1, np.full(data_1.size, time_0))
        delta_time = delta_time[delta_time >= 0]
        delta_time = delta_time[delta_time < time_max]

这样，当列表被排序时，我选择了一个子数组data_1，其形式为data_1[index_min: index_max]。
所以我需要找到两个索引来得到我想要的。你知道吗

有趣的是，当我转到下一个time_0时，由于data_0也被排序，我只需要找到新的index_min/index_max，比如new_index_min >= index_min/new_index_max >= index_max。 意思是我不需要再浏览所有的data_1。
（从头开始的数据列表）。你知道吗

我实现了这样一个解决方案，没有使用numpy方法（只使用while循环），它给我的结果和以前一样，但没有以前快（15倍长！）。
我认为通常它需要较少的计算，应该有一种方法可以使用numpy方法使它更快，但我不知道怎么做。
有人有主意吗？你知道吗

我不确定我是否非常清楚，所以如果你有任何问题，请不要客气。你知道吗

先谢谢你

保罗

Answer 1

这里是一个使用argsort的矢量化方法。它使用了一种类似于避免完全扫描的策略：

import numpy as np

def find_gt(ref, data, incl=True):
    out = np.empty(len(ref) + len(data) + 1, int)
    total = (data, ref) if incl else (ref, data)
    out[1:] = np.argsort(np.concatenate(total), kind='mergesort')
    out[0] = -1
    split = (out < len(data)) if incl else (out >= len(ref))
    if incl:
        out[~split] -= len(data)
        split[0] = False
    return np.maximum.accumulate(np.where(split, -1, out))[split] + 1

def find_intervals(ref, data, span, incl=(True, True)):
    index_min = find_gt(ref, data, incl[0])
    index_max = len(ref) - find_gt(-ref[::-1], -span-data[::-1], incl[1])[::-1]
    return index_min, index_max

ref = np.sort(np.random.randint(0,20000,(10000,)))
data = np.sort(np.random.randint(0,20000,(10000,)))
span = 2

idmn, idmx = find_intervals(ref, data, span, (True, True))

print('checking')
for d,mn,mx in zip(data, idmn, idmx):
    assert mn == len(ref) or ref[mn] >= d
    assert mn == 0 or ref[mn-1] < d
    assert mx == len(ref) or ref[mx] > d+span
    assert mx == 0 or ref[mx-1] <= d+span
print('ok')

它的工作原理是

• 将两个集合间接排序在一起
• 一组中的每一次都是另一组中的前一次 这是使用maximum.reduce完成的
• 前面的步骤应用两次，第二次是 一组按跨度移动