Подтвердить что ты не робот

Почему более скорое число мод на python вызывается с показателями экспоненты?

Я пытался оптимизировать программу, с которой я возился, когда заметил, что выполнение value = i % 65536 оказалось медленным, а затем value = i % (2**16).

Чтобы проверить это, я запустил следующую программу:

import cProfile
import pstats

AMOUNT = 100000000

def test1():
    for i in xrange(AMOUNT):
        value = i % 65536
    return

def test2():
    for i in xrange(AMOUNT):
        value = i % (256**2)
    return

def test3():
    for i in xrange(AMOUNT):
        value = i % (16**4)
    return

def test4():
    for i in xrange(AMOUNT):
        value = i % (4**8)
    return

def test5():
    for i in xrange(AMOUNT):
        value = i % (2**16)
    return

def run_tests():
    test1()
    test2()
    test3()
    test4()
    test5()
    return

if __name__ == '__main__':
    cProfile.run('run_tests()', 'results')
    stats = pstats.Stats('results')
    stats.sort_stats('calls', 'nfl')
    stats.print_stats()

... который произвел следующий вывод:

Fri May 11 15:11:59 2012    results

         8 function calls in 40.473 seconds

   Ordered by: call count, name/file/line

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000   40.473   40.473 <string>:1(<module>)
        1    0.000    0.000   40.473   40.473 test.py:31(run_tests)
        1   10.466   10.466   10.466   10.466 test.py:6(test1)
        1    7.475    7.475    7.475    7.475 test.py:11(test2)
        1    7.485    7.485    7.485    7.485 test.py:16(test3)
        1    7.539    7.539    7.539    7.539 test.py:21(test4)
        1    7.508    7.508    7.508    7.508 test.py:26(test5)

Использование 65536 было самым медленным на 10.466 секунд, тогда как 256**2 было самым быстрым на 7,475 секунды (с другими возможными значениями экспоненты, находящимися между ними). Разумеется, эта разница в скорости заметна только при большом количестве повторений, но мне все еще интересно, почему это происходит.

Почему количество мод на 65536 медленнее, чем при использовании мода, используя экспоненты? Они должны оценивать один и тот же номер, и я бы подумал, что интерпретатору python потребуется больше времени, чтобы полностью оценить экспоненты, прежде чем принимать мода.

Как правило, более эффективно использовать полномочия двух в выражениях python, а не полностью набирать номер? И этот шаблон справедлив для операций, кроме модуля или других чисел, кроме 2?

(Кстати, я использую Python 2.7.2 (32 бит), и я запустил выше на 64-битном ноутбуке Windows 7).

EDIT:
Поэтому я попытался изменить порядок функций, которые я называю, и теперь обратное верно. Похоже, что первая функция в run_tests всегда будет работать медленнее при использовании cProfile, что странно. Итак, урок, я думаю, - профайлеры странны: D

4b9b3361

ОТВЕТЫ

Ответ 1

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

>>> import dis
>>> dis.dis(test1)
  2           0 SETUP_LOOP              30 (to 33)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_GLOBAL              1 (AMOUNT)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                16 (to 32)
             16 STORE_FAST               0 (i)

  3          19 LOAD_FAST                0 (i)
             22 LOAD_CONST               1 (65536)
             25 BINARY_MODULO       
             26 STORE_FAST               1 (value)
             29 JUMP_ABSOLUTE           13
        >>   32 POP_BLOCK           

  4     >>   33 LOAD_CONST               0 (None)
             36 RETURN_VALUE        
>>> dis.dis(test5)
  2           0 SETUP_LOOP              30 (to 33)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_GLOBAL              1 (AMOUNT)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                16 (to 32)
             16 STORE_FAST               0 (i)

  3          19 LOAD_FAST                0 (i)
             22 LOAD_CONST               3 (65536)
             25 BINARY_MODULO       
             26 STORE_FAST               1 (value)
             29 JUMP_ABSOLUTE           13
        >>   32 POP_BLOCK           

  4     >>   33 LOAD_CONST               0 (None)
             36 RETURN_VALUE

