python - lista - ¿Por qué es max más lento que el tipo?

sort python 3

Question

Descubrí que max es más lento que la función de sort en Python 2 y 3.

Python 2

$ python -m timeit -s ''import random;a=range(10000);random.shuffle(a)'' ''a.sort();a[-1]''
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s ''import random;a=range(10000);random.shuffle(a)'' ''max(a)''        
1000 loops, best of 3: 342 usec per loop

Python 3

$ python3 -m timeit -s ''import random;a=list(range(10000));random.shuffle(a)'' ''a.sort();a[-1]''
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s ''import random;a=list(range(10000));random.shuffle(a)'' ''max(a)''
1000 loops, best of 3: 371 usec per loop

¿Por qué max ( O(n) ) es más lento que la función de sort ( O(nlogn) )?

Answer 1

En primer lugar, tenga en cuenta que max() usa el protocolo iterador , mientras que list.sort() usa código ad-hoc . Claramente, el uso de un iterador es una sobrecarga importante, es por eso que está observando esa diferencia en los tiempos.

Sin embargo, aparte de eso, sus pruebas no son justas. Está ejecutando a.sort() en la misma lista más de una vez. El algoritmo utilizado por Python está específicamente diseñado para ser rápido para datos ya (parcialmente) ordenados. Sus pruebas dicen que el algoritmo está haciendo bien su trabajo.

Estas son pruebas justas:

$ python3 -m timeit -s ''import random;a=list(range(10000));random.shuffle(a)'' ''max(a[:])''
1000 loops, best of 3: 227 usec per loop
$ python3 -m timeit -s ''import random;a=list(range(10000));random.shuffle(a)'' ''a[:].sort()''
100 loops, best of 3: 2.28 msec per loop

Aquí estoy creando una copia de la lista cada vez. Como puede ver, el orden de magnitud de los resultados es diferente: micro y milisegundos, como era de esperar.

Y recuerde: big-Oh especifica un límite superior! El límite inferior para el algoritmo de clasificación de Python es Ω ( n ). Ser O ( n log n ) no implica automáticamente que cada ejecución tome un tiempo proporcional a n log n . Ni siquiera implica que deba ser más lento que un algoritmo O ( n ), pero esa es otra historia. Lo importante es entender que en algunos casos favorables, un algoritmo O ( n log n ) puede ejecutarse en tiempo O ( n ) o menos.

Answer 2

Esto podría deberse a que l.sort es miembro de la list mientras que max es una función genérica. Esto significa que l.sort puede confiar en la representación interna de la list mientras que max tendrá que pasar por un protocolo iterador genérico.

Esto hace que cada recuperación de elementos para l.sort sea ​​más rápida que la recuperación de cada elemento que hace max .

Supongo que si en su lugar usa sorted(a) obtendrá el resultado más lento que max(a) .

Answer 3

timeit tener mucho cuidado al usar el módulo timeit en Python.

python -m timeit -s ''import random;a=range(10000);random.shuffle(a)'' ''a.sort();a[-1]''

Aquí el código de inicialización se ejecuta una vez para producir una matriz aleatoria a . Luego, el resto del código se ejecuta varias veces. La primera vez que ordena la matriz, pero cada dos veces está llamando al método de ordenación en una matriz ya ordenada. Solo se devuelve el tiempo más rápido, por lo que en realidad está cronometrando cuánto tiempo le lleva a Python ordenar una matriz ya ordenada.

Parte del algoritmo de clasificación de Python es detectar cuándo la matriz ya está parcial o completamente clasificada. Cuando está completamente ordenado, simplemente tiene que escanear una vez a través de la matriz para detectar esto y luego se detiene.

Si en cambio lo intentaste:

python -m timeit -s ''import random;a=range(100000);random.shuffle(a)'' ''sorted(a)[-1]''

entonces la ordenación ocurre en cada ciclo de tiempo y puede ver que el tiempo para ordenar una matriz es mucho más largo que solo encontrar el valor máximo.

Editar: la answer @ skyking explica la parte que dejé sin explicar: a.sort() sabe que está trabajando en una lista, por lo que puede acceder directamente a los elementos. max(a) funciona en cualquier iterativo arbitrario, por lo que debe usar iteración genérica.