Numpy数组：首次出现N个连续小于阈值的值

Question

我有一个一维的numpy数组，例如：

a = np.array([1, 4, 5, 7, 1, 2, 2, 4, 10])

我希望能够获得第一个数字的索引，使得接下来的N个值都低于某个值x。

例如，在本例中，对于N=3和x=3，我将查找第一个数字，其之后三个输入都小于三，即a[4]。

可以通过简单地通过for循环迭代所有值来轻松实现此操作，但我想知道是否有更清洁和高效的方法来完成此操作。

- Henry Shackleton

---

倒序循环并检查三个数的和是否满足条件？ - bbd108

@bbd108 倒序执行的缺点是必须耗尽列表才能确保；它无法进行短路优化。 - Ma0

是的，它总是O(n)。 - bbd108

@Henry Shackleton，由于您提到了输入为数组，请编辑示例以反映相同的内容。 - Divakar

这实际上是一个非常有趣的问题。对于给定的示例，我能想到的最佳算法是跳过条目4和5，因为在检查条目1时，它在位置3遇到了7。因此，它将在第二次迭代中解决此问题，而不是第四次。 - Ma0

Answer 1

方法一：

这是一个向量化的 NumPy 方法 -

def start_valid_island(a, thresh, window_size):
    m = a<thresh
    me = np.r_[False,m,False]
    idx = np.flatnonzero(me[:-1]!=me[1:])
    lens = idx[1::2]-idx[::2]
    return idx[::2][(lens >= window_size).argmax()]

样例运行结果 -

In [44]: a
Out[44]: array([ 1,  4,  5,  7,  1,  2,  2,  4, 10])

In [45]: start_valid_island(a, thresh=3, window_size=3)
Out[45]: 4

In [46]: a[:3] = 1

In [47]: start_valid_island(a, thresh=3, window_size=3)
Out[47]: 0

方法二：

使用SciPy的二值腐蚀函数-

from scipy.ndimage.morphology import binary_erosion

def start_valid_island_v2(a, thresh, window_size):
    m = a<thresh
    k = np.ones(window_size,dtype=bool)
    return binary_erosion(m,k,origin=-(window_size//2)).argmax()

第三种方法：

为了完成该集合，这里有一个基于短路和使用numba效率的循环方法-

from numba import njit

@njit
def start_valid_island_v3(a, thresh, window_size):
    n = len(a)
    out = None
    for i in range(n-window_size+1):
        found = True
        for j in range(window_size):
            if a[i+j]>=thresh:
                found = False
                break
        if found:
            out = i
            break
    return out

时间 -

In [142]: np.random.seed(0)
     ...: a = np.random.randint(0,10,(100000000))

In [145]: %timeit start_valid_island(a, thresh=3, window_size=3)
1 loop, best of 3: 810 ms per loop

In [146]: %timeit start_valid_island_v2(a, thresh=3, window_size=3)
1 loop, best of 3: 1.27 s per loop

In [147]: %timeit start_valid_island_v3(a, thresh=3, window_size=3)
1000000 loops, best of 3: 608 ns per loop

- Divakar

---

Mind Approach #1的window_size参数。使用start_valid_island(a, thresh=3, window_size=3)和a[5] = 4将会得到0。换句话说，当没有符合window_size的岛屿时，该函数将返回第一个符合threshold的索引。请注意这一点。 - pr94

Answer 2

尝试像这样编写代码，如果没有数字符合条件，则返回None:

def func(a, n, x):
    for i, e in enumerate(a):
        nextN = a[i+1:i+n+1]
        if len(nextN) < n:
            return None
        elif all([j < x for j in nextN]):
            return e

- zipa

Answer 3

话虽如此，这是在 原生Python 中如何实现它。

a = [1,4,5,7,1,2,2,4,10]

res = next(i for i in range(len(a)-3) if all(j<3 for j in a[i:i+3]))
print(res)  # 4

可能大多数Numpy的解决方案会更快。

还请注意，如果找不到解决方案，则以上内容将抛出StopIteration，因此请考虑将其包装在try块中。

- Ma0