Ist divmod() schneller als die Operatoren% und //?

Question

Ich erinnere mich aus Assembly, dass ganzzahlige Division Anweisungen sowohl den Quotienten als auch den Rest ergeben. Also, in Python wird die integrierte divmod() - Funktion leistungsfähiger als die Verwendung der Operatoren% und // (angenommen, natürlich benötigt man sowohl den Quotienten als auch den Rest)?

q, r = divmod(n, d) 
q, r = (n // d, n % d) 

Answer 1

zu messen ist (alle Timings auf einem Macbook Pro 2,8 GHz i7) zu wissen:

>>> import sys, timeit 
>>> sys.version_info 
sys.version_info(major=2, minor=7, micro=12, releaselevel='final', serial=0) 
>>> timeit.timeit('divmod(n, d)', 'n, d = 42, 7') 
0.1473848819732666 
>>> timeit.timeit('n // d, n % d', 'n, d = 42, 7') 
0.10324406623840332 

Die divmod() Funktion im Nachteil hier ist, weil Sie die globale jedes Mal nachschlagen müssen. Die Bindung an einen lokalen (alle Variablen in einer timeit Zeitfahren sind lokal) verbessert die Leistung ein wenig:

>>> timeit.timeit('dm(n, d)', 'n, d = 42, 7; dm = divmod') 
0.13460898399353027 

aber die Betreiber immer noch gewinnen, weil sie nicht den aktuellen Frame während einer Funktionsaufruf divmod() bewahren müssen ausgeführt: weise

>>> import dis 
>>> dis.dis(compile('divmod(n, d)', '', 'exec')) 
    1   0 LOAD_NAME    0 (divmod) 
       3 LOAD_NAME    1 (n) 
       6 LOAD_NAME    2 (d) 
       9 CALL_FUNCTION   2 
      12 POP_TOP    
      13 LOAD_CONST    0 (None) 
      16 RETURN_VALUE   
>>> dis.dis(compile('(n // d, n % d)', '', 'exec')) 
    1   0 LOAD_NAME    0 (n) 
       3 LOAD_NAME    1 (d) 
       6 BINARY_FLOOR_DIVIDE 
       7 LOAD_NAME    0 (n) 
      10 LOAD_NAME    1 (d) 
      13 BINARY_MODULO  
      14 BUILD_TUPLE    2 
      17 POP_TOP    
      18 LOAD_CONST    0 (None) 
      21 RETURN_VALUE   

die // und % Variante mehr Opcodes verwendet, aber die CALL_FUNCTION Bytecode ist ein Bär, Leistung.

---

In PyPy, für kleine ganze Zahlen gibt es nicht wirklich viel Unterschied; die kleinen Geschwindigkeitsvorteil der Opcodes haben schmilzt unter der schieren Geschwindigkeit von C Integer-Arithmetik weg:

>>>> import platform, sys, timeit 
>>>> platform.python_implementation(), sys.version_info 
('PyPy', (major=2, minor=7, micro=10, releaselevel='final', serial=42)) 
>>>> timeit.timeit('divmod(n, d)', 'n, d = 42, 7', number=10**9) 
0.5659301280975342 
>>>> timeit.timeit('n // d, n % d', 'n, d = 42, 7', number=10**9) 
0.5471200942993164 

(ich die Anzahl der Wiederholungen bis zu 1 Milliarde zu zeigen, wie klein der Unterschied wirklich ist, PyPy blazingly Kurbel hatte, ist schnell hier).

Wenn jedoch die Zahlen große, divmod()gewinnt von einem Land Meile erhalten:

>>>> timeit.timeit('divmod(n, d)', 'n, d = 2**74207281 - 1, 26', number=100) 
17.620037078857422 
>>>> timeit.timeit('n // d, n % d', 'n, d = 2**74207281 - 1, 26', number=100) 
34.44323515892029 

(ich jetzt musste Melodie unten die Anzahl der Wiederholungen um den Faktor 10 im Vergleich zu Hobbs 'Zahlen, nur um ein Ergebnis in einer angemessenen Zeit zu bekommen).

Dies liegt daran, dass PyPy diese ganzen Zahlen nicht mehr als C-Ganzzahlen auspacken kann;

>>>> timeit.timeit('divmod(n, d)', 'import sys; n, d = sys.maxint, 26', number=10**7) 
0.008622884750366211 
>>>> timeit.timeit('n // d, n % d', 'import sys; n, d = sys.maxint, 26', number=10**7) 
0.007693052291870117 
>>>> timeit.timeit('divmod(n, d)', 'import sys; n, d = sys.maxint + 1, 26', number=10**7) 
0.8396248817443848 
>>>> timeit.timeit('n // d, n % d', 'import sys; n, d = sys.maxint + 1, 26', number=10**7) 
1.0117690563201904 

Answer 2

Martijn Antwort richtig ist, wenn Sie mit „kleinen“ native ganzen Zahlen, wo arithmetische Operationen sind sehr schnell im Vergleich zu Funktionsaufrufen: Sie können zwischen der Verwendung von sys.maxint und sys.maxint + 1 den auffallenden Unterschied in Timings sehen. Doch mit bigints, es ist eine ganz andere Geschichte:

>>> import timeit 
>>> timeit.timeit('divmod(n, d)', 'n, d = 2**74207281 - 1, 26', number=1000) 
24.22666597366333 
>>> timeit.timeit('n // d, n % d', 'n, d = 2**74207281 - 1, 26', number=1000) 
49.517399072647095 

, wenn eine 22-Millionen-stellige Zahl teilt, divmod ist fast genau doppelt so schnell wie die Teilung und Modul separat zu tun, wie man erwarten könnte.

Auf meiner Maschine tritt die Frequenzweiche irgendwo um 2^63 auf, aber nehmen Sie mein Wort dafür nicht. Wie Martijn sagt, messen Sie! Wenn Leistung wirklich wichtig ist, darf man nicht davon ausgehen, dass das, was an einem Ort wahr ist, in einem anderen noch wahr ist.