重构计算排序算法的运行时间 - python

Question

我写这个来计算排序算法的平均运行时间， ，我只是好奇，如果有一种方法来重构这个更简单或更好。

time = [] 
for i in range(3): 
    start = timeit.default_timer() 
    insert_list = [] 
    for i in range(3000): 
     insert_list.append(randint(0,5000)) 
    sorted_list = merge_sort(insert_list) 
    stop = timeit.default_timer() 
    time.append(stop - start) 
print sum(time) /len(time) 

Answer 1

尝试使用datetime来测量算法的运行时间。

datetime.datetime了），如果你选择使用datetime.datetime.now（也可以使用微秒属性

from datetime import datetime 
    startTime = datetime.now() 
    #CODE 
    print("Time taken:",datetime.now() - startTime) 

Answer 2

首先，你必须移动for i in range(3000)周期的时间测量之外。这不是排序，所以你实际测量数据集的人口。而且由于使用了随机数，它将高度依赖于熵源的速度（例如/ dev/random，/ dev/urandom或类似），在某些配置中它可能非常缓慢（例如，虚拟机开启共享主机或云中）。这与排序算法的速度无关。

time = [] 
for i in range(3): 
    insert_list = [] 
    for i in range(3000): 
     insert_list.append(randint(0,5000)) 
    start = timeit.default_timer() 
    sorted_list = merge_sort(insert_list) 
    stop = timeit.default_timer() 
    time.append(stop - start) 
print sum(time) /len(time) 

其次，不是那么重要，这个定时器（以便time.time() & datetime.now()）可以给在时区的变化，夏令，NTP时间调整等，这是更好地使用monotonic.monotonic()的情况下意外的结果，它使用如果可能的话，操作系统是单调时间的来源。虽然，这是一个外部图书馆，而不是内建的。

time = [] 
for i in range(3): 
    insert_list = [] 
    for i in range(3000): 
     insert_list.append(randint(0,5000)) 
    start = monotonic.monotonic() 
    sorted_list = merge_sort(insert_list) 
    stop = monotonic.monotonic() 
    time.append(stop - start) 
print sum(time) /len(time) 

第三，如果单独测量每个呼叫，测量结果可能会受到外部环境的影响。例如太小的数据集上的算法太快，这将导致由于时钟精度导致的测量舍入。相反，使N个呼叫排序并测量整个周期的时间。然后将总时间除以操作次数。这是以内存为代价的，因为你必须事先准备好所有N个数组。

N = 3 
dataset = [] 
for i in range(N): 
    insert_list = [] 
    for i in range(3000): 
     insert_list.append(randint(0,5000)) 
    dataset.append(insert_list) 
start = monotonic.monotonic() 
for insert_list in dataset: 
    sorted_list = merge_sort(insert_list) 
stop = monotonic.monotonic() 
print (stop - start)/N 

四，为什么不使用timeit.timeit()函数？

N = 3 
dataset = [[randint(0, 5000) for j in range(3000)] for i in range(N)] 
print(timeit.timeit(lambda: merge_sort(dataset.pop()), number=N))