一、用bisect 來管理已排序的序列
bisect 模塊包含兩個主要函數(shù)，bisect 和 insort瓤逼，兩個函數(shù)都利用二分查找算法來在有序序列中查找或插入元素
1.1 用bisect來搜索
bisect(haystack, needle) 在 haystack 里搜索 needle 的位置礼华，該位置滿足的條件是，把 needle 插入這個位置之后戏售，haystack 還能保持升序侨核。也就是說這個函數(shù)返回的位置前面的值草穆，都小于或等于 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 函數(shù)來計算元素應該出現(xiàn)的位置
offset = position * ' |' # 利用該位置來算出需要幾個分隔符號
print(ROW_FMT.format(needle, position, offset)) # 把元素和其應該出現(xiàn)的位置打印出來
if __name__ == '__main__':
if sys.argv[-1] == 'left': # 根據(jù)命令上最后一個參數(shù)來選用bisect 函數(shù)
bisect_fn = bisect.bisect_left
else:
bisect_fn = bisect.bisect_right
print('DEMO: ', bisect_fn.__name__) # 把選定的函數(shù)在抬頭打印出來。
print('haystack -> ', ' '.join('%2d' % n for n in HAYSTACK))
demo(bisect_fn)
運行結(jié)果如下：
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 的表現(xiàn)可以從兩個方面來調(diào)教
首先可以用它的兩個可選參數(shù)——lo 和 hi——來縮小搜尋的范圍段标。lo的默認值是0涯冠，hi的默認值是序列的長度，即len()作用于該序列的返回值怀樟。
其次功偿， bisect 函數(shù)其實是 bisect_right 函數(shù)的別名，后者還有個姊妹函數(shù)叫做 bisect_left往堡。它們的區(qū)別在于械荷，bisect_left 返回的插入位置是原序列中跟被插入元素相等的位置，也就是新元素會被放置于它相等的元素前面虑灰，而 bisect_right 返回的則是跟它相等的元素之后的位置吨瞎。
bisect 可以用來建立一個用數(shù)字作為索引的查詢表格，比如說把分數(shù)個成績對應起來穆咐。
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)
運行結(jié)果如下:
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)
運行結(jié)果如下：
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 兩個可選參數(shù)來控制查找范圍拆讯。它也有個變體叫 insort_left , 這個變體在背后用的是 bisect_left 脂男。
