È divmod() più veloce rispetto all'utilizzo degli operatori% e //?

Question

Ricordo dal montaggio che le istruzioni di divisione intera producono sia il quoziente che il resto. Quindi, in python la funzione integrata divmod() sarà migliore per le prestazioni rispetto all'uso degli operatori% e // (supponiamo naturalmente che sia necessario il quoziente e il resto)?

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

Answer 1

Per misurare è sapere (tutti i tempi su un MacBook Pro 2.8Ghz i7):

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

La funzione divmod() è in svantaggio qui perché è necessario guardare il ogni volta globale. Legandola ad un locale (tutte le variabili in una prova timeit ora sono locali) migliora le prestazioni un po ':

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

ma gli operatori ancora vincere, perché non c'è bisogno di preservare il frame corrente, mentre una chiamata di funzione per divmod() viene eseguito:

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

la variante // e % utilizza più codici operativi, ma il bytecode CALL_FUNCTION è un orso, prestazioni saggio.

---

In PyPy, per i numeri interi piccoli non c'è davvero molta differenza; il piccolo vantaggio di velocità i codici operativi hanno scioglie sotto la velocità pura di C aritmetica intera:

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

(ho dovuto alzare il numero di ripetizioni fino a 1 miliardo per mostrare quanto piccola la differenza è davvero, PyPy è incredibilmente veloce qui).

Tuttavia, quando i numeri diventano grande, divmod()vittorie da un miglio di paese:

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

(ora avevo a sintonizzare giù il numero di ripetizioni di un fattore 10 rispetto al numeri di hobbs, solo per ottenere un risultato in un ragionevole lasso di tempo).

Ciò è dovuto al fatto che PyPy non è più in grado di annullare l'estrazione di tali interi come numeri interi C; si può vedere la notevole differenza di tempi tra l'utilizzo sys.maxint e sys.maxint + 1: risposta

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

di Martijn è corretta se si sta utilizzando "piccoli" interi nativi, in cui le operazioni aritmetiche sono molto veloce rispetto alle chiamate di funzione. Tuttavia, con bigints, è una storia completamente diversa:

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

quando la divisione di un numero di 22 milioni di cifre, divmod è quasi esattamente due volte più veloce di fare la divisione e il modulo a parte, come ci si potrebbe aspettare.

Sulla mia macchina, il crossover si verifica da qualche parte intorno a 2^63, ma non credetemi. Come dice Martijn, misura! Quando le prestazioni sono davvero importanti, non dare per scontato che ciò che è vero in un posto sarà ancora vero in un altro.