python timeit 函数是否可能将 0 报告为执行时间？

Question

我正在做一个项目，在这个项目中我们必须比较几种排序算法（插入排序、快速排序、归并排序...）对于大小为 2 到 2^16 的列表的执行时间。我的导师指出，由于现代计算机速度非常快，"small" 大小的运行时间可能根本不会注册并报告为 0。作为解决方案，建议对于小型实例我们运行算法在一个附加循环中计算总执行时间，然后将这个总时间除以循环重复次数。例如，

while(repeat test 20 times) 
        while(execute algorithm 50 times)
             run algorithm

我正在使用 Python timeit 函数按如下方式完成此操作

    setup = '''
gc.enable()
import random
from __main__ import insertionSort
from __main__ import n #current instance size
from __main__ import s #random array
    '''
    average = sum(timeit.Timer('A=s[:]; insertionSort(A);',setup = setup).repeat(20,50))/20

我为 n 到 32 的大小执行此操作，此时我通过执行

继续测试

average = sum(timeit.Timer('A=s[:]; insertionSort(A);',setup = setup).repeat(1,50))/50

我遇到的问题是，一旦超过 32，平均值就会下降

Averages for size 2^ 1
Insertion Sort Average:  0.00014180380003381288
Averages for size 2^ 2
Insertion Sort Average:  0.0002706763001697254
Averages for size 2^ 3
Insertion Sort Average:  0.0005087433502012573
Averages for size 2^ 4
Insertion Sort Average:  0.0018256775000736526
Averages for size 2^ 5
Insertion Sort Average:  0.006701907949900487
Averages for size 2^ 6
Insertion Sort Average:  0.00045550270002422624 #smaller average for larger instance?!

所以我想我的问题是- 是否需要额外重复较小的实例？我尝试对大小为 2 的单次执行计时，得到的数字非常接近 0 (x10^-6)，但实际上从未得到零。

Answer 1

我尝试了一些实验，这似乎是必要的——不是为了避免 0 次，而是为了分摊一些开销。这是一个典型的例子，pass命令的退化情况：

>>> for n in range(9):
...   timeit.timeit("pass", number=10**n)/(10**n)
... 
3.0994415283203125e-06
1.9073486328125001e-07
5.0067901611328123e-08
3.6001205444335936e-08
3.3092498779296877e-08
3.4611225128173827e-08
1.6702890396118163e-08
1.2709689140319825e-08
1.1296820640563965e-08

这表明开销约为 3 微秒，执行时间约为 11 纳秒。

python timeit 函数是否可能将 0 报告为执行时间？

Is it possible for the python timeit function to ever report 0 as the execution time?

python

algorithm

timeit

insertion-sort