python的`timeit`并不总是与数字线性对比？

Question

我在16GB,2.7GHz i5,OSX 10.11.5机器上运行Python 2.7.10.

我在许多不同类型的例子中多次观察到这种现象,所以下面的例子虽然有点人为,但具有代表性.这正是我今天早些时候正在努力的事情,当我的好奇心终于被激起时.

>>> 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,然后是从1e4到1e5的因子2(所以从1e3到1e5的总因数为100,这是预期的).

我认为必须在实际的过程中进行某种基于缓存的优化,无论是在实际的过程中还是在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.

我可以做更多临时数据收集,但此时我还没有考虑过假设.

关于为什么非线性标度在某些中间运行次数的任何概念？

Answer 1

这与较少数量的运行不足以获得您想要的定时分辨率有关.

当您增加运行次数时,时间之间的比率接近运行次数之间的比率:

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