python - ¿Es divmod() más rápido que usar los operadores% y//?

performance division

Question

Recuerdo del ensamblaje que las instrucciones de división de enteros producen tanto el cociente como el resto. Entonces, en python, ¿la función divmod () incorporada tendrá un mejor rendimiento que el uso de los operadores% y // (supongamos que uno necesita tanto el cociente como el resto)?

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

Answer 1

La respuesta de Martijn es correcta si está utilizando enteros nativos "pequeños", donde las operaciones aritméticas son muy rápidas en comparación con las llamadas a funciones. Sin embargo, con bigints, es una historia completamente diferente:

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

cuando se divide un número de 22 millones de dígitos, divmod es casi exactamente el doble de rápido que hacer la división y el módulo por separado, como es de esperar.

En mi máquina, el cruce se produce en algún lugar alrededor de 2 ^ 63, pero no confíes en mi palabra. Como dice Martijn, ¡mida! Cuando el desempeño realmente importa, no asuma que lo que se mantuvo en un lugar seguirá siendo cierto en otro.

Answer 2

Medir es saber (todos los tiempos en una 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 función divmod() está en desventaja aquí porque necesita buscar el global cada vez. Vincularlo a un local (todas las variables en un timeit tiempo son locales) mejora un poco el rendimiento:

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

pero los operadores aún ganan porque no tienen que preservar el marco actual mientras se ejecuta una llamada de función a divmod() :

>>> 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 // y % usa más CALL_FUNCTION , pero el bytecode CALL_FUNCTION es un oso, en cuanto a rendimiento.

En PyPy, para los enteros pequeños no hay mucha diferencia; La pequeña ventaja de la velocidad de los códigos de operación se derrite bajo la velocidad absoluta de la aritmética de enteros C:

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

(Tuve que aumentar el número de repeticiones hasta 1 billón para mostrar cuán pequeña es realmente la diferencia, PyPy es increíblemente rápido aquí).

Sin embargo, cuando los números se vuelven grandes , divmod() gana por una milla de país :

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

(Ahora tenía que reducir la cantidad de repeticiones por un factor de 10 en comparación con los números de hobbs, solo para obtener un resultado en un tiempo razonable).

Esto se debe a que PyPy ya no puede desempaquetar esos enteros como enteros C; Puede ver la notable diferencia en los tiempos entre el uso de sys.maxint y sys.maxint + 1 :

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