Ist & bei der Prüfung auf ungerade Zahlen schneller als %?

Question

Ist die Prüfung auf gerade und ungerade Zahlen mit dem niedrigsten Bit effizienter als mit dem Modulo-Prinzip?

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

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

Answer 1

Mit Python 3.6 lautet die Antwort keine . Die Verwendung des unten stehenden Codes 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)

Ergibt 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 angedeutet, sind die Funktionsaufrufe ein großer Overhead, jedoch zeigt das Entfernen, dass modulo immer noch schneller ist als bitweise 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 die Ausführung in Python 2.7 etwa doppelt so lange dauert.

$ 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

Answer 2

Abgesehen von der bösen Optimierung nimmt es das sehr idiomatische "var % 2 == 0" weg, das jeder Programmierer versteht, ohne zweimal hinzusehen. Dies ist also ein Verstoß gegen Pythons Zen für einen sehr geringen Gewinn.

Außerdem wurde a = b und True or False zur besseren Lesbarkeit ersetzt durch

return True if num & 1 else False

Answer 3

Ich war wirklich überrascht, dass keine der obigen Antworten sowohl das Einrichten von Variablen (wörtliches Timing ist eine andere Geschichte) als auch keinen Funktionsaufruf (der offensichtlich "niedrigere Terme" ausblendet) berücksichtigt hat. Ich habe mich an das Timing von ipython's timeit gehalten, wo ich einen klaren Gewinner x&1 hatte - besser für ~18% mit python2.6 (~12% mit python3.1).

Auf meinem sehr alten Rechner:

$ 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 4

Aktualisieren der Ergebnisse für die neueste Python-Version, % ist schneller als &

  python -m timeit -s 'def isodd(x): x & 1' 'isodd(9)'
5000000 loops, best of 5: 78.4 nsec per loop
  python -m timeit -s 'def isodd(x): x & 1' 'isodd(10)'
5000000 loops, best of 5: 79.6 nsec per loop
  python -m timeit -s 'def isodd(x): x % 2' 'isodd(9)'
5000000 loops, best of 5: 65.8 nsec per loop
  python -m timeit -s 'def isodd(x): x % 2' 'isodd(10)'
5000000 loops, best of 5: 68.5 nsec per loop