Numpy Array: First occurence of N consecutive values smaller than threshold
Approach #1 :
Here's a vectorized NumPy way -
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()]
Sample runs -
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
Approach #2 :
With SciPy's binary-erosion
-
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()
Approach #3 :
To complete the set, here's a loopy one based on short-ciruiting and using the efficiency of 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
Timings -
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