Python中bisect的使用方法
Python中列表(list)的实现其实是一个数组,当要查找某一个元素的时候时间复杂度是O(n),使用list.index()方法,但是随着数据量的上升,list.index()的性能也逐步下降,所以我们需要使用bisect模块来进行二分查找,前提我们的列表是一个有序的列表。
递归二分查找和循环二分查找
def binary_search_recursion(lst, val, start, end): if start > end: return None mid = (start + end) // 2 if lst[mid] < val: return binary_search_recursion(lst, val, mid + 1, end) if lst[mid] > val: return binary_search_recursion(lst, val, start, mid - 1) return mid def binary_search_loop(lst, val): start, end = 0, len(lst) - 1 while start <= end: mid = (start + end) // 2 if lst[mid] < val: start = mid + 1 elif lst[mid] > val: end = mid - 1 else: return mid return None
为了比对一下两者的性能,我们使用timeit模块来测试两个方法执行,timeit模块的timeit方法默认会对需要测试的函数执行1000000,然后返回执行的时间。
>>> import random >>> from random import randint >>> from random import choice >>> random.seed(5) >>> lst = [randint(1, 100) for _ in range(500000)] >>> lst.sort() >>> val = choice(lst) >>> val 6 >>> def test_recursion(): ... return binary_search_recursion(lst, val, 0, len(lst) - 1) ... >>> def test_loop(): ... return binary_search_loop(lst, val) ... >>> import timeit >>> t1 = timeit.timeit("test_recursion()", setup="from __main__ import test_recursion") >>> t1 3.9838006450511045 >>> t2 = timeit.timeit("test_loop()", setup="from __main__ import test_loop") >>> t2 2.749765167240339
可以看到,循环二分查找比递归二分查找性能要来的好些。现在,我们先用bisect的二分查找测试一下性能
用bisect来搜索
>>> import bisect >>> def binary_search_bisect(lst, val): ... i = bisect.bisect(lst, val) ... if i != len(lst) and lst[i] == val: ... return i ... return None ... >>> def test_bisect(): ... return binary_search_bisect(lst, val) ... >>> t3 = timeit.timeit("test_bisect()", setup="from __main__ import test_bisect") >>> t3 1.3453236258177412
对比之前,我们可以看到用bisect模块的二分查找的性能比循环二分查找快一倍。再来对比一下,如果用Python原生的list.index()的性能
>>> def test_index(): ... return lst.index(val) ... >>> t4 = timeit.timeit("test_index()", setup="from __main__ import test_index") >>> t4 518.1656223725007
可以看到,如果用Python原生的list.index()执行1000000,需要500秒,相比之前的二分查找,性能简直慢到恐怖
用bisect.insort插入新元素
排序很耗时,因此在得到一个有序序列之后,我们最好能够保持它的有序。bisect.insort就是为这个而存在的
insort(seq, item)把变量item插入到序列seq中,并能保持seq的升序顺序
import random from random import randint import bisect lst = [] SIZE = 10 random.seed(5) for _ in range(SIZE): item = randint(1, SIZE) bisect.insort(lst, item) print('%2d ->' % item, lst)
输出:
10 -> [10]
5 -> [5, 10]
6 -> [5, 6, 10]
9 -> [5, 6, 9, 10]
1 -> [1, 5, 6, 9, 10]
8 -> [1, 5, 6, 8, 9, 10]
4 -> [1, 4, 5, 6, 8, 9, 10]
1 -> [1, 1, 4, 5, 6, 8, 9, 10]
3 -> [1, 1, 3, 4, 5, 6, 8, 9, 10]
2 -> [1, 1, 2, 3, 4, 5, 6, 8, 9, 10]
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
- 有时为了网站安全和版权问题,会对自己写的php源码进行加密,在php加密技术上最常用的是zend公司的zend guard 加密软件,现在我们来图文讲解一下。 下面就简单说说如何...2016-11-25
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
- ps软件是现在很多人都会使用到的,HSL面板在ps软件中又有着非常独特的作用。这次文章就给大家介绍下ps怎么使用HSL面板,还不知道使用方法的下面一起来看看。  ...2017-07-06
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 许多的朋友对于Plesk控制面板应用不是非常的了解特别是英文版的Plesk控制面板,在这里小编整理了一些关于Plesk控制面板常用的使用方案整理,具体如下。 本文基于Linu...2016-10-10
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
使用insertAfter()方法在现有元素后添加一个新元素
复制代码 代码如下: //在现有元素后添加一个新元素 function insertAfter(newElement, targetElement){ var parent = targetElement.parentNode; if (parent.lastChild == targetElement){ parent.appendChild(newEl...2014-05-31- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
jQuery 1.9使用$.support替代$.browser的使用方法
jQuery 从 1.9 版开始,移除了 $.browser 和 $.browser.version , 取而代之的是 $.support 。 在更新的 2.0 版本中,将不再支持 IE 6/7/8。 以后,如果用户需要支持 IE 6/7/8,只能使用 jQuery 1.9。 如果要全面支持 IE,并混合...2014-05-31使用percona-toolkit操作MySQL的实用命令小结
1.pt-archiver 功能介绍: 将mysql数据库中表的记录归档到另外一个表或者文件 用法介绍: pt-archiver [OPTION...] --source DSN --where WHERE 这个工具只是归档旧的数据,不会对线上数据的OLTP查询造成太大影响,你可以将...2015-11-24