Fastest way to create strictly increasing lists in Python
Running a version of @juanpa.arrivillaga's function with numba
import numba
def psi(A):
a_cummax = np.maximum.accumulate(A)
a_new, idx = np.unique(a_cummax, return_index=True)
return idx
def foo(arr):
aux=np.maximum.accumulate(arr)
flag = np.concatenate(([True], aux[1:] != aux[:-1]))
return np.nonzero(flag)[0]
@numba.jit
def f(A):
m = A[0]
a_new, idx = [m], [0]
for i, a in enumerate(A[1:], 1):
if a > m:
m = a
a_new.append(a)
idx.append(i)
return idx
timing
%timeit f(a)
The slowest run took 5.37 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.83 µs per loop
%timeit foo(a)
The slowest run took 9.41 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 6.35 µs per loop
%timeit psi(a)
The slowest run took 9.66 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 9.95 µs per loop
You can calculate the cumulative max of a
and then drop duplicates with np.unique
with which you can also record the unique index so as to subset b
correspondingly:
a = np.array([2,1,2,3,4,5,4,6,5,7,8,9,8,10,11])
b = np.array([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
a_cummax = np.maximum.accumulate(a)
a_new, idx = np.unique(a_cummax, return_index=True)
a_new
# array([ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
b[idx]
# array([ 1, 4, 5, 6, 8, 10, 11, 12, 14, 15])