Является ли divmod() быстрее, чем с помощью операторов% и //?

Question

Я помню из сборки, что целые инструкции деления дают как фактор, так и остаток. Таким образом, в python встроенная функция divmod() будет лучше по производительности, чем использование операторов% и // (предположим, конечно, нужно как частное, так и остальное)?

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

Answer 1

Для измерения нужно знать (все тайминги на Macbook Pro с тактовой частотой 2,8 ГГц 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 

divmod() функция находится в невыгодном положении, потому что здесь нужно искать глобальный каждый раз. Связывание его локального (все переменные в timeit время судебного разбирательства являются локальными) повышает производительность немного:

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

но операторы еще выиграть, потому что они не должны сохранить текущий кадр во время вызова функции к 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   

вариант // и % использует больше опкоды, но CALL_FUNCTION байткодом медведь, производительность мудрым.

В PyPy для небольших целых чисел на самом деле нет большой разницы; малая скорость преимущество в опкодах есть тает под чистой скоростью 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 

(мне пришлось провернуть количество повторений до 1 млрд показать, насколько мала разница на самом деле, PyPy является невероятно быстро здесь).

Однако, когда числа получают большой, divmod()выигрывает милей страны:

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

(теперь я должен был настроить вниз число повторений по 10 раз по сравнению с hobbs ', просто чтобы получить результат в разумные сроки).

Это потому, что PyPy больше не может удалить эти целые числа в виде целых чисел C; вы можете увидеть поразительную разницу в таймингах между использованием sys.maxint и 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 

Answer 2

Мартейн является правильным, если вы используете «маленькие» родные целые числа, где арифметические операции очень быстро по сравнению с вызовами функций. Тем не менее, с bigints, это совершенно другая история:

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

при делении 22 миллионов цифр, divmod почти ровно в два раза быстрее, чем делать деление и модуль отдельно, как можно было бы ожидать.

На моей машине кроссовер встречается где-то около 2^63, но не смирился с этим. Как говорит Мартин, измерьте! Когда производительность действительно имеет значение, не думайте, что то, что было верно в одном месте, по-прежнему будет истинным в другом.