bisect – алгоритм деления массива пополам¶bisect – Array bisection algorithm

Исходный код: Lib/bisect.py

Этот модуль позволяет поддерживать список в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков с дорогостоящими операциями сравнения это может быть эффективнее линейного поиска или частой пересортировки.

Модуль называется bisect, потому что использует базовый алгоритм деления пополам. В отличие от других инструментов бинарного поиска, которые ищут конкретное значение, функции этого модуля предназначены для нахождения точки вставки. Соответственно, они никогда не вызывают метод __eq__() для проверки, найдено ли значение. Вместо этого они вызывают метод __lt__() и возвращают точку вставки между элементами массива.

Предоставляются следующие функции:

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

Находит точку вставки для x в a, чтобы сохранить сортировку. Параметры lo и hi можно использовать для указания подмножества списка; по умолчанию используется весь список. Если x уже присутствует в a, точка вставки будет перед (левее) всех существующих вхождений. Возвращаемое значение можно использовать в качестве первого аргумента для list.insert(), если a уже отсортирован.

Возвращаемая точка вставки ip делит массив a на два среза так, что all(elem < x for elem in a[lo : ip]) истинно для левого среза, а all(elem >= x for elem in a[ip : hi]) истинно для правого среза.

key задаёт функцию ключа с одним аргументом, которая извлекает ключ сравнения из каждого элемента массива. Для поддержки поиска в сложных записях функция ключа не применяется к значению x.

Если key равно None, элементы сравниваются напрямую, и функция ключа не вызывается.

Изменено в версии 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(), но возвращает точку вставки, которая находится после (правее) всех существующих вхождений x в a.

Возвращаемая точка вставки ip делит массив a на два среза так, что all(elem <= x for elem in a[lo : ip]) истинно для левого среза, а all(elem > x for elem in a[ip : hi]) истинно для правого среза.

Изменено в версии 3.10: Добавлен параметр key.

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

Вставляет x в a в отсортированном порядке.

Сначала эта функция запускает bisect_left() для поиска точки вставки. Затем она вызывает метод insert() у a, чтобы вставить x в нужное место для сохранения порядка сортировки.

Чтобы поддерживать вставку записей в таблицу, функция key (если задана) применяется к x на этапе поиска, но не на этапе вставки.

Стоит помнить, что поиск за 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(), но вставляет x в a после всех существующих вхождений x.

Сначала эта функция запускает bisect_right() для поиска точки вставки. Затем она вызывает метод insert() у a, чтобы вставить x в нужное место для сохранения порядка сортировки.

Чтобы поддерживать вставку записей в таблицу, функция key (если задана) применяется к x на этапе поиска, но не на этапе вставки.

Стоит помнить, что поиск за O(log n) уступает по скорости медленному этапу вставки за O(n).

Изменено в версии 3.10: Добавлен параметр key.

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

>>> def grade(score):
...     i = bisect([60, 70, 80, 90], score)
...     return "FDCBA"[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

>>> 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, 'Spielberg'),
...     Movie('Titanic', 1997, 'Cameron'),
...     Movie('The Birds', 1963, 'Hitchcock'),
...     Movie('Aliens', 1986, 'Cameron')
... ]

>>> # Найти первый фильм, выпущенный после 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')

>>> # Вставить фильм, сохраняя порядок сортировки
>>> 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='Spielberg'),
 Movie(name='Aliens', released=1986, director='Cameron'),
 Movie(name='Titanic', released=1997, director='Cameron')]

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # Или используйте operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Предварительно вычислите список ключей.
>>> 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)