¿Pasa revertir = Verdadero cuando la clasificación de una lista en Python afecta la eficiencia?

Question

Al llamar al sort() en una lista en Python, al pasar cmp=f se ralentiza el orden. ¿Pasar reverse=True afecta la eficiencia del género de alguna manera (o es idéntica a la clasificación sin inversión)?

Answer 1

El método sort() es nativo, es decir, se implementa en el idioma del host en lugar de en Python. Al pasar una función en el argumento cmp se fuerza a la implementación nativa a llamar a esa función y ejecutar código Python en cada iteración. Ahí es donde proviene el golpe de rendimiento.

Por otro lado, pasar True en el argumento reverse solo indica al algoritmo nativo que ordene los elementos en orden inverso. Si cmp no está configurado, solo estará involucrado el código nativo, por lo que el rendimiento debería ser comparable al simple sort().

Por supuesto, la evaluación comparativa lo diría con certeza.

Answer 2

Supongo que no hay desaceleración debido a reverse=True ya que el resultado podría simplemente construirse con decisiones invertidas en el camino. Si se comparan correctamente (gracias a Duncan), esta suposición se confirma:

In [18]: import random 

In [57]: x = range(1000) 

In [58]: random.shuffle(x) 

In [59]: %timeit sorted(x) 
1000 loops, best of 3: 341 us per loop 

In [54]: x = range(1000) 

In [55]: random.shuffle(x) 

In [56]: %timeit sorted(x, reverse = True) 
1000 loops, best of 3: 344 us per loop 

He repetido esta prueba varias veces y con diferentes listas de tamaño (N = 10**3, 10**4, 10**5) y recibieron resultados consistentes.

Answer 3

De mis puntos de referencia, parece que hay una pequeña diferencia:

import timeit 

setup = """ 
import random 
random.seed(1) 
l = range(10000) 
random.shuffle(l) 
""" 

run1 = """ 
sorted(l) 
""" 

run2 = """ 
sorted(l, reverse=True) 
""" 

n1 = timeit.timeit(run1, setup, number=10000) 
n2 = timeit.timeit(run2, setup, number=10000) 

print n1, n2 
print (n2/n1 - 1)*100,"%" 

Resultados en (en mi máquina):

38.8531708717 41.2889549732 
6.26920286513 % 

la misma corrida, pero para una lista de 1000 elementos:

2.80148005486 2.74061703682 
-2.17253083528 % 

# ...another round... 
2.90553498268 2.86594104767 
-1.36270722083 % 

Answer 4

Sorprendentemente, lleva más tiempo revertir-ordenar una lista. Las otras respuestas ya han demostrado esto con buenos puntos de referencia. Miré en la fuente y encontré el explanation in listobject.c:

/* Reverse sort stability achieved by initially reversing the list, 
applying a stable forward sort, then reversing the final result. */ 
if (reverse) { 
    if (keys != NULL) 
     reverse_slice(&keys[0], &keys[saved_ob_size]); 
    reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]); 
} 

Por lo tanto, para obtener una salida ordenada, la lista se invierte antes de la clasificación, a continuación, ordenadas, y finalmente invierte de nuevo. Invertir una lista es una operación O (n), por lo que pagará más y más por esto, más larga será la lista.

Esto sugiere que si usted está construyendo una función clave personalizada de todos modos, a continuación, se puede ahorrar tiempo para grandes listas negando directamente:

very_long_list.sort(key=lambda x, y: -cmp(x, y)) 

en lugar de utilizar reversed=True:

very_long_list.sort(key=lambda x, y: cmp(x, y), reverse=True) 

En este caso, puede pasar key=cmp directamente en el segundo caso y guardar la llamada extra a través de la función lambda. Pero si tiene una expresión más grande, entonces esto podría dar sus frutos.

Answer 5

Tenga en cuenta que la cmp arg a list.sort y la función incorporada sorted están en desuso en Python 2. x y ya no se permiten en 3. x, a causa de los malos resultados que dan, como usted ha notado . En su lugar, se supone que debe usar el key arg para definir un orden de clasificación personalizado.