bisect --- 數(shù)組二分查找算法?
源代碼： Lib/bisect.py
這個(gè)模塊對(duì)有序列表提供了支持，使得他們可以在插入新數(shù)據(jù)仍然保持有序。對(duì)于長(zhǎng)列表，如果其包含元素的比較操作十分昂貴的話，這可以是對(duì)更常見方法的改進(jìn)。這個(gè)模塊叫做 bisect 因?yàn)槠涫褂昧嘶镜亩郑╞isection）算法。源代碼也可以作為很棒的算法示例（邊界判斷也做好啦?。?/p>
定義了以下函數(shù)：
- bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)?
在 a 中找到 x 合適的插入點(diǎn)以維持有序。參數(shù) lo 和 hi 可以被用于確定需要考慮的子集；默認(rèn)情況下整個(gè)列表都會(huì)被使用。如果 x 已經(jīng)在 a 里存在，那么插入點(diǎn)會(huì)在已存在元素之前（也就是左邊）。如果 a 是列表（list）的話，返回值是可以被放在
list.insert()的第一個(gè)參數(shù)的。返回的插入點(diǎn) i 將數(shù)組 a 分成兩半，使得
all(val < x for val in a[lo : i])在左半邊而all(val >= x for val in a[i : hi])在右半邊。key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value.
If key is
None, the elements are compared directly with no intervening function call.在 3.10 版更改: 增加了 key 形參。
- bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)?
- bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)?
類似于
bisect_left()，但是返回的插入點(diǎn)是 a 中已存在元素 x 的右側(cè)。返回的插入點(diǎn) i 將數(shù)組 a 分成兩半，使得左半邊為
all(val <= x for val in a[lo : i])而右半邊為all(val > x for val in a[i : hi])。key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value.
If key is
None, the elements are compared directly with no intervening function call.在 3.10 版更改: 增加了 key 形參。
- bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)?
按照已排序順序?qū)?x 插入到 a 中。
此函數(shù)首先會(huì)運(yùn)行
bisect_left()來(lái)定位一個(gè)插入點(diǎn)。 然后，它會(huì)在 a 上運(yùn)行insert()方法在正確的位置插入 x 以保持排序順序。To support inserting records in a table, the key function (if any) is applied to x for the search step but not for the insertion step.
請(qǐng)記住
O(log n)搜索是由緩慢的 O(n) 拋入步驟主導(dǎo)的。在 3.10 版更改: 增加了 key 形參。
- bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)?
- bisect.insort(a, x, lo=0, hi=len(a), *, key=None)?
類似于
insort_left()，但是把 x 插入到 a 中已存在元素 x 的右側(cè)。此函數(shù)首先會(huì)運(yùn)行
bisect_right()來(lái)定位一個(gè)插入點(diǎn)。 然后，它會(huì)在 a 上運(yùn)行insert()方法在正確的位置插入 x 以保持排序順序。To support inserting records in a table, the key function (if any) is applied to x for the search step but not for the insertion step.
請(qǐng)記住
O(log n)搜索是由緩慢的 O(n) 拋入步驟主導(dǎo)的。在 3.10 版更改: 增加了 key 形參。
性能說明?
當(dāng)使用 bisect() 和 insort() 編寫時(shí)間敏感的代碼時(shí)，請(qǐng)記住以下概念。
二分法對(duì)于搜索一定范圍的值是很高效的。 對(duì)于定位特定的值，則字典的性能更好。
insort() 函數(shù)的時(shí)間復(fù)雜度為
O(n)因?yàn)閷?duì)數(shù)時(shí)間的搜索步驟被線性時(shí)間的插入步驟所主導(dǎo)。這些搜索函數(shù)都是無(wú)狀態(tài)的并且會(huì)在它們被使用后丟棄鍵函數(shù)的結(jié)果。 因此，如果在一個(gè)循環(huán)中使用搜索函數(shù)，則鍵函數(shù)可能會(huì)在同一個(gè)數(shù)據(jù)元素上被反復(fù)調(diào)用。 如果鍵函數(shù)速度不快，請(qǐng)考慮用
functools.cache()來(lái)包裝它以避免重復(fù)計(jì)算。 另外，也可以考慮搜索一個(gè)預(yù)先計(jì)算好的鍵數(shù)組來(lái)定位插入點(diǎn)（如下面的示例節(jié)所演示的）。
參見
Sorted Collections 是一個(gè)使用 bisect 來(lái)管理數(shù)據(jù)的已排序多項(xiàng)集的高性能模塊。
SortedCollection recipe 使用 bisect 構(gòu)建了一個(gè)功能完整的多項(xiàng)集類，擁有直觀的搜索方法和對(duì)鍵函數(shù)的支持。 所有鍵函數(shù)都 是預(yù)先計(jì)算好的以避免在搜索期間對(duì)鍵函數(shù)的不必要的調(diào)用。
搜索有序列表?
上面的 bisect() 函數(shù)對(duì)于找到插入點(diǎn)是有用的，但在一般的搜索任務(wù)中可能會(huì)有點(diǎn)尷尬。下面 5 個(gè)函數(shù)展示了如何將其轉(zhuǎn)變成有序列表中的標(biāo)準(zhǔn)查找函數(shù)
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
例子?
函數(shù) bisect() 還可以用于數(shù)字表查詢。這個(gè)例子是使用 bisect() 從一個(gè)給定的考試成績(jī)集合里，通過一個(gè)有序數(shù)字表，查出其對(duì)應(yīng)的字母等級(jí)：90 分及以上是 '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']
The bisect() and insort() functions also work with lists of
tuples. The key argument can serve to extract the field used for ordering
records in a table:
>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint
>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))
>>> movies = [
... Movie('Jaws', 1975, 'Speilberg'),
... Movie('Titanic', 1997, 'Cameron'),
... Movie('The Birds', 1963, 'Hitchcock'),
... Movie('Aliens', 1986, 'Scott')
... ]
>>> # Find the first movie released on or after 1960
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')
>>> # Insert a movie while maintaining sort order
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
Movie(name='Love Story', released=1970, director='Hiller'),
Movie(name='Jaws', released=1975, director='Speilberg'),
Movie(name='Aliens', released=1986, director='Scott'),
Movie(name='Titanic', released=1997, director='Cameron')]
If the key function is expensive, it is possible to avoid repeated function calls by searching a list of precomputed keys to find the index of a record:
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1]) # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data] # Precompute a 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)