python_bisect模块
一、用bisect 来管理已排序的序列
bisect 模块包含两个主要函数，bisect 和 insort，两个函数都利用二分查找算法来在有序序列中查找或插入元素
1.1 用bisect来搜索
bisect(haystack, needle) 在 haystack 里搜索 needle 的位置，该位置满足的条件是，把 needle 插入这个位置之后，haystack 还能保持升序。也就是说这个函数返回的位置前面的值，都小于或等于 needle 的值。其中 haystack 必须是一个有序的序列。你可以先用 bisect(haystack, needle) 查找位置 index，再用 haystack.insert(index, needle) 来插入新值。当然也可以用 insort 来一步到位，并且后者的速度更快一些。
import bisect
import sys
HAYSTACK = [1, 4, 5, 6, 8, 11, 13, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 24, 25, 29, 30, 31]
ROW_FMT = '{0: 2d} @ {1: 2d} {2}{0: < 2d}'
def demo(bisect_fn):
for needle in reversed(NEEDLES):
position = bisect_fn(HAYSTACK, needle) # 用特定的bisect 函数来计算元素应该出现的位置
offset = position * ' |' # 利用该位置来算出需要几个分隔符号
print(ROW_FMT.format(needle, position, offset)) # 把元素和其应该出现的位置打印出来
if __name__ == '__main__':
if sys.argv[-1] == 'left': # 根据命令上最后一个参数来选用bisect 函数
bisect_fn = bisect.bisect_left
else:
bisect_fn = bisect.bisect_right
print('DEMO: ', bisect_fn.__name__) # 把选定的函数在抬头打印出来。
print('haystack -> ', ' '.join('%2d' % n for n in HAYSTACK))
demo(bisect_fn)
运行结果如下：
F:\anaconda\python.exe E:/project/demo/demo2.py
DEMO: bisect_right
haystack -> 1 4 5 6 8 11 13 15 20 21 23 23 26 29 30
31 @ 15 | | | | | | | | | | | | | | | 31
30 @ 15 | | | | | | | | | | | | | | | 30
29 @ 14 | | | | | | | | | | | | | | 29
25 @ 12 | | | | | | | | | | | | 25
24 @ 12 | | | | | | | | | | | | 24
22 @ 10 | | | | | | | | | | 22
10 @ 5 | | | | | 10
8 @ 5 | | | | | 8
5 @ 3 | | | 5
2 @ 1 | 2
1 @ 1 | 1
0 @ 0 0
Process finished with exit code 0
bisect 的表现可以从两个方面来调教
首先可以用它的两个可选参数——lo 和 hi——来缩小搜寻的范围。lo的默认值是0，hi的默认值是序列的长度，即len()作用于该序列的返回值。
其次， bisect 函数其实是 bisect_right 函数的别名，后者还有个姊妹函数叫做 bisect_left。它们的区别在于，bisect_left 返回的插入位置是原序列中跟被插入元素相等的位置，也就是新元素会被放置于它相等的元素前面，而 bisect_right 返回的则是跟它相等的元素之后的位置。
bisect 可以用来建立一个用数字作为索引的查询表格，比如说把分数个成绩对应起来。
import bisect
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
i = bisect.bisect(breakpoints, score)
return grades[i]
student_grade = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
print(student_grade)
运行结果如下:
F:\anaconda\python.exe E:/project/demo/demo2.py
['F', 'A', 'C', 'C', 'B', 'A', 'A']
Process finished with exit code 0
二、用 bisect.insort 插入新元素
排序很耗时，因此在得到一个有序序列之后，我们最好能保持它的有序。 bisect.insort 就是为了这个而存在的。
insort(seq, item) 把变量item插入序列 seq 中，并能保持 seq 的升序顺序。
import bisect
import random
SIZE = 7
random.seed(1729)
my_list = []
for i in range(SIZE):
new_item = random.randrange(SIZE * 2)
bisect.insort(my_list, new_item)
print("%2d -> " % new_item, my_list)
运行结果如下：
F:\anaconda\python.exe E:/project/demo/demo2.py
10 -> [10]
0 -> [0, 10]
6 -> [0, 6, 10]
8 -> [0, 6, 8, 10]
7 -> [0, 6, 7, 8, 10]
2 -> [0, 2, 6, 7, 8, 10]
10 -> [0, 2, 6, 7, 8, 10, 10]
Process finished with exit code 0
insort 跟 bisect 一样， 有 lo 和 hi 两个可选参数来控制查找范围。它也有个变体叫 insort_left , 这个变体在背后用的是 bisect_left 。