(ну на самом деле есть разница: число хранится при разных смещениях в таблице констант. Я не могу себе представить, что это может вызвать какую-либо разницу).

Для полноты, здесь правильный тест, который использует модуль timeit:

import timeit

setup = "i = 1337"

best1 = best2 = float("inf")
for _ in range(5000):
  best1 = min(best1, timeit.timeit("i % 65536", setup=setup, number=10000))
for _ in range(5000):
  best2 = min(best2, timeit.timeit("i % (2**16)", setup=setup, number=10000))
print best1
print best2

Обратите внимание, что я измеряю минимальное время, а не среднее. Если по какой-то причине это занимает больше времени, это просто означает, что он прерывался чаще (потому что код не зависит ни от чего, кроме мощности вашего процессора).

Ответ 2

Hmmm, используя dis, чтобы показать коды байтов python, показывает, что функции идентичны. Python оптимизировал константу (как и ожидалось). Поэтому я подозреваю, что разница во времени - это кеширующие эффекты. Тайминги на моем ноутбуке несут это (используя Python 2.7.3 64 бит на Linux)

Fri May 11 23:37:49 2012    results

     8 function calls in 38.825 seconds

Ordered by: call count, name/file/line

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     1    0.000    0.000   38.825   38.825 <string>:1(<module>)
     1    0.000    0.000   38.825   38.825 z.py:31(run_tests)
     1    7.880    7.880    7.880    7.880 z.py:6(test1)
     1    7.658    7.658    7.658    7.658 z.py:11(test2)
     1    7.806    7.806    7.806    7.806 z.py:16(test3)
     1    7.784    7.784    7.784    7.784 z.py:21(test4)
     1    7.697    7.697    7.697    7.697 z.py:26(test5)

Все в значительной степени идентичны

>>> from dis import dis
>>> def test1():
...     for i in xrange(AMOUNT):
...         value = i % 65536
...     return
... 
>>> def test5():
...     for i in xrange(AMOUNT):
...         value = i % (2**16)
...     return
... 
>>> dis(test1)
  2           0 SETUP_LOOP              30 (to 33)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_GLOBAL              1 (AMOUNT)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                16 (to 32)
             16 STORE_FAST               0 (i)

  3          19 LOAD_FAST                0 (i)
             22 LOAD_CONST               1 (65536)
             25 BINARY_MODULO       
             26 STORE_FAST               1 (value)
             29 JUMP_ABSOLUTE           13
        >>   32 POP_BLOCK           

  4     >>   33 LOAD_CONST               0 (None)
             36 RETURN_VALUE        
>>> dis(test5)
  2           0 SETUP_LOOP              30 (to 33)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_GLOBAL              1 (AMOUNT)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                16 (to 32)
             16 STORE_FAST               0 (i)

  3          19 LOAD_FAST                0 (i)
             22 LOAD_CONST               3 (65536)
             25 BINARY_MODULO       
             26 STORE_FAST               1 (value)
             29 JUMP_ABSOLUTE           13
        >>   32 POP_BLOCK           

  4     >>   33 LOAD_CONST               0 (None)
             36 RETURN_VALUE        
>>>

Ответ 3

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

>>> timeit.timeit('for i in range(10000): i % 65536', number=1000)
0.8686108589172363
>>> timeit.timeit('for i in range(10000): i % 256**2', number=1000)
0.862062931060791
>>> timeit.timeit('for i in range(10000): i % 4**8', number=1000)
0.8644928932189941
>>> timeit.timeit('for i in range(10000): i % 2**16', number=1000)
0.8643178939819336
>>> timeit.timeit('for i in range(10000): i % 65536', number=1000)
0.8640358448028564

Вы можете видеть, что среднее значение всегда равно 0.864.