Tengo una matriz numpy y me gusta comprobar si está ordenada.

>>> a = np.array([1,2,3,4,5])
array([1, 2, 3, 4, 5])
16
luca 29 oct. 2017 a las 22:45

4 respuestas

La mejor respuesta

Con las herramientas NumPy:

np.diff(a)>=0

Pero las soluciones numpy son todas O (n).

Si desea un código rápido y una conclusión muy rápida en matrices sin clasificar:

import numba
@numba.jit
def is_sorted(a):
    for i in range(a.size-1):
         if a[i+1] < a[i] :
               return False
    return True

Que es O (1) en matrices aleatorias.

24
kmario23 29 oct. 2017 a las 20:05

La solución ineficiente pero fácil de escribir:

(a == np.sort(a)).all()
1
1'' 29 oct. 2017 a las 19:57
np.all(a[:-1] <= a[1:])

Ejemplos:

is_sorted = lambda a: np.all(a[:-1] <= a[1:])

>>> a = np.array([1,2,3,4,9])
>>> is_sorted(a)
True

>>> a = np.array([1,2,3,4,3])
>>> is_sorted(a)
False
15
luca 27 nov. 2017 a las 09:59

Para completar, la solución iterativa O (log n) se encuentra a continuación. La versión recursiva es más lenta y se bloquea con grandes tamaños de vectores. Sin embargo, todavía es más lento que el numpy nativo usando np.all(a[:-1] <= a[1:]) probablemente debido a las optimizaciones modernas de la CPU. El único caso en el que el O (log n) es más rápido es en el caso aleatorio "promedio" o si está "casi" ordenado. Si sospecha que su matriz ya está completamente ordenada, entonces np.all será más rápido.

def is_sorted(a):
    idx = [(0, a.size - 1)]
    while idx:
        i, j = idx.pop(0) # Breadth-First will find almost-sorted in O(log N)
        if i >= j:
            continue
        elif a[i] > a[j]:
            return False
        elif i + 1 == j:
            continue
        else:
            mid = (i + j) >> 1 # Division by 2 with floor
            idx.append((i, mid))
            idx.append((mid, j))
    return True

is_sorted2 = lambda a: np.all(a[:-1] <= a[1:])

Aquí están los resultados:

# Already sorted array - np.all is super fast
sorted_array = np.sort(np.random.rand(1000000))

%timeit is_sorted(sorted_array)
659 ms ± 3.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit is_sorted2(sorted_array)
431 µs ± 35.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# Here I included the random in each command so we need to substract it's timing
%timeit np.random.rand(1000000)
6.08 ms ± 17.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit is_sorted(np.random.rand(1000000))
6.11 ms ± 58.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# Without random part, it took 6.11 ms - 6.08 ms = 30µs per loop

%timeit is_sorted2(np.random.rand(1000000))
6.83 ms ± 75.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# Without random part, it took 6.83 ms - 6.08 ms = 750µs per loop

Net, un código optimizado de vector O (n) es mejor que un algoritmo O (log n), a menos que ejecute> 100 millones de matrices de elementos.

0
Dorian B. 4 ene. 2020 a las 08:27