8.6. bisect
—数组平分算法¶
源代码: Lib/bisect.py
此模块支持以排序顺序维护列表,而不必在每次插入后对列表进行排序。对于具有昂贵的比较操作的项目的长列表,这可以是对更常见的方法的改进。该模块称为 bisect
,因为它使用基本对分算法来完成其工作。源代码作为算法的工作示例可能是最有用的(边界条件已经是正确的!)。
提供以下功能:
-
bisect.
bisect_left
(a, x, lo=0, hi=len(a))¶ 在 a 中找到 x 的插入点以保持排序顺序。参数 lo 和 hi 可以用于指定应当考虑的列表的子集;默认情况下使用整个列表。如果 x 已经存在于 a 中,则插入点将在任何现有条目之前(左侧)。返回值适合于用作
list.insert()
的第一个参数,假设 a 已经排序。返回的插入点 i 将阵列 a 分成两半,使得
all(val < x for val in a[lo:i])
用于左侧,all(val >= x for val in a[i:hi])
用于右侧。
-
bisect.
bisect_right
(a, x, lo=0, hi=len(a))¶ -
bisect.
bisect
(a, x, lo=0, hi=len(a))¶ 与
bisect_left()
类似,但是返回一个插入点,该插入点在 a 中 x 的任何现有条目之后(右侧)。返回的插入点 i 将阵列 a 分成两半,使得
all(val <= x for val in a[lo:i])
用于左侧,all(val > x for val in a[i:hi])
用于右侧。
-
bisect.
insort_left
(a, x, lo=0, hi=len(a))¶ 按照排序顺序在 a 中插入 x。这相当于假设 a 已经排序的
a.insert(bisect.bisect_left(a, x, lo, hi), x)
。请记住,O(log n)搜索由缓慢的O(n)插入步骤控制。
-
bisect.
insort_right
(a, x, lo=0, hi=len(a))¶ -
bisect.
insort
(a, x, lo=0, hi=len(a))¶ 类似于
insort_left()
,但在 x 的任何现有条目之后在 a 中插入 x。
参见
SortedCollection食谱 使用bisect构建一个全功能的集合类,使用直接搜索方法和支持键功能。密钥预先计算以在搜索期间保存对密钥功能的不必要的调用。
8.6.1. 搜索排序列表¶
上述 bisect()
函数对于查找插入点是有用的,但是对于公共搜索任务可能是棘手或笨拙的。以下五个函数显示如何将它们转换为排序列表的标准查找:
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def find_lt(a, x):
'Find rightmost value less than x'
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
def find_le(a, x):
'Find rightmost value less than or equal to x'
i = bisect_right(a, x)
if i:
return a[i-1]
raise ValueError
def find_gt(a, x):
'Find leftmost value greater than x'
i = bisect_right(a, x)
if i != len(a):
return a[i]
raise ValueError
def find_ge(a, x):
'Find leftmost item greater than or equal to x'
i = bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueError
8.6.2. 其他示例¶
bisect()
函数可用于数字表查找。这个例子使用 bisect()
基于一组有序数字断点来查找考试成绩(例如)的字母分数:90和up是’A’,80到89是’B’,等等:
>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
... i = bisect(breakpoints, score)
... return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']
与 sorted()
函数不同,bisect()
函数不具有 key 或 reversed 参数是没有意义的,因为这将导致低效的设计(对二等分函数的连续调用不会“记住”所有先前的键查找)。
相反,最好搜索预先计算的密钥列表以查找有问题的记录的索引:
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data] # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)