专栏地址: 每周一个 Python 模块
bisect 模块, 用于维护有序列表. 实现了一个算法用于插入元素到有序列表. 在一些情况下, 这比反复排序列表或构造一个大的列表再排序的效率更高. Bisect 是二分法的意思, 这里使用二分法来排序, 它会将一个元素插入到一个有序列表的合适位置, 这使得不需要每次调用 sort 的方式维护有序列表.
以排序顺序插入
看下面的例子, insort() 用于按排序顺序将项目插入列表.
- import bisect
- # A series of random numbers
- values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]
- print('New Pos Contents')
- print('--- --- --------')
- l = []
- for i in values:
- position = bisect.bisect(l, i)
- bisect.insort(l, i)
- print('{:3} {:3}'.format(i, position), l)
- # output
- # New Pos Contents
- # --- --- --------
- # 14 0 [14]
- # 85 1 [14, 85]
- # 77 1 [14, 77, 85]
- # 26 1 [14, 26, 77, 85]
- # 50 2 [14, 26, 50, 77, 85]
- # 45 2 [14, 26, 45, 50, 77, 85]
- # 66 4 [14, 26, 45, 50, 66, 77, 85]
- # 79 6 [14, 26, 45, 50, 66, 77, 79, 85]
- # 10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
- # 3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
- # 84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
- # 77 8 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
- # 1 0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
输出的第一列显示要插入的值. 第二列显示数字将插入列表的位置. 第三列是当前排序列表.
处理重复
上面例子显示的结果集包括重复值 77.bisect 模块提供了两种处理重复的方法: 可以将新值插入现有值的左侧, 也可以插入右侧. insort() 函数实际上是 insort_right() 的别名, 它在现有值之后插入一个项目. 相应的函数 insort_left(), 在现有值之前插入.
- import bisect
- # A series of random numbers
- values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]
- print('New Pos Contents')
- print('--- --- --------')
- # Use bisect_left and insort_left.
- l = []
- for i in values:
- position = bisect.bisect_left(l, i)
- bisect.insort_left(l, i)
- print('{:3} {:3}'.format(i, position), l)
- # output
- # New Pos Contents
- # --- --- --------
- # 14 0 [14]
- # 85 1 [14, 85]
- # 77 1 [14, 77, 85]
- # 26 1 [14, 26, 77, 85]
- # 50 2 [14, 26, 50, 77, 85]
- # 45 2 [14, 26, 45, 50, 77, 85]
- # 66 4 [14, 26, 45, 50, 66, 77, 85]
- # 79 6 [14, 26, 45, 50, 66, 77, 79, 85]
- # 10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
- # 3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
- # 84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
- # 77 8 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
- # 1 0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
当使用 bisect_left() 和 insort_right() 操作相同的数据时, 结果是相同的排序列表, 但插入位置对于重复值是不同的.
相关文档:
- https://pymotw.com/3/bisect/index.html
- http://www.liujiangblog.com/course/python/57
- http://kuanghy.github.io/2016/06/14/python-bisect
来源: https://juejin.im/post/5c123655e51d455fa5451c42