Python `timeit` не всегда линейно масштабируется с числом?

Я запускаю Python 2.7.10 на машине i5 с тактовой частотой 16 ГБ, 2,7 ГГц и OSX 10.11.5.

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

>>> timeit('unicodedata.category(chr)', setup = 'import unicodedata, random; chr=unichr(random.randint(0,50000))', number=100)
3.790855407714844e-05
>>> timeit('unicodedata.category(chr)', setup = 'import unicodedata, random; chr=unichr(random.randint(0,50000))', number=1000)
0.0003371238708496094
>>> timeit('unicodedata.category(chr)', setup = 'import unicodedata, random; chr=unichr(random.randint(0,50000))', number=10000)
0.014712810516357422
>>> timeit('unicodedata.category(chr)', setup = 'import unicodedata, random; chr=unichr(random.randint(0,50000))', number=100000)
0.029777050018310547
>>> timeit('unicodedata.category(chr)', setup = 'import unicodedata, random; chr=unichr(random.randint(0,50000))', number=1000000)
0.21139287948608398

Вы заметите, что от 100 до 1000, как и ожидалось, время увеличивается в 10 раз. Однако от 1e3 до 1e4 это больше похоже на множитель 50, а затем на множитель 2 от 1e4 до 1e5 (так что общий множитель 100 от 1e3 до 1e5, что и ожидается).

Я полагал, что должна происходить какая-то оптимизация на основе кеширования либо в фактическом синхронизируемом процессе, либо в самом timeit, но я не могу понять эмпирически так, так ли это. Импорт, похоже, не имеет значения, как это можно увидеть на простейшем примере:

>>> timeit('1==1', number=10000)
0.0005490779876708984
>>> timeit('1==1', number=100000)
0.01579904556274414
>>> timeit('1==1', number=1000000)
0.04653501510620117

где от 1e4 до 1e6 истинная разница во времени равна 1e2, но промежуточные шаги составляют ~ 30 и ~ 3.

Я мог бы собирать больше специальных данных, но на данный момент у меня нет гипотезы.

Любое представление о том, почему нелинейная шкала при определенных промежуточных количествах прогонов?


python optimization performance timeit
person gmoss    schedule 27.09.2016    source источник
comment
У меня нет для вас конкретного ответа, но в такие короткие сроки трудно точно знать, что еще может происходить в среде (на вашем компьютере), что вызывает колебания во времени ...   -  person mgilson    schedule 27.09.2016
comment
Просто запустите timeit('1==1', number=10000) несколько раз и наблюдайте за колебаниями. Вы в основном наблюдаете за шумом. Ваш процесс может быть вытеснен другим процессом, или разрешение таймера может быть недостаточно высоким для точного определения таких коротких времен.   -  person Sven Marnach    schedule 27.09.2016

Ответы (1)


arrow_upward
8
arrow_downward

Это связано с тем, что меньшее количество прогонов недостаточно точно для получения желаемого разрешения по времени.

По мере увеличения количества запусков соотношение между временами приближается к соотношению между количеством запусков:

>>> def timeit_ratio(a, b):
...     return timeit('unicodedata.category(chr)', setup = 'import unicodedata, random; chr=unichr(random.randint(0,50000))', number=a) / timeit('unicodedata.category(chr)', setup = 'import unicodedata, random; chr=unichr(random.randint(0,50000))', number=b)
>>> for i in range(32):
...   r = timeit_ratio(2**(i+1), 2**i)
...   print 2**i, 2**(i+1), r, abs(r - 2)**2  # mean squared error
...
1 2 3.0 1.0
2 4 1.0 1.0
4 8 1.5 0.25
8 16 1.0 1.0
16 32 0.316455696203 2.83432142285
32 64 2.04 0.0016
64 128 1.97872340426 0.000452693526483
128 256 2.05681818182 0.00322830578512
256 512 1.93333333333 0.00444444444444
512 1024 2.01436781609 0.000206434139252
1024 2048 2.18793828892 0.0353208004422
2048 4096 1.98079658606 0.000368771106961
4096 8192 2.11812990721 0.0139546749772
8192 16384 2.15052027269 0.0226563524921
16384 32768 1.93783596324 0.00386436746641
32768 65536 2.28126901347 0.0791122579397
65536 131072 2.18880312306 0.0356466192769
131072 262144 1.8691643357 0.0171179710535
262144 524288 2.02883451562 0.000831429291038
524288 1048576 1.98259818317 0.000302823228866
1048576 2097152 2.088684654 0.00786496785554
2097152 4194304 2.02639479643 0.000696685278755
4194304 8388608 1.98014042724 0.000394402630024
8388608 16777216 1.98264956218 0.000301037692533
person Claudiu    schedule 27.09.2016
comment
С этим не поспоришь. (Приму ответ через несколько минут, как только SO позволит мне это сделать) - person gmoss; 27.09.2016