Python中bisect的使用方法
作者:北洛 发布时间:2021-12-03 05:56:12
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]
来源:https://www.cnblogs.com/beiluowuzheng/p/8452671.html
猜你喜欢
- 这篇论坛文章(赛迪网技术社区)主要介绍了一种简单的MySQL数据库安装方法,详细内容请大家参考下文:虽然安装MySQL数据库的文章很多,但是
- IE8 的测试版发布,ACID 3 测试正式推出,听上去是让人兴奋的技术进步,而对中文互联网站却是极大的威胁:这意味着,超过半数的中文网页在
- 经常有网友会问,SQL Server占用了太多的内存,而且还会不断的增长;或者说已经设置了使用内存,可它没有用到那么多,这是怎么一回事儿呢?
- Object 类型的对象虽然有 toString 方法,但结果却是 [Object Object] 让人没法理解的字符。比如简单的对象:{n
- 一、字符串与字节数组?字符串是 Go 语言中最常用的基础数据类型之一,本质上是只读的字符型数组,虽然字符串往往都被看做是一个整体,但是实际上
- select * from V$NLS_PARAMETERS; SQL> alter session set NLS_DATE_LAN
- 最近在做新闻发布系统的时候,用到了二级联动,我把使用方法记录下来,以便日后查阅以及帮助新手朋友们。下面是效果图:下面来讲解一下实现的方法:1
- 成为一个顶级设计师的第一准则:限制你的字体让你成为设计大的七个基本原则之一好~设计大师,或者也太吹牛了吧,但根据下面七个基本原则至少你可以成
- 在网上我们常常看见一些注册表单的输入框部分并不是我们常见的矩形框,而是一条细线,很多朋友对此很感兴趣。其实要实现这样的效果并不困难,我们只要
- AXObject可用来解决IE需要激活 ActiveX 控件和生成控件调用代码 AXObjec
- 当系统出现故障时,只要存在数据日志那么就可以利用它来恢复数据解决数据库故障。作为SQL Server数据库管理员,了解数据日志文件的作用,以
- 连接数据库:mysql -u用户名 -p密码导入数据 source d:\create.sql用下面的语句就可以导出mysql中的数据了:m
- 富文本编辑器,Rich Text Editor, 简称 RTE, 它提供类似于 Microsoft Word 的编辑功能,容易被不会编写 H
- [sql] --1.将每个老师的工资更新为原来的工资+奖金 --定义两个变量,用来存储ttid与reward declare @tid in
- 1、XML 是什么?XML仅仅是一种数据存放格式,这种格式是一种文本(虽然XML规范中也提供了存放二进制数据的解决方案)。事实上有很多文本格
- 我就废话不多说了,大家还是直接看代码吧~#!/usr/bin/env python# encoding: utf-8''
- 阅读上一篇:FrontPage XP设计教程4——Css样式表的应用表单在网站的制作过程中是比较常见的,举个简单的例子,我们在申请免费电子信
- javascript可以根据输入值自动搜索显示相关的select列表,对于列表很长时可以很方便的查找到要的值。js代码:<script
- 本文试图从iPhone的角度结合一些iPhone平台项目的设计经验提炼出iPhone平台的一些优秀设计思路,以供大家在做移动互联网设备设计时
- 最近一直忙,我们的注册页面还是在持续优化。今天抽时间分析了下数据,依然以主注册表单为例,对表单里3个区块、9个字段做了个小小出错排行;看看哪