¿Por qué es max más lento que sort?

Question

¿Por qué es max más lento que sort?

He encontrado que max es más lento que la función 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é es max (O(n)) ¿más lento que la función sort (O(nlogn))?

90

python sorting max python-internals

Author: martineau, 2016-01-26

Source

3 answers

En primer lugar, tenga en cuenta que max() utiliza el protocolo iterador, mientras list.sort() utiliza código ad-hoc . Claramente, usar 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 ordenados (parcialmente). Sus pruebas están diciendo que el algoritmo es 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 se puede ver, el orden de magnitud de los resultados son diferentes: micro-vs milisegundos, como cabría esperar.

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

88

Author: Andrea Corbellini,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-01-26 14:02:40

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

Esto hace que cada elemento fetch para l.sort sea más rápido que cada elemento fetch que max lo haga.

Asumo que si usas sorted(a) obtendrás el resultado más lento que max(a).

31

Author: skyking,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-01-26 13:40:25

score 123 · Accepted Answer

Debes 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 que está llamando al método sort en una matriz ya ordenada. Solo se devuelve el tiempo más rápido, por lo que en realidad está cronometrando el tiempo que tarda Python en ordenar una matriz ya ordenada.

Parte del algoritmo de ordenación de Python es para detectar cuando el array ya está parcial o completamente ordenado. 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 bucle de tiempo y se puede ver que el tiempo para ordenar una matriz es de hecho mucho más largo que simplemente encontrar el valor máximo.

Editar: La respuesta de @skyking explica la parte que dejé inexplicable: a.sort() sabe que está funcionando en un lista para que pueda acceder directamente a los elementos. max(a) funciona en cualquier iterable arbitrario, por lo que debe usar iteración genérica.