在一个（非常大的）数组中找到所有时间差大于 x

Question

我的数组是时间，所以是排序递增的。

我必须取出数组中差异大于 30 的 beginning/end。其他解决方案未涵盖的问题是数组有数千个值，因此遍历数组似乎效率低下。

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，您希望保存它们的元组。

这里的关键词是for each。这是一个经典的 O(n) 复杂度算法，所以降低它的时间复杂度对我来说似乎是不可能的。

但是，您可以针对您的数组进行特定更改，以使算法更快。

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

处寻找 index i

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

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

如果这对你有效，运行测试，15 是完全任意的，也许你的幻数是 25。稍微改变一下，看看你的函数有多长运行.

Answer 3

想到的一个策略是我们不必检查距离小于 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

在一个（非常大的）数组中找到所有时间差大于 x

Find all the times in a (very large) array that have a difference greater than x

python

arrays

tuples

numpy