ordenado() usando expresiones de generador en lugar de listas

Después de ver la discusión aquí: Python - generate the time difference Me puse curioso. Inicialmente, también pensé que un generador es más rápido que una lista, pero cuando se trata de ordenado() no lo sé. ¿Hay algún beneficio en enviar una expresión de generador a sorted() en lugar de a una lista? ¿La expresión del generador termina convirtiéndose en una lista dentro de ordenada() antes de ordenar de todos modos?ordenado() usando expresiones de generador en lugar de listas

EDITAR: Me duele solo poder aceptar una respuesta, ya que siento que muchas respuestas han ayudado a aclarar el problema. Gracias de nuevo a todos.

Fuente

2010-11-11 Brent Newey

Lo primero que hace sorted() es convertir los datos en una lista. Básicamente la primera línea (después de la validación de argumentos) de la aplicación es

newlist = PySequence_List(seq);

Ver también the full source code version 2.7 y version 3.1.2.

Editar: Como se ha señalado en el answer by aaronasterling, la variable newlist es, así, una nueva lista . Si el parámetro ya es una lista, se copia. Entonces, una expresión de generador realmente tiene la ventaja de usar menos memoria.

Fuente

2010-11-11 13:12:46

Impresionante. Gracias. ¿Crees que habría alguna ventaja para realizar algún trabajo durante el primer paso del generador? Sé que esto sería relativamente inconsecuente en general, pero parece que podría ser un poco más eficiente. –

Supongo que usan Quicksort. No parece posible hacer "algún trabajo" durante el primer pase; implicaría intercambiar elementos con el elemento al final de la lista, que aún no se conoce. –

Por lo que he leído sobre la clasificación de Python, hacen muchas optimizaciones y no vuelven a Quicksort. Al transferir los valores de la expresión del generador, en teoría podría hacer algunas comparaciones con los valores que ya ha colocado en su lista. –

No hay forma de ordenar una secuencia sin conocer todos los elementos de la secuencia, por lo que cualquier generador pasado a sorted() se agota.

Fuente

2010-11-11 12:56:15

Esto tiene sentido. También tengo curiosidad por saber qué ordenó() cuando recibe un generador. ¿Lo convierte inmediatamente en una lista antes de realizar el ordenamiento, o la primera pasada del algoritmo de ordenación sobre el generador hace algún trabajo hacia el tipo real? –

También Inicialmente se pensó que una lista por comprensión es más rápido que una lista

¿Qué quiere decir más rápido que una lista? ¿Quiere decir más rápido que un for explícito? Para eso diré que depende: la comprensión de la lista es más como un azúcar sintáctico, pero es muy útil cuando se trata de bucle simple.

pero cuando se trata de ordenar() Yo no saber. ¿Hay alguna ventaja en enviar una expresión de generador para ordenar() en lugar de una lista?

La principal diferencia entre las comprensiones de listas y las expresiones de generador es que las expresiones de generador evitan la sobrecarga de generar toda la lista a la vez. En su lugar, devuelven un objeto generador que se puede iterar uno por uno, por lo que las expresiones del Generador se usan más probablemente para ahorrar el uso de la memoria.

Pero tienes que entender una cosa en Python: es muy difícil saber si una forma es más rápida (optimista) que otra forma con solo mirarla, y si quieres hacerlo, debes usar timeit para la evaluación comparativa (y el benchmarking es más complejo que solo ejecutar un tiempo en una sola máquina).

Lea this para obtener más información sobre algunas técnicas de optimización.

Fuente

2010-11-11 13:13:27 mouad

En este caso, estoy preguntando sobre el comportamiento específico de sorted(). No iría demasiado lejos en el camino de discutir sobre la sintaxis de la lista de comprensiones y generadores. EDITAR: también me preocupa la cuestión de si hay alguna ventaja teórica para procesar el generador a medida que itera sobre él. –

@Brent Newey: creo que ya tiene la respuesta sobre el uso de la expresión de generador de Sven Marnach, y para __ hay alguna ventaja teórica al procesar el generador mientras itera sobre él__ como dije en mi respuesta, principalmente para ahorrar memoria. , piense en un generador como este cuando pasa un genexpr a un bucle que el bucle le preguntará cada vez que me dé el siguiente artículo y cada vez que genexpr genere este elemento para él como generación Just In Time (JIT), espero que mi explicación sea bueno :) – mouad

Python utiliza Timsort. Timsort necesita saber el número total de elementos por adelantado para calcular el parámetro minrun. Por lo tanto, como informa Sven, lo primero que se ordena al recibir un generador es convertirlo en una lista.

Dicho esto, sería posible escribir una versión incremental de Timsort, que consumía los valores del generador más lentamente - solo tendría que arreglar minrun antes de comenzar, y aceptar el dolor de tener algunas fusiones desequilibradas en el fin. Timsort funciona en dos fases. La primera fase implica un pase a través de toda la matriz, identificando ejecuciones y haciendo una ordenación de inserción para hacer ejecuciones donde los datos están desordenados. Tanto la búsqueda de ejecución como la ordenación de inserción son intrínsecamente incrementales. La segunda fase implica una fusión de las corridas ordenadas; eso sucedería exactamente como ahora.

