pythonの `timeit`は常に数値で直線的に拡大するとは限りませんか？

Question

私はPython 2.7.10を、16GB、2.7GHzのi5、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倍、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