¿Es más rápido que% cuando se buscan números impares?

Question

Para verificar el entero par e impar, ¿es la comprobación de bit más baja más eficiente que usar el módulo?

>>> def isodd(num): 
     return num & 1 and True or False 

>>> isodd(10) 
False 
>>> isodd(9) 
True 

Answer 1

Yep. El módulo timeit en la biblioteca estándar es cómo verificar esas cosas. Por ejemplo:

AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x & 1' 'isodd(9)' 
1000000 loops, best of 3: 0.446 usec per loop 
AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x & 1' 'isodd(10)' 
1000000 loops, best of 3: 0.443 usec per loop 
AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x % 2' 'isodd(10)' 
1000000 loops, best of 3: 0.453 usec per loop 
AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x % 2' 'isodd(9)' 
1000000 loops, best of 3: 0.461 usec per loop 

Como se ve, en mi (primer día de edad == == lento ;-) Macbook Air, la solución & es repetible entre 7 y 18 nanosegundos más rápido que la solución %.

timeit no sólo te dice lo que es más rápido, pero por la cantidad de (basta con ejecutar las pruebas de unas pocas veces), que por lo general muestra cómo sumamente poco importante que es (¿verdad realmente cuidado diferencia de unos 10 nanosegundos, cuando la sobrecarga de llamar a la función es alrededor de 400?! -) ...

Convencer a los programadores de que las micro-optimizaciones son esencialmente irrelevantes ha demostrado ser una tarea imposible -a pesar de que han pasado 35 años (sobre qué computadoras han recibido órdenes de magnitud más rápido!) desde Knuth wrote

Debemos olvidarnos de las pequeñas eficiencias , digamos aproximadamente el 97% del tiempo : la optimización prematura es la raíz de todos los males.

que como explicó es una cita de una declaración aún más antigua de Hoare. ¡Creo que todos están totalmente convencidos de que SU CASO cae en el 3% restante!

Así que en lugar de repetir repetidas veces "no importa", nosotros (Tim Peters, en particular, merece los honores) poner en el módulo de biblioteca de Python estándar timeit, que hace que sea trivialmente fácil medir tales micro-referencias y por lo tanto ser titular al menos algunos programadores convencerse de que, hmmm, este caso se cae en el grupo de 97% -!)

Answer 2

Para ser totalmente honesto, no creo que importe.

El primer problema es la legibilidad. ¿Qué tiene más sentido para otros desarrolladores? Personalmente, esperaría un módulo al verificar la uniformidad/rareza de un número. Esperaría que la mayoría de los otros desarrolladores esperaran lo mismo. Al introducir un método diferente e inesperado, puede hacer que la lectura de códigos, y por lo tanto el mantenimiento, sea más difícil.

El segundo es simplemente un hecho que probablemente nunca tendrá un cuello de botella al hacer cualquiera de las dos operaciones. Estoy a favor de la optimización, pero la optimización temprana es lo peor que puedes hacer en cualquier idioma o entorno. Si, por algún motivo, determinar si un número es par o impar es un cuello de botella, entonces encuentre la forma más rápida de resolver el problema. Sin embargo, esto me lleva de vuelta a mi primer punto: la primera vez que escribe una rutina, debe escribirse de la manera más legible posible.

Answer 3

"return num & 1 and True or False"? Wah! Si está loco por la velocidad (1) "return num & 1" (2) en línea: if somenumber % 2 == 1 es legible Y late isodd(somenumber) porque evita la llamada a la función Python.

Answer 4

John plantea un buen punto.La sobrecarga real está en la llamada de función:

me@localhost ~> python -mtimeit -s'9 % 2' 
10000000 loops, best of 3: 0.0271 usec per loop 
me@localhost ~> python -mtimeit -s'10 % 2' 
10000000 loops, best of 3: 0.0271 usec per loop 

me@localhost ~> python -mtimeit -s'9 & 1' 
10000000 loops, best of 3: 0.0271 usec per loop 
me@localhost ~> python -mtimeit -s'9 & 1' 
10000000 loops, best of 3: 0.0271 usec per loop 

