Python中bisect的使用方法

2023-08-03 17:33:04 57

Python中列表（list）的实现其实是一个数组，当要查找某一个元素的时候时间复杂度是O(n)，使用list.index()方法，但是随着数据量的上升，list.index()的性能也逐步下降，所以我们需要使用bisect模块来进行二分查找，前提我们的列表是一个有序的列表。

递归二分查找和循环二分查找

defbinary_search_recursion(lst,val,start,end):
ifstart>end:
returnNone
mid=(start+end)//2
iflst[mid]val:
returnbinary_search_recursion(lst,val,start,mid-1)
returnmid


defbinary_search_loop(lst,val):
start,end=0,len(lst)-1
whilestart<=end:
mid=(start+end)//2
iflst[mid]val:
end=mid-1
else:
returnmid
returnNone

为了比对一下两者的性能，我们使用timeit模块来测试两个方法执行，timeit模块的timeit方法默认会对需要测试的函数执行1000000，然后返回执行的时间。

>>>importrandom
>>>fromrandomimportrandint
>>>fromrandomimportchoice
>>>random.seed(5)
>>>lst=[randint(1,100)for_inrange(500000)]
>>>lst.sort()
>>>val=choice(lst)
>>>val
6
>>>deftest_recursion():
...returnbinary_search_recursion(lst,val,0,len(lst)-1)
...
>>>deftest_loop():
...returnbinary_search_loop(lst,val)
...
>>>importtimeit
>>>t1=timeit.timeit("test_recursion()",setup="from__main__importtest_recursion")
>>>t1
3.9838006450511045
>>>t2=timeit.timeit("test_loop()",setup="from__main__importtest_loop")
>>>t2
2.749765167240339

可以看到，循环二分查找比递归二分查找性能要来的好些。现在，我们先用bisect的二分查找测试一下性能

用bisect来搜索

>>>importbisect
>>>defbinary_search_bisect(lst,val):
...i=bisect.bisect(lst,val)
...ifi!=len(lst)andlst[i]==val:
...returni
...returnNone
...
>>>deftest_bisect():
...returnbinary_search_bisect(lst,val)
...
>>>t3=timeit.timeit("test_bisect()",setup="from__main__importtest_bisect")
>>>t3
1.3453236258177412

对比之前，我们可以看到用bisect模块的二分查找的性能比循环二分查找快一倍。再来对比一下，如果用Python原生的list.index()的性能

>>>deftest_index():
...returnlst.index(val)
...
>>>t4=timeit.timeit("test_index()",setup="from__main__importtest_index")
>>>t4
518.1656223725007

可以看到，如果用Python原生的list.index()执行1000000，需要500秒，相比之前的二分查找，性能简直慢到恐怖

用bisect.insort插入新元素

排序很耗时，因此在得到一个有序序列之后，我们最好能够保持它的有序。bisect.insort就是为这个而存在的

insort(seq,item)把变量item插入到序列seq中，并能保持seq的升序顺序

importrandom
fromrandomimportrandint
importbisect

lst=[]
SIZE=10
random.seed(5)
for_inrange(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]

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Python中bisect的使用方法

热门推荐

随机推荐