lists - sort python 3

Método de ordenación de Python() en la lista frente a la función clasificada internamente()

Question

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

""" Example Output: $ python list_sort_timeit.py Using sort method: 20.0662879944 Using sorted builin method: 259.009809017 """ import random import timeit print ''Using sort method:'', x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000)").repeat()) print x print ''Using sorted builin method:'', x = min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000)").repeat()) print x Como dice el título, me interesaba comparar list.sort () versus sorted (list). El fragmento de arriba mostró algo interesante que, la función de ordenación de Python se comporta muy bien para los datos ya ordenados. Como señaló Anurag, en el primer caso, el método de clasificación está trabajando en datos ya clasificados y, mientras que en el segundo orden, está trabajando en una pieza nueva para hacer el trabajo una y otra vez.

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

""" Example Output: $ python list_sort_timeit.py Using sort method: 19.0166599751 Using sorted builin method: 23.203567028 """ import random import timeit print ''Using sort method:'', x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000);test_list1.sort()").repeat()) print x print ''Using sorted builin method:'', x = min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000);test_list2.sort()").repeat()) print x

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

Answer 1

Bueno, el método de listas .sort() 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 esperaba. Tal vez list.sort() tiene alguna 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.

Editar : Alex y Anurag tienen razón, la diferencia de orden de magnitud se debe a que accidentalmente ordenaste una lista ya ordenada en tu 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.

Answer 2

Porque list.sort clasifica en su lugar, por lo que la primera vez que ordena, pero la próxima vez que está ordenando la lista ordenada.

Por ejemplo, intente esto y obtendrá los mismos resultados en el caso de timeit. La mayor parte del tiempo se usa para copiar y ordenar; también hace 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

Answer 3

Su error en la medición es el siguiente: después de su primera llamada a test_list1.sort() , ese objeto de lista está ordenado, y el género de Python, también timsort como timsort , es perversamente rápido en las listas ya ordenadas. Ese es el error más frecuente al usar timeit : inadvertidamente obtener efectos secundarios y no tenerlos en cuenta.

Aquí hay un buen conjunto de medidas, utilizando timeit desde la línea de comando, ya que 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 x.sort() , pero x.sort() gracias a los efectos secundarios gana más de un orden de magnitud, solo por su error de medición: esto le dice ¡No hay nada sobre el sort versus sorted per se! -)