me@localhost ~> python -mtimeit -s'def isodd(x): x % 2' 'isodd(10)' 
1000000 loops, best of 3: 0.334 usec per loop 
me@localhost ~> python -mtimeit -s'def isodd(x): x % 2' 'isodd(9)' 
1000000 loops, best of 3: 0.358 usec per loop 

me@localhost ~> python -mtimeit -s'def isodd(x): x & 1' 'isodd(10)' 
1000000 loops, best of 3: 0.317 usec per loop 
me@localhost ~> python -mtimeit -s'def isodd(x): x & 1' 'isodd(9)' 
1000000 loops, best of 3: 0.319 usec per loop 

Curiosamente ambos métodos Remore al mismo tiempo sin la llamada de función.

Answer 5

La mejor optimización que puede obtener es no ponga la prueba en una función. 'number % 2' y 'número & 1' son formas muy comunes de verificar la imparidad/igualdad, los programadores experimentados reconocerán el patrón al instante, y siempre puedes enviar un comentario como '# si el número es impar, entonces blah blah blah' si realmente necesitas que sea obvio

# state whether number is odd or even 
if number & 1: 
    print "Your number is odd" 
else: 
    print "Your number is even" 

Answer 6

Aparte de la optimización del mal, que le quita el idiomática "var% 2 == 0" que cada codificador entiende sin mirar dos veces. Esto también viola pythons zen por muy poco aumento.

Además a = b y Verdadero o Falso ha sido sustituida por una mejor legibilidad por

retorno True si num & 1 de lo contrario False

Answer 7

sorprendió realmente ninguna de las respuestas anteriores hizo ambas variables de configuración (temporización literal es historia diferente) y no invocación de función (que obviamente oculta "términos más bajos"). Atascado en ese tiempo del timeit de ipython, donde obtuve el claro ganador x & 1 - mejor para ~ 18% usando python2.6 (~ 12% usando python3.1).

En mi muy antigua máquina:

$ python -mtimeit -s 'x = 777' 'x&1' 
10000000 loops, best of 3: 0.18 usec per loop 
$ python -mtimeit -s 'x = 777' 'x%2' 
1000000 loops, best of 3: 0.219 usec per loop 

$ python3 -mtimeit -s 'x = 777' 'x&1' 
1000000 loops, best of 3: 0.282 usec per loop 
$ python3 -mtimeit -s 'x = 777' 'x%2' 
1000000 loops, best of 3: 0.323 usec per loop 

Answer 8

utilizar Python 3.6 la respuesta es no . El uso del código de abajo en un MBP 2017 muestra que el uso de módulo es más rápido.

# odd.py 
from datetime import datetime 

iterations = 100_000_000 


def is_even_modulo(n): 
    return not n % 2 


def is_even_and(n): 
    return not n & 1 


def time(fn): 
    start = datetime.now() 
    for i in range(iterations, iterations * 2): 
     fn(i) 
    print(f'{fn.__name__}:', datetime.now() - start) 


time(is_even_modulo) 
time(is_even_and) 

le da a este resultado:

$ python3 -m odd 
is_even_modulo: 0:00:14.347631 
is_even_and: 0:00:17.476522 
$ python3 --version 
Python 3.6.1 

Como se ha sugerido en otras respuestas, las llamadas de función es una gran sobrecarga, sin embargo, la eliminación de módulo muestra que sigue siendo más rápido que el nivel de bits y en Python 3.6.1 :

# odd.py 
from datetime import datetime 

iterations = 100_000_000 


def time_and(): 
    start = datetime.now() 
    for i in range(iterations): 
     i & 1 
    print('&:', datetime.now() - start) 


def time_modulo(): 
    start = datetime.now() 
    for i in range(iterations): 
     i % 2 
    print('%:', datetime.now() - start) 


time_modulo() 
time_and() 

resultados:

$ python3 -m odd 
%: 0:00:05.134051 
&: 0:00:07.250571 

Bonificación: resulta que se necesita aproximadamente el doble de tiempo para ejecutar en Python 2.7.

$ time python2 -m odd 
('&:', '0:00:20.169402') 
('%:', '0:00:19.837755') 

real 0m41.198s 
user 0m39.091s 
sys 0m1.899s 
$ time python3 -m odd 
&: 0:00:11.375059 
%: 0:00:08.010738 

real 0m19.452s 
user 0m19.354s 
sys 0m0.042s