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 。