bisect
- bisect主要用来管理有序序列，注意：一定是“有序”，bisect可以对有序序列进行快速的查找和插入。bisect模块主要包含两个函数：
- bisect：用来搜索元素位置（元素插入位置）
- insort：用来插入新元素
- 这两个函数都是使用二分查找算法在有序序列中查找或插入元素，所以执行效率非常高
- 下面将通过一些例子来对比说明bisect的高效率：
- 现在有一个场景：如果我需要插入一个值到一个有序列表中，然后依然保证这个列表的有序，那么如何快速获取需要插入值的位置索引？
import bisect
from time import perf_counter
from decimal import Decimal
ordered_list = [i for i in range(0, 10000000, 2)] # 定义一个0-9999999的升序偶数列表
insert_value = 9966666 # 需要插入的值
def loop_traversal_search():
"""用传统循环遍历方式进行搜索"""
start_time = perf_counter() # 开始时间
for i, value in enumerate(ordered_list):
if insert_value <= value:
print('插入元素{}的索引值应为: {}'.format(insert_value, i))
break
end_time = perf_counter() # 结束时间
duration_time = end_time - start_time # 搜索时间计算
print("循环遍历方式搜索耗时: {}秒".format(Decimal(str(duration_time))))
def bisect_search():
"""用bisect搜索"""
start_time = perf_counter() # 开始时间
position = bisect.bisect_left(ordered_list, insert_value)
print('插入元素{}的索引值应为: {}'.format(insert_value, position))
end_time = perf_counter() # 结束时间
duration_time = end_time - start_time # 搜索时间计算
print("bisect搜索耗时: {}秒".format(Decimal(str(duration_time))))
if __name__ == '__main__':
loop_traversal_search()
print('---------------------------------------------------')
bisect_search()
插入元素9966666的索引值应为: 4983333
循环遍历方式搜索耗时: 0.3305077秒
---------------------------------------------------
插入元素9966666的索引值应为: 4983333
bisect搜索耗时: 0.000009599999999998499秒
- 对比搜索时间，我们可以得出结论：bisect通过二分法进行搜索的速度比循环遍历快得多。
-
注意：在上面的例子中，bisect搜索时用的函数时bisect_left，其实还有一个对应的bisect_right。bisect_left和bisect_right的区别就在于：如果需要插入的值是在有序列表中已经存在，那么bisect_left将返回这个已存在值的索引（这意味着如果新的值从这个位置插入，将会在原来已经存在的值的前面），bisect_left将返回这个已存在值的下一个位置的索引（这意味着如果新的值从这个位置插入，将会在原来已经存在的值的后面），bisect_right通常简写为bisect。
- 当我们得到需要插入的位置索引后，就可以用insert进行元素插入了。
insort
- bisect还提供了一种快速插入的方法，insort，insort也区分insort_left和insort_right，insort_right简写为insort。
import bisect
from time import perf_counter
from decimal import Decimal
def bisect_search_and_insert(ordered_list, insert_value):
"""用bisect搜索并且insert插入"""
start_time = perf_counter() # 开始时间
position = bisect.bisect(ordered_list, insert_value)
ordered_list.insert(position, insert_value)
end_time = perf_counter() # 结束时间
duration_time = end_time - start_time # 搜索并插入时间计算
print("bisect搜索并插入耗时: {}秒".format(Decimal(str(duration_time))))
def bisect_insort_value(ordered_list, insert_value):
""""用insort插入"""
start_time = perf_counter()
bisect.insort(ordered_list, insert_value)
end_time = perf_counter()
duration_time = end_time - start_time # 搜索并插入时间计算
print("insort插入耗时: {}秒".format(Decimal(str(duration_time))))
if __name__ == '__main__':
bisect_search_and_insert([i for i in range(0, 10000000, 2)], 9696969)
print('----------------------------------------------------------')
bisect_insort_value([i for i in range(0, 10000000, 2)], 9696969)
bisect搜索并插入耗时: 0.0002004秒
----------------------------------------------------------
insort插入耗时: 0.000128000000000017秒
- 经过测试：用insort插入元素并且保持列表有序的速度更快一些
- 其他应用延伸：bisect还可以用来在有序序列中快速搜索某个元素的所在位置索引
