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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 是什么导致这两种插入排序实现之间的性能差异？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1643字，纯文字阅读大概需要3分钟。

内容图文

我有两个插入排序的实现.第一个是我的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()调用之间的差异.他们都给出了非常一致的结果.另外我只想强调一点,我每次都在创建一个新列表,而不是对已排序的列表进行排序.

解决方法:

我能够重现你的时间.对于随机数据或反向排序数据,insert_sort2比Python3.6上的insertion_sort快一点.但是,正如您所指出的,对于已经排序的数据,insertion_sort2的速度要慢三倍.

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

第二种情况(排序数据慢得多)的原因是,当迭代次数为零时,while循环比等效for循环便宜.这是因为while循环没有设置成本.等效的for循环仍然必须创建一个范围对象和一个range_iterator对象,然后才能找出没有迭代的东西.因此,while循环在空或几乎为空时击败for循环,因为它们避免了设置成本.

内容总结

以上是互联网集市为您收集整理的python – 是什么导致这两种插入排序实现之间的性能差异？全部内容，希望文章能够帮你解决python – 是什么导致这两种插入排序实现之间的性能差异？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---