简介
这个库还是比较简单的。
基本的要点有两个：
- 它内部的所有操作都使用 二分查找法
- 它操作的所有序列都要求为升序，且操作最好为线性表（即数组，如果使用 list，性能不佳）
它提供的函数分为两类：
bisect bisect_left bisect_right
查找某元素在序列中的插入位置
如果某元素在序列中已存在， bisect_left 则返回该元素左边的位置， bisect_right 返回该元素右边的位置
1
bisect = bisect_right # 向后兼容
insort insort_left insort_right
将某元素插入到序列中
如果某元素在序列中已存在 , insort_left 插入到该元素的左边，insort_right 插入到该元素的右边
1
insort = insort_right # 向后兼容
当然，如果直接使用 Python 来实现这些功能，性能是不怎么样的，所以在源码中，一开始给出了 Python 版本的定义，但是在文件最后，还是会尝试导入 C 语言版本。
1 2 3 4 | try:
from _bisect import *
except ImportError:
pass
|
bisect&&bisect_right
bisect_right 的签名还是很简单的：
a 为操作的序列
x 为某元素
lo hi 用来指定 a 中的开始查找和结束查找位置，默认是指整个 a 序列
原代码实现（Python 版本）：
1 2 3 4 5 6 7 8 9 10 | def bisect_right(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2 # 使用 floor 除法，保证 a[mid] 不会抛出 IndexError
if x < a[mid]: hi = mid
else: lo = mid+1
return lo
|
上面的源代码没啥好解释的，知道 二分查找 是啥，基本就能懂了。
但是我还是想用递归思想重写一遍。
因为二分查找的算法定义是什么样子，它对应的代码就是什么样子，能够和定义一一对应，一眼就能看明白。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def help_mybisect_right(a, x, lo, hi):
if lo > hi:
return lo
mid_index = (lo + hi) // 2
mid = a[mid_index]
if x == mid:
return mid_index + 1
elif x < mid:
return help_mybisect_right(a, x, lo, mid_index - 1)
else:
return help_mybisect_right(a, x, mid_index + 1, hi)
def mybisect_right(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a) - 1
return help_mybisect_right(a, x, lo, hi)
|
嗯，咱们比较一下两者的性能。
1 2 3 4 5 6 7 8 9 | In [164]: import array
In [165]: a = array.array("i", xrange(1000))
In [178]: %timeit -n10000 -r100 bisect_right(a, 7)
10000 loops, best of 100: 1.45 µs per loop
In [179]: %timeit -n10000 -r100 mybisect_right(a, 7)
10000 loops, best of 100: 2.86 µs per loop
|
性能相差两倍左右 ... ...，SO，我还挺希望 Python 的解释器有尾递归优化的，甚至尾调用优化。
bisect_left
原代码实现（Python 版本）：
1 2 3 4 5 6 7 8 9 10 | def bisect_left(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
|
使用递归来实现一下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def help_mybisect_left(a, x, lo, hi):
if lo > hi:
return lo
mid_index = (lo + hi) // 2
mid = a[mid_index]
if x == mid:
return mid_index
elif x < mid:
return help_mybisect_left(a, x, lo, mid_index - 1)
else:
return help_mybisect_left(a, x, mid_index + 1, hi)
def mybisect_left(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
return help_mybisect_left(a, x, lo, hi)
|
help_mybisect_left help_mybisect_right 大体差不多么，将公共部分抽出来，用连续的概念，再添加一个参数 continue_func 。用来处理 help_mybisect 的结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def help_mybisect(a, x, lo, hi, continue_func):
if lo > hi:
return lo
mid_index = (lo + hi) // 2
mid = a[mid_index]
if x == mid:
return continue_func(mid_index)
elif x < mid:
return help_mybisect_left(a, x, lo, mid_index - 1)
else:
return help_mybisect_left(a, x, mid_index + 1, hi)
help_mybisect_left = lambda a, x, lo, hi: help_mybisect(a, x, lo, hi, lambda num: num)
help_mybisect_right = lambda a, x, lo, hi: help_mybisect(a, x, lo, hi, lambda num: num + 1)
|
insort&&insort_right
这个函数的代码基本上就是先用 bisect_right 查找出需要插入的位置，然后调用 a.insert 即可。
insort_left
这个函数的代码基本上就是先用 bisect_left 查找出需要插入的位置，然后调用 a.insert 即可。