title in python plot

La forma más rápida de crear listas estrictamente crecientes en Python

Question

Me gustaría averiguar cuál es la forma más eficiente de lograr lo siguiente en Python:

Supongamos que tenemos dos listas a y b que tienen la misma longitud y contienen hasta 1e7 elementos. Sin embargo, para facilitar la ilustración, podemos considerar lo siguiente:

a = [2, 1, 2, 3, 4, 5, 4, 6, 5, 7, 8, 9, 8,10,11]
b = [1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15]

El objetivo es crear una lista estrictamente monotónica a partir de a mientras que solo se utiliza el primer punto de muestra de puntos de muestra con valores idénticos. Los mismos índices que deben eliminarse en a también deben eliminarse en b modo que el resultado final sea:

a_new = [2, 3, 4, 5, 6, 7, 8, 9,10,11]
b_new = [1, 4, 5, 6, 8,10,11,12,14,15]

Por supuesto, esto puede hacerse usando costos computacionales for bucles, que sin embargo no son adecuados debido a la gran cantidad de datos.

Cualquier sugerencia es muy apreciada.

Answer 1

Aquí hay una solución Python de vainilla que hace una pasada:

>>> a = [2,1,2,3,4,5,4,6,5,7,8,9,8,10,11]
>>> b = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
>>> a_new, b_new = [], []
>>> last = float(''-inf'')
>>> for x, y in zip(a, b):
...     if x > last:
...         last = x
...         a_new.append(x)
...         b_new.append(y)
...
>>> a_new
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> b_new
[1, 4, 5, 6, 8, 10, 11, 12, 14, 15]

Tengo curiosidad por ver cómo se compara con la solución numpy , que tendrá una complejidad de tiempo similar pero hace un par de pases en los datos.

Aquí hay algunos tiempos. Primero, la configuración:

>>> small = ([2,1,2,3,4,5,4,6,5,7,8,9,8,10,11], [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
>>> medium = (np.random.randint(1, 10000, (10000,)), np.random.randint(1, 10000, (10000,)))
>>> large = (np.random.randint(1, 10000000, (10000000,)), np.random.randint(1, 10000000, (10000000,)))

Y ahora los dos enfoques:

>>> def monotonic(a, b):
...     a_new, b_new = [], []
...     last = float(''-inf'')
...     for x,y in zip(a,b):
...         if x > last:
...             last = x
...             a_new.append(x)
...             b_new.append(y)
...     return a_new, b_new
...
>>> def np_monotonic(a, b):
...     a_new, idx = np.unique(np.maximum.accumulate(a), return_index=True)
...     return a_new, b[idx]
...

Tenga en cuenta que los enfoques no son estrictamente equivalentes, uno se queda en tierra de Python de vainilla, el otro se queda en tierra de variedad numpy . Compararemos el rendimiento suponiendo que esté comenzando con la estructura de datos correspondiente (ya sea numpy.array o list ):

Entonces, primero, una pequeña lista, la misma del ejemplo del OP, vemos que el numpy no es realmente más rápido, lo que no es sorprendente para las estructuras de datos pequeñas:

>>> timeit.timeit("monotonic(a,b)", "from __main__ import monotonic, small; a, b = small", number=10000)
0.039130652003223076
>>> timeit.timeit("np_monotonic(a,b)", "from __main__ import np_monotonic, small, np; a, b = np.array(small[0]), np.array(small[1])", number=10000)
0.10779813499539159

Ahora, una lista / matriz "media" de 10,000 elementos, comenzamos a ver numpy ventajas:

>>> timeit.timeit("monotonic(a,b)", "from __main__ import monotonic, medium; a, b = medium[0].tolist(), medium[1].tolist()", number=10000)
4.642718859016895
>>> timeit.timeit("np_monotonic(a,b)", "from __main__ import np_monotonic, medium; a, b = medium", number=10000)
1.3776302759943064

Ahora, curiosamente, la ventaja parece reducirse con matrices "grandes", del orden de 1e7 elementos:

>>> timeit.timeit("monotonic(a,b)", "from __main__ import monotonic, large; a, b = large[0].tolist(), large[1].tolist()", number=10)
4.400254560023313
>>> timeit.timeit("np_monotonic(a,b)", "from __main__ import np_monotonic, large; a, b = large", number=10)
3.593393853981979

Tenga en cuenta que, en el último par de tiempos, solo los hice 10 veces cada uno, pero si alguien tiene una máquina mejor o más paciencia, no dude en aumentar el number

Answer 2

Ejecutando una versión de la función de @ juanpa.arrivillaga con 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

sincronización

%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

Answer 3

Puede calcular el máximo acumulativo de a y luego soltar los duplicados con np.unique con los que también puede registrar el índice único de manera que el subconjunto b corresponda:

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])

Answer 4

unique con return_index utiliza argsort . Con maximum.accumulate que no es necesario. Así que podemos canibalizar de forma unique y hacer:

In [313]: a = [2,1,2,3,4,5,4,6,5,7,8,9,8,10,11]
In [314]: arr = np.array(a)
In [315]: aux = np.maximum.accumulate(arr)
In [316]: flag = np.concatenate(([True], aux[1:] != aux[:-1])) # key unique step
In [317]: idx = np.nonzero(flag)
In [318]: idx
Out[318]: (array([ 0,  3,  4,  5,  7,  9, 10, 11, 13, 14], dtype=int32),)
In [319]: arr[idx]
Out[319]: array([ 2,  3,  4,  5,  6,  7,  8,  9, 10, 11])
In [320]: np.array(b)[idx]
Out[320]: array([ 1,  4,  5,  6,  8, 10, 11, 12, 14, 15])

In [323]: np.unique(aux, return_index=True)[1]
Out[323]: array([ 0,  3,  4,  5,  7,  9, 10, 11, 13, 14], dtype=int32)

def foo(arr):
    aux=np.maximum.accumulate(arr)
    flag = np.concatenate(([True], aux[1:] != aux[:-1]))
    return np.nonzero(flag)[0]

In [330]: timeit foo(arr)
....
100000 loops, best of 3: 12.5 µs per loop
In [331]: timeit np.unique(np.maximum.accumulate(arr), return_index=True)[1]
....
10000 loops, best of 3: 21.5 µs per loop

Con el medium forma (10000), este único sin género tiene una ventaja de velocidad sustancial:

In [334]: timeit np.unique(np.maximum.accumulate(medium[0]), return_index=True)[1]
1000 loops, best of 3: 351 µs per loop
In [335]: timeit foo(medium[0])
The slowest run took 4.14 times longer ....
10000 loops, best of 3: 48.9 µs per loop

[1]: use np.source(np.unique) para ver el código, o ?? en IPython