bisect --- 陣列二分演算法 (Array bisection algorithm)

原始碼:Lib/bisect.py


這個模組維護一個已經排序過的 list ,當我們每次做完插入後不需要再次排序整個 list 。一個很長的 list 的比較操作很花費時間,為了改進這點,這個模組是其中一個常用的方法。這個模組被命名為 bisect 來自他使用一個基礎的 bisection 演算法實作。模組的原始碼是這個演算法的一個完善的實作(邊界條件已經是正確的了)。

此模組提供下面的函式

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

a 當中找到一個位置,讓 x 插入後 a 仍然是排序好的。參數 lohi 用來指定 list 中應該被考慮的子區間,預設是考慮整個 list 。如果 a 裡面已經有 x 出現,插入的位置會在所有 x 的前面(左邊)。回傳值可以被當作 list.insert() 的第一個參數,但列表 a 必須先排序過。

回傳的插入位置 i 將陣列 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() ,但回傳的插入位置會在所有 a 當中的 x 的後面(右邊)。

回傳的插入位置 i 將陣列 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)

按照已排序顺序将 x 插入到 a 中。

此函数首先会运行 bisect_left() 来定位一个插入点。 然后,它会在 a 上运行 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.

请记住 O(log n) 搜索是由缓慢的 O(n) 抛入步骤主导的。

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() ,但插入的位置會在所有 a 當中的 x 的後面(右邊)。

此函数首先会运行 bisect_right() 来定位一个插入点。 然后,它会在 a 上运行 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.

请记住 O(log n) 搜索是由缓慢的 O(n) 抛入步骤主导的。

3.10 版更變: 新增 key 參數。

性能说明

当使用 bisect()insort() 编写时间敏感的代码时,请记住以下概念。

  • 二分法对于搜索一定范围的值是很高效的。 对于定位特定的值,则字典的性能更好。

  • insort() 函数的时间复杂度为 O(n) 因为对数时间的搜索步骤被线性时间的插入步骤所主导。

  • 这些搜索函数都是无状态的并且会在它们被使用后丢弃键函数的结果。 因此,如果在一个循环中使用搜索函数,则键函数可能会在同一个数据元素上被反复调用。 如果键函数速度不快,请考虑用 functools.cache() 来包装它以避免重复计算。 另外,也可以考虑搜索一个预先计算好的键数组来定位插入点(如下面的示例节所演示的)。

也參考

  • Sorted Collections 是一个使用 bisect 来管理数据的已排序多项集的高性能模块。

  • SortedCollection recipe 使用 bisect 构建了一个功能完整的多项集类,拥有直观的搜索方法和对键函数的支持。 所有键函数都 是预先计算好的以避免在搜索期间对键函数的不必要的调用。

搜索有序列表

上面的 bisect() 函数对于找到插入点是有用的,但在一般的搜索任务中可能会有点尴尬。下面 5 个函数展示了如何将其转变成有序列表中的标准查找函数

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

範例

函数 bisect() 还可以用于数字表查询。这个例子是使用 bisect() 从一个给定的考试成绩集合里,通过一个有序数字表,查出其对应的字母等级: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)