python - 是什么导致了插入排序的这两种实现之间的性能差异？

Question

我有两个插入排序的实现。第一个几乎是我的 java 教科书中示例的转录(尽管使用 while 循环而不是 java for 循环)

def insertion_sort(array):
    for i in range(1,len(array)):
        j = i
        while j > 0 and array[j] < array[j-1]:
            array[j],array[j-1] = array[j-1], array[j]
            j=j-1
    return array

第二个似乎是一个更 pythonic 的实现。

def insertion_sort2(array):
    for i in range(1,len(array)):
        for j in range(i-1,-1,-1):
            if array[j+1] < array[j]:
                array[j+1],array[j] = array[j],array[j+1]
            else:
                break
    return array

在对两者进行计时后，当列表已经排序或非常接近排序时，第二个似乎慢得多(慢 3 到 4 倍)。然而，随着反转次数的增加，第二种实现似乎占了上风(快 10-15%)。我只是想知道是否有人可以解释造成这种差异的原因。谢谢!

编辑:这是我用来创建随机列表的函数。

def rand_list(length):
    return [random.randint(0,9*length) for _ in range(length)]

当我想要一个部分排序的列表时，我只需调用 list(range(length1)) + rand_list(length2)。

至于计时它们运行多长时间，我使用了 %timeit 工具和两个 datetime.now() 调用之间的区别。他们都给出了相当一致的结果。另外我只想强调，我每次都在创建一个新列表，而不是对已经排序的列表进行排序。

Answer 1

我能够重现您的时间安排。对于随机数据或反向排序数据，insertion_sort2 在 Python3.6 上比 insertion_sort 快一点。但是，如您所述，insertion_sort2 对于已排序的数据要慢三倍。

第一种情况(在随机或排序数据上稍微快一些)的原因是 range_iterator 对象比手动编写 j=j- 更快地生成递减整数(在内部使用 C 代码) 1 和 j > 0 都是纯 python 步骤。因此，一旦 for 循环预热，它的运行速度就会比等效的 while 循环快一点。

第二种情况(在排序数据上慢得多)的原因是当迭代次数为零时，while 循环比等效的 for 循环更便宜。这是因为 while 循环没有设置成本。等效的 for 循环仍然必须同时创建一个 range 对象和一个 range_iterator 对象，然后才能确定没有迭代。因此，while 循环在为空或几乎为空时胜过 for 循环，因为它们避免了设置成本。