Ist bei der Suche nach ungeraden Zahlen & schneller als%?

Question

Um nach ungeraden und geraden Integer zu suchen, ist das niedrigste Bit effizienter als die Verwendung des Modulo?

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

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

Answer 1

Ja. Das timeit Modul in der Standardbibliothek ist, wie Sie diese Dinge überprüfen. Z. B:

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 

Wie Sie sehen, auf meinem (ersten Tag == == alt langsam ;-) Macbook Air, die & Lösung ist wiederholbar zwischen 7 und 18 ns schneller als die % Lösung.

timeit sagt Ihnen nicht nur, was schneller ist, sondern davon, wie viel (nur die Tests ein paar Mal laufen), die in der Regel zeigt, wie höchst unwichtige es (tun Sie wirklich Pflege etwa 10 ns Unterschied, wenn der Kopf der Aufruf der Funktion ist etwa 400?! -) ...

Überzeugende Programmierer, dass Mikro-Optimierungen im Wesentlichen irrelevant sind, hat sich als eine unmögliche Aufgabe erwiesen - obwohl es 35 Jahre ist (über die Computer haben Bestellungen von Betrag schneller!) seit Knuth wrote

Wir sollten über kleine Wirkungsgrade vergessen, sagen etwa 97% der Zeit: vorzeitige Optimierung ist die Wurzel aller Übel.

was wie er erklärt ist ein Zitat aus einer noch älteren Aussage von Hoare. Ich denke jeder ist total davon überzeugt, dass IHR Fall in die restlichen 3% fällt!

Also anstatt endlos zu wiederholen "es ist egal", setzen wir (Tim Peters insbesondere verdient die Ehrungen dort) in das Standard-Python-Bibliotheksmodul timeit, das macht es einfach, solche Mikro-Benchmarks und damit zu messen lets mindestens einige Programmierer überzeugen sich, dass, hmmm, ist dieser Fall fällt in die 97% Gruppe! -)

Answer 2

Um ganz ehrlich zu sein, ich glaube nicht, es darauf ankommt.

Das erste Problem ist Lesbarkeit. Was macht für andere Entwickler mehr Sinn? Ich persönlich würde einen Modulo erwarten, wenn ich die Ebenheit einer Zahl überprüfe. Ich würde erwarten, dass die meisten anderen Entwickler dasselbe erwarten würden. Wenn Sie eine andere und unerwartete Methode einführen, können Sie das Lesen von Code und damit die Wartung erschweren.

Die zweite ist nur eine Tatsache, dass Sie wahrscheinlich nie einen Engpass haben werden, wenn Sie beide Operationen durchführen. Ich bin für die Optimierung, aber frühe Optimierung ist das Schlimmste, was Sie in jeder Sprache oder Umgebung tun können. Wenn Sie aus irgendeinem Grund feststellen, ob eine Zahl gerade oder ungerade ist, dann suchen Sie den schnellsten Weg, um das Problem zu lösen. Das bringt mich jedoch zu meinem ersten Punkt zurück - das erste Mal, wenn Sie eine Routine schreiben, sollte sie so lesbar wie möglich geschrieben werden.

Answer 3

"Rücksendenummer & 1 und True oder False"? Wah! Wenn Sie speed-verrückt sind (1) "Return-Nummer & 1" (2) Inline es: if somenumber % 2 == 1 ist lesbar UND schlägt isodd(somenumber), weil es den Python-Funktionsaufruf vermeidet.

Answer 4

John bringt einen guten Punkt.Der eigentliche Aufwand ist in den Funktionsaufruf:

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 

Interessanter beide Methoden Remore gleichzeitig ohne Funktionsaufruf.

Answer 5

Die beste Optimierung, die Sie erhalten können, ist nicht setzen Sie den Test in eine Funktion. 'number % 2' und 'Nummer & 1' sind sehr häufige Arten der Überprüfung der Ungerade/Ebenheit, erfahrene Programmierer werden das Muster sofort erkennen, und Sie können immer einen Kommentar wie '# wenn Nummer ist ungerade, dann bla bla bla' if Du brauchst es wirklich, um offensichtlich zu sein.

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

Answer 6

Neben der bösen Optimierung, nimmt es das idiomatische „var% 2 == 0“ weg, dass jeder Codierer zweimal ohne einen Blick versteht. Das ist also auch gegen Pythons Zen für sehr wenig Gewinn verletzt.

Weiterhin a = b und Wahr oder Falsch zur besseren Lesbarkeit wurde von

abgelöst

return true, wenn num & 1 sonst Falsch

Answer 7

war wirklich überrascht, keine der oben genannten Antworten sowohl variable Setup tat (wörtliche Zeit ist eine andere Geschichte) und kein Funktionsaufruf (der offensichtlich "niedrigere Begriffe" verbirgt). Stuck auf dieses Timing von Ipython's Timeit, wo ich klar Gewinner x & 1 bekam - besser für ~ 18% mit Python2.6 (~ 12% mit Python3.1).

Auf meiner sehr alte Maschine:

$ 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

Verwendung von Python 3.6 ist die Antwort keine. Die Verwendung des folgenden Code auf einem MBP 2017 zeigt, dass die Verwendung von Modulo schneller ist.

# 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) 

gibt dieses Ergebnis:

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

Wie in anderen Antworten vorgeschlagen, ruft die Funktion ein großer Aufwand ist es jedoch zeigt das Entfernen dass Modulo als bitweise noch schneller und in 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() 

Ergebnisse:

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

Bonus: Es stellt sich heraus, dass dies ungefähr doppelt so lange dauert wie in 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