在差异大于x的（非常大）数组中查找所有时间

Question

我的数组是时间数组，所以它被排序并递增

当数组中的差值大于30时，我必须拉出开头/结尾。其他解决方案没有解决的问题是，数组有数千个值，因此在数组中循环似乎效率低下

hugeArr = np.array([0, 2.072, 50.0, 90.0, 91.1])

我希望上述数组的输出类似于：（2.072,50）（50,90）

有没有办法做到这一点

Answer 1

您可以使用np.diff和np.where查找正确的索引：

>>> idxs = np.where(np.diff(hugeArr) > 30)[0]
>>> list(zip(hugeArr[idxs], hugeArr[idxs + 1]))
[(2.072, 50.0), (50.0, 90.0)]

（假设只需要连续值）

正如@not_speshal所提到的，您可以使用np.column_stack而不是list(zip(...))来保持在NumPy边界内：

>>> np.column_stack((hugeArr[idxs], hugeArr[idxs+1]))
array([[ 2.072, 50.   ],
       [50.   , 90.   ]])

Answer 2

我想到的一个策略是，我们不必检查距离小于30的两个数字之间的数字，我们可以这样做，因为它是经过排序的。例如，如果abs(hugeArr[0] - hugeArr[-1]) < 30我们不需要检查任何东西，因为没有任何东西的距离会超过30

我们会从末端开始，朝里走。所以首先检查起始号码和结束号码。然后我们走到一半hugeArr[len(hugeArr)//2]，并根据hugeArr[0]和hugeArr[-1]检查数字距离。然后我们进入范围（hugeArr[0:len(hugeArr)//2]和hugeArr[len(hugeArr)//2:-1]）。我们再次将这两个范围一分为二，只要端到端的距离小于30，我们就不检查它们。我们可以把它变成一个递归算法

最坏的情况是，你将有一个超过30的距离，并结束与O（n），但它可以给你一些优势

但是，类似这样的东西可能需要重构为numpy

def check(arr):
    pairs = []
    
    def check_range(hugeArr):
        difference = abs(hugeArr[0] - hugeArr[-1])

        if difference < 30:
            return

        if len(hugeArr) == 2:
            pairs.append((hugeArr[0], hugeArr[1]))
            return 

        halfway = len(hugeArr)//2

        check_range(hugeArr[:halfway+1])
        check_range(hugeArr[halfway:])
        
    check_range(arr)
    return pairs

Answer 3

试着想想你想做什么。对于数组中的每个值，如果下一个值大于30，则需要保存它们的元组

这里的关键字是每个的。这是一个经典的O(n)复杂度算法，因此降低其时间复杂度对我来说似乎是不可能的

但是，您可以针对阵列进行更改，以加快算法的速度

例如，如果您正在寻找30的差异，并且您知道平均差异为1，那么您最好在

difference = hugeArr[i+15] - hugeArr[i]

看看这个是否大于30。如果不是（而且很可能不会），您可以跳过这15个索引，因为您知道两个连续值之间的差距不大于大差距

如果这对您有效，运行测试，15是完全任意的，可能您的神奇数字是25。更改它一点，并更改函数运行所需的时间