No creo que haya muchos puntos en esto, sin embargo. Tal vez haría más fácil la administración de la memoria, porque en lugar de tener que leer desde el generador a una matriz en constante crecimiento (como supongo sin fundamento que la implementación actual sí lo hace), podrías leer cada ejecución en un pequeño buffer, luego solo asignar un final tampón de tamaño una vez, al final. Sin embargo, esto implicaría tener ranuras 2N de matriz en la memoria a la vez, mientras que una matriz en crecimiento se puede hacer con 1.5N si se duplica cuando crece. Entonces, probablemente no sea una buena idea.

Fuente

2010-11-11 13:36:46

Buena discusión sobre los pros y los contras de manejar el generador en ordenados(). Gracias. –

Hay una gran ventaja. Debido a que sorted no afecta a la secuencia aprobada, tiene que hacer una copia de la misma. Si está haciendo una lista de la expresión del generador, solo se hace una lista. Si se pasa una comprensión de lista, primero se construye y luego sorted hace una copia para ordenar.

Esto se refleja en la línea

newlist = PySequence_List(seq);

citado en Sven Marnach's answer. Esencialmente, esto hará incondicionalmente una copia de cualquier secuencia que se le pase.

Fuente

2010-11-11 14:52:27 aaronasterling

Tienes razón :) Pero también ten en cuenta los tiempos de Dave Webb. Actualizaré mi respuesta. –

Buen punto. No había pensado en eso. –

La forma más fácil de ver cuál es más rápido es utilizar timeit y me dice que es más rápido para aprobar una lista en lugar de un generador:

>>> import random 
>>> randomlist = range(1000) 
>>> random.shuffle(randomlist) 
>>> import timeit 
>>> timeit.timeit("sorted(x for x in randomlist)",setup = "from __main__ import randomlist",number = 10000) 
4.944492386602178 
>>> timeit.timeit("sorted([x for x in randomlist])",setup = "from __main__ import randomlist",number = 10000) 
4.635165083830486

>>> timeit.timeit("sorted(x for x in xrange(1000,1,-1))",number = 10000) 
1.411807087213674 
>>> timeit.timeit("sorted([x for x in xrange(1000,1,-1)])",number = 10000) 
1.0734657617099401

creo esto es porque cuando sorted() convierte el valor entrante a una lista, puede hacerlo más rápidamente para algo que ya es una lista que para un generador. The source code seems to confirm this (pero esto es por leer los comentarios en lugar de entender completamente todo lo que está sucediendo).

Fuente

2010-11-11 15:15:47

+1, Suposiciones de apoyo con datos. –

un punto que siempre me ha quedado claro es: ¿qué tan bueno es Python para detectar los valores desechables y otras situaciones más complicadas? detecta algunos casos, por lo que cuando dices 'print (id ([42,])); print (id ([42,])); 'regularmente recibes la misma identificación. python garantiza que cuando compare las dos instancias de lista, tendrán diferentes identificadores, pero como eso no puede suceder aquí, python lo hace de manera más eficiente y reutiliza la memoria. por esta razón, sería más justo asegurarse de que la lista no sea un valor desechable, ya que luego ordenada no puede evitar copiarla. – flow

Si el rendimiento es importante, ¿por qué no procesar los datos tal como son generados por el generador y aplicar el orden sobre los resultados de las iteraciones? Por supuesto, esto podría usarse solo si no hay un condicionamiento causal entre iteraciones (es decir, los datos de la iteración ordenada n. ° [i] no son necesarios para hacer ningún cálculo para la iteración ordenada n. ° [i + 1]). Lo que trato de decir en este caso es que ordenar un conjunto de estructuras potencialmente más grandes generadas por el generador podría estar agregando mucha complejidad innecesaria a un pedido que podría tener lugar después de procesar todos los elementos.

Fuente

2012-11-27 21:49:10

vez debería añadir a la respuesta de tiempo de Dave Webb [puse en lo que puede ser una edición anónima], que cuando se accede a un generador optimizado directamente, que puede ser mucho más rápido; gran parte de la sobrecarga puede ser la creación del código de una lista o generador propio:

>>> timeit.timeit("sorted(xrange(1000, 1, -1))", number=10000) 
0.34192609786987305 
>>> timeit.timeit("sorted(range(1000, 1, -1))", number=10000) 
0.4096639156341553 
>>> timeit.timeit("sorted([el for el in xrange(1000, 1, -1)])", number=10000) 
0.6886589527130127 
>>> timeit.timeit("sorted(el for el in xrange(1000, 1, -1))", number=10000) 
0.9492318630218506

Fuente

2015-10-14 14:23:59 Mark

ordenado() usando expresiones de generador en lugar de listas

Respuesta

Cuestiones relacionadas