¿Por qué es "ordenados()" más lento que "copiar y, a continuación .Sort()" de Python

Aquí está el código que encontré:¿Por qué es "ordenados()" más lento que "copiar y, a continuación .Sort()" de Python

import timeit 

print timeit.Timer('''a = sorted(x)''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000) 
print timeit.Timer('''a=x[:];a.sort()''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000)

y aquí están los resultados:

0.00259663215837 
0.00207390190177

Me gustaría saber por qué usar .sort() es consistentemente más rápido que sorted() a pesar de que ambos son listas de copiado.

Nota: Me postulo Python 2.7 en un sistema i5 a 2,53 GHz con Win7

Fuente

2012-07-18 TimY

recomendaría probar este varias veces seguidas con listas mucho más grandes para el rigor –

@AndrewGorcester Compro la sugerencia de la lista más grande, pero ¿por qué más veces? ¿1000 no es suficiente para una precisión estadística razonable? – robert

Disculpe, no estaba familiarizado con el módulo de tiempo y me acababa de dar cuenta de que se repetía 1000 veces al mismo tiempo que respondía. Eso debería ser un montón de repeticiones. –

La diferencia que usted está mirando es minúsculo, y completamente desaparece de las listas más largas. Simplemente añadiendo * 1000 a la definición de x da los siguientes resultados en mi máquina:

2.74775004387 
2.7489669323

Mi mejor conjetura por la razón que sorted() era un poco más lento para usted es que sorted() tiene que utilizar un código genérico que puede copiar cualquier iterable a una lista, mientras que copiar la lista directamente puede hacer la suposición de que la fuente también es una lista. El código de clasificación utilizado por CPython es realmente el mismo para list.sort() y sorted(), por lo que no es eso lo que está causando la diferencia.

Editar: El source code of the current development version of sorted() hace el equivalente moral de

a = list(x) 
a.sort()

y, de hecho, el uso de este código en lugar de su segunda versión elimina cualquier diferencia de velocidad significativas para cualquier tamaño de la lista.

Fuente

2012-07-18 18:13:14

[los resultados en mi máquina respaldan su respuesta] (http://stackoverflow.com/a/11547854/4279). – jfs

Yup - 'list.sort' puede trabajar con un tamaño conocido, y intercambiar elementos dentro de ese tamaño,' sorted() 'tiene que trabajar con tamaños desconocidos e iterables genéricos, y así puede tener que asignar memoria a medida que se crea (posiblemente forzando una memcpy si no contig), pero esto debería ser mínimo como usted ha indicado. Copiar una lista es bastante simple ya que es solo una simple operación malloc/memcpy op (y la creación de un nuevo PyObject *) –

En apoyo de @Sven Marnach's answer:

Hay una pequeña diferencia para pequeñas listas:

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]; s=sorted" "a=s(x)" 
1000000 loops, best of 3: 1.87 usec per loop 

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]" "a=x[:];a.sort()" 
1000000 loops, best of 3: 1.66 usec per loop

La diferencia desaparece con * 1000 (listas más grandes):

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000; s=sorted" "a=s(x)" 
100 loops, best of 3: 3.42 msec per loop 

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000" "a=x[:];a.sort()" 
100 loops, best of 3: 3.48 msec per loop

Fuente

2012-07-18 18:20:36 jfs

¿Por qué es "ordenados()" más lento que "copiar y, a continuación .Sort()" de Python

Respuesta

Cuestiones relacionadas