Método de orden de Python () en la lista vs función ordenada () incorporada

Sé que la función __builtin__ sorted () funciona en cualquier iterable. Pero, ¿puede alguien explicar esta enorme diferencia de rendimiento (10x) entre anylist.sort () vs ordenada (anylist)? Además, señale si estoy haciendo algo mal con la forma en que se mide.

 ""
 Ejemplo de salida:
 $ python list_sort_timeit.py 
 Usando el método de clasificación: 20.0662879944
 Utilizando el método builin ordenado: 259.009809017
 ""

 importar al azar
 tiempo de importación

 Imprimir 'Usando el método de clasificación:',
 x = min (timeit.Timer ("test_list1.sort ()", "importar aleatoriamente; test_list1 = random.sample (xrange (1000), 1000)"). repeat ())
 imprimir x

 Imprimir 'Usando el método builin ordenado:',
 x = min (timeit.Timer ("sorted (test_list2)", "import random, test_list2 = random.sample (xrange (1000), 1000)"). repeat ())
 imprimir x

Como dice el título, estaba interesado en comparar list.sort () vs ordenados (list). El fragmento anterior mostró algo interesante que, la función de ordenación de python se comporta muy bien para los datos ya ordenados. Como lo señaló Anurag, en el primer caso, el método de clasificación está trabajando en los datos ya ordenados y, mientras que en la segunda, está trabajando en una pieza nueva para trabajar una y otra vez.

Así que escribí este para probar y sí, están muy cerca.

 ""
 Ejemplo de salida:
 $ python list_sort_timeit.py 
 Usando el método de clasificación: 19.0166599751
 Usando el método builin ordenado: 23.203567028
 ""

 importar al azar
 tiempo de importación

 Imprimir 'Usando el método de clasificación:',
 x = min (timeit.Timer ("test_list1.sort ()", "import aleatorio; test_list1 = random.sample (xrange (1000), 1000); test_list1.sort ()"). repeat ())
 imprimir x

 Imprimir 'Usando el método builin ordenado:',
 x = min (timeit.Timer ("sorted (test_list2)", "import random, test_list2 = random.sample (xrange (1000), 1000); test_list2.sort ()"). repeat ())
 imprimir x

Oh, veo a Alex Martelli con una respuesta, ya que estaba escribiendo esta … (Dejaré la edición, ya que podría ser útil).

Su error en la medición es el siguiente: después de su primera llamada a test_list1.sort() , ese objeto de la lista ESTÁ ordenado – ¡y el género de Python, también conocido como timsort , es increíblemente rápido en las listas ya ordenadas! Ese es el error más frecuente en el uso de timeit : obtener efectos secundarios sin dar cuenta de ellos.

Aquí hay un buen conjunto de mediciones, usando timeit desde la línea de comando como se usa mejor:

 $ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' ' y=list(x); y.sort()' 1000 loops, best of 3: 452 usec per loop $ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' ' x.sort()' 10000 loops, best of 3: 37.4 usec per loop $ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' ' sorted(x)' 1000 loops, best of 3: 462 usec per loop 

Como puede ver, y.sort() y sorted(x) son cuello y cuello, pero x.sort() gracias a los efectos secundarios x.sort() en un orden de ventaja de magnitud, solo por su error de medición, sin embargo: esto indica Usted no tiene nada que ver con el sort frente a sí mismo! -)

Debido a que list.sort realiza la clasificación en su lugar, la primera vez que ordena, pero la próxima vez que ordena la lista ordenada.

Por ejemplo, intente esto y obtendrá los mismos resultados en el tiempo, en el caso de que la mayor parte del tiempo se invierta en copiar y ordenar, también se realiza una copia más.

 import time import random test_list1=random.sample(xrange(1000),1000) test_list2=random.sample(xrange(1000),1000) s=time.time() for i in range(100): test_list1.sort() print time.time()-s s=time.time() for i in range(100): test_list2=sorted(test_list2) print time.time()-s 

Bueno, el método .sort() de listas ordena la lista en su lugar, mientras que sorted() crea una nueva lista. Entonces, si tiene una lista grande, parte de su diferencia de rendimiento se deberá a la copia.

Aún así, una diferencia de orden de magnitud parece más grande de lo que yo esperaría. Tal vez list.sort() tiene una optimización de list.sort() especial que sorted() no puede usar. Por ejemplo, dado que la clase de list ya tiene una Py_Object*[] interna Py_Object*[] del tamaño correcto, quizás pueda realizar intercambios de manera más eficiente.

Edición : Alex y Anurag tienen razón, el orden de la diferencia de magnitud se debe a que usted clasificó accidentalmente una lista ya clasificada en su caso de prueba. Sin embargo, como muestran los puntos de referencia de Alex, list.sort() es aproximadamente un 2% más rápido que sorted() , lo que tendría sentido debido a la sobrecarga de copia.