为什么我的代码对2个列表的排序比4个列表的排序要长1000倍

Question

我正在尝试计算selectionsort代码对长度为2^I的列表进行排序所需的时间，但由于某些原因，排序2^1所需的时间要比排序2^2所需的时间长

import random
import time

def selectionsort(mylist):
    sortedlist=[]
    while len(mylist) > 0:
        lowest = mylist[0]
        for i in mylist:
            if i < lowest:
                lowest=i
        sortedlist.append(lowest)
        mylist.remove(lowest)
    return sortedlist

mylist = []
ivalues = []
sorttimelist = []
for i in range(2):
    ivalues.append(2**i)
    for x in range(2**i):
        mylist.append(random.random())
    start_time=time.perf_counter()
    selectionsort(mylist)
    end_time=time.perf_counter()
    sorttime=end_time-start_time
    sorttimelist.append(sorttime)
    mylist.clear()
print(sorttimelist)

使用打印只是为了测试它是否正常运行

Answer 1

像这样的测试，只有一次测试迭代和如此小的数据量，是没有意义的。我的猜测是，第一个测试是“预热”系统，因此需要更长的时间。因此，第二次运行的任何测试都会更快

我增强了您的代码，使每个测试运行10000次，总共是单个测试的次数。当我这样做时，第二个数字每次运行时都比第一个大。以下是新的测试代码：

sorttimelist = []
for i in range(2):
    total_time = 0
    for iter in range(10000):
        mylist = []
        for x in range(2 ** i):
            mylist.append(random.random())
        start_time = time.perf_counter()
        selectionsort(mylist)
        end_time = time.perf_counter()
        sorttime = end_time - start_time
        total_time += sorttime
        mylist.clear()
    sorttimelist.append(total_time)

print(sorttimelist)

以及一些示例结果：

[0.0065520769999985184, 0.0096335120000004]
[0.00565655999999945,   0.009094481000001708]
[0.005614095000000513,  0.00950561699999955]