Dos formas similares de verificar si una lista contiene un número impar:
any(x % 2 for x in a) any(True for x in a if x % 2)
Resultados de tiempo con a = [0] * 10000000
(cinco intentos cada uno, tiempos en segundos):
0.60 0.60 0.60 0.61 0.63 any(x % 2 for x in a) 0.36 0.36 0.36 0.37 0.37 any(True for x in a if x % 2)
¿Por qué la segunda forma es casi el doble de rápida?
Mi código de prueba:
from timeit import repeat setup = 'a = [0] * 10000000' expressions = [ 'any(x % 2 for x in a)', 'any(True for x in a if x % 2)', ] for expression in expressions: times = sorted(repeat(expression, setup, number=1)) print(*('%.2f ' % t for t in times), expression)
Las respuestas anteriores suponen que el lector ya está familiarizado con la sintaxis y los generadores. Me gustaría explicar más para las personas que no lo son.
el fragmento
any(x % 2 for x in a)
es una sintaxis corta para:
any((x % 2 for x in a))
Entonces, lo que sucede es que (x % 2 for x in a)
se evalúa y el valor del resultado se asigna a any
función. Al igual que print(21 * 2
) calcula el valor 42, que luego se le da a la función de print
.
La expresión (x % 2 for x in a)
es una expresión generadora y su resultado es un iterador generador. Ese es un objeto que calcula y entrega sus valores a pedido. Entonces, en este caso, cuando se le pide un valor, este iterador busca el siguiente valor de a
, calcula su resto módulo 2 (es decir, 0 para par y 1 para impar) y entrega ese valor. Y luego, literalmente, espera que posiblemente se le pregunte nuevamente por otro valor.
La función any
es un segundo actor aquí. Obtiene el iterador como argumento y luego le pide al iterador más y más valores, esperando que uno sea verdadero (tenga en cuenta que 1 es verdadero y 0 es falso).
Realmente puedes pensar en ello como dos personas diferentes interactuando. El tipo cualquiera que le pide valores al tipo iterador. Nuevamente, tenga en cuenta que el iterator-guy no calcula todos los valores por adelantado. Solo uno a la vez, cada vez que cualquier tipo pregunta por el siguiente valor. Así que es realmente un tira y afloja entre los dos muchachos.
En el caso de any(x % 2 for x in a)
, el iterator-guy, cada vez que any-guy le pregunta por el siguiente valor, solo calcula un valor de módulo, se lo entrega a any-guy, y el cualquier- chico tiene que juzgarlo. Aquí, el chico iterador es como un desarrollador junior incompetente, involucrando al gerente para cada número, obligándolos a microgestionar de alguna manera.
En el caso de any(True for x in a if x % 2)
, el tipo iterador, cada vez que el tipo cualquiera le pregunta por el siguiente valor, no entrega sin pensar solo los valores del módulo. En cambio, este iterador juzga los valores él mismo y solo le entrega algo al gerente cuando hay algo que vale la pena entregar. Es decir, solo cuando descubre un valor impar (en cuyo caso no entrega 0
o 1
, sino True
). Aquí, el tipo iterador es como un desarrollador sénior competente que hace todo el trabajo, y el gerente puede relajarse y relajarse por completo (y al final del día aún se lleva todo el crédito).
Debería quedar claro que la segunda forma es mucho más eficiente, ya que no se comunican innecesariamente para cada... único... número de entrada. Especialmente porque su entrada a = [0] * 10000000
no contiene números impares. El desarrollador junior reporta diez millones de ceros al gerente que tiene que juzgarlos todos. Con un ida y vuelta constante entre ellos por cada cero. El desarrollador senior juzga todo él mismo y no informa nada a su gerente. Bueno, está bien, ambos desarrolladores al final también informan que han terminado, momento en el cual el administrador concluye que es False
como resultado de toda la expresión any(...)
).
El número de "verificación de falsedad" no es la razón real porque en una versión más rápida podemos ver una declaración if
que interna llama a bool()
. Esa comprobación se hace "por adelantado" en caso de que sea más rápido. Entonces, en ambos casos, Python tiene que pasar por todos los valores y verificar la veracidad de todos ellos .
El procedimiento que se muestra en la respuesta de Chepner es, de hecho, la respuesta a la pregunta. Busquemos cuándo se puede solicitar el siguiente elemento en el bucle for...:
En un caso más rápido, está justo después de BINARY_MODULO
, pero en la declaración POP_JUMP_IF_FALSE
tiene que hacer un poco de trabajo para verificar la veracidad ( if
llama a bool()
), mientras que en la versión más lenta no lo verifica allí. Hasta ahora (-1) punto para la versión más rápida. PERO en la versión más lenta, tiene que hacer tres pasos para llegar al punto de solicitar el siguiente elemento, YIELD_VALUE
, POP_TOP
, JUMP_ABSOLUTE
. Entonces (-3) para una versión más lenta... Esos tres pasos provocan la sobrecarga porque no se pueden omitir.
En otras palabras, la versión más rápida solo hace "verificación" para llegar al punto de solicitud del siguiente elemento, pero la versión más lenta tiene que hacer "verificación + esos pasos". Una vez más, ambos verifican la veracidad de todos los valores.
La respuesta es la sobrecarga de rendimiento.
El primer método envía todo a any()
mientras que el segundo solo envía a any()
cuando hay un número impar, por lo que any()
tiene menos elementos para pasar.
(x % 2 for x in a)
Este generador produce una serie de valores falsos hasta que produce un valor verdadero (si lo hace), momento en el que any
dejará de iterar el generador y devolverá True
.
(True for x in a if x % 2)
Este generador solo producirá exactamente un valor True
(si lo hace), momento en el que any
detendrá la iteración y devolverá True
.
El ir y venir adicional de ceder a any
y luego obtener el siguiente valor del generador en el primer caso representa la sobrecarga.
TL; DR La versión lenta tiene que iterar sobre una larga secuencia de valores falsos antes de devolver False
. La versión rápida "itera" sobre una secuencia vacía antes de hacer lo mismo. La diferencia es el tiempo que se tarda en construir la secuencia larga y falsa frente a la secuencia vacía.
Veamos el código de bytes generado por cada uno. He omitido la primera sección para cada uno, ya que son idénticos para ambos. Es solo el código de los generadores involucrados lo que necesitamos mirar.
In [5]: dis.dis('any(x%2 for x in a)') [...] Disassembly of <code object <genexpr> at 0x105e860e0, file "<dis>", line 1>: 1 0 LOAD_FAST 0 (.0) >> 2 FOR_ITER 14 (to 18) 4 STORE_FAST 1 (x) 6 LOAD_FAST 1 (x) 8 LOAD_CONST 0 (2) 10 BINARY_MODULO 12 YIELD_VALUE 14 POP_TOP 16 JUMP_ABSOLUTE 2 >> 18 LOAD_CONST 1 (None) 20 RETURN_VALUE In [6]: dis.dis('any(True for x in a if x % 2)') [...] Disassembly of <code object <genexpr> at 0x105d993a0, file "<dis>", line 1>: 1 0 LOAD_FAST 0 (.0) >> 2 FOR_ITER 18 (to 22) 4 STORE_FAST 1 (x) 6 LOAD_FAST 1 (x) 8 LOAD_CONST 0 (2) 10 BINARY_MODULO 12 POP_JUMP_IF_FALSE 2 14 LOAD_CONST 1 (True) 16 YIELD_VALUE 18 POP_TOP 20 JUMP_ABSOLUTE 2 >> 22 LOAD_CONST 2 (None) 24 RETURN_VALUE
Ambos son idénticos hasta la instrucción BINARY_MODULO
. Después de eso, la versión más lenta tiene que generar el valor resultante para que any
lo consuma antes de continuar, mientras que el segundo código pasa inmediatamente al siguiente valor. Básicamente, el código más lento tiene que consumir una larga lista de valores falsos (es decir, distintos de cero) para determinar que no hay valores verdaderos. El código más rápido solo necesita consumir una lista vacía.