Содержание страницы

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

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

Этот модуль поддерживает хранение списка в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков, где операции сравнения дороги, это может быть эффективнее более распространенного подхода. Модуль называется bisect, потому что использует базовый алгоритм деления пополам. Исходный код может быть полезным как рабочий пример этого алгоритма (граничные условия уже правильные!).

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

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

Находит точку вставки для x в a, чтобы сохранить сортировку. Параметры 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]).

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.

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

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

Изменено в версии 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 в нужное место для сохранения порядка сортировки.

Имейте в виду, что O(log n) поиск в основном определяется медленным O(n) шагом вставки.

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

Примечания по производительности¶Performance Notes

При написании кода, чувствительного ко времени, с использованием bisect() и insort(), учитывайте следующее:

Бинарный поиск эффективен для поиска в диапазонах значений. Для поиска конкретных значений словари более производительны.
Функции insort() являются O(n), поскольку логарифмический шаг поиска перекрывается линейным шагом вставки.
Функции поиска не имеют состояния и отбрасывают результаты ключевой функции после их использования. Следовательно, если функции поиска используются в цикле, ключевая функция может вызываться снова и снова для одних и тех же элементов массива. Если ключевая функция не быстрая, рассмотрите обёртку с помощью functools.cache(), чтобы избежать повторных вычислений. В качестве альтернативы рассмотрите поиск по массиву предварительно вычисленных ключей для определения точки вставки (как показано в разделе примеров ниже).

См. также

Sorted Collections – это высокопроизводительный модуль, использующий bisect для управления отсортированными коллекциями данных.
Рецепт SortedCollection использует bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой ключевой функции. Ключи предварительно вычисляются, чтобы избежать лишних вызовов ключевой функции во время поиска.

Поиск в отсортированных списках¶Searching Sorted Lists

Вышеупомянутые функции 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

Примеры¶Examples

Функция 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']

Функции bisect() и insort() также работают со списками кортежей. Аргумент key может использоваться для извлечения поля, по которому упорядочиваются записи в таблице:

>>> 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')
... ]

>>> # Найти первый фильм, выпущенный после 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='Speilberg'),
 Movie(name='Aliens', released=1986, director='Scott'),
 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)

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

Примечания по производительности¶Performance Notes

Поиск в отсортированных списках¶Searching Sorted Lists

Примеры¶Examples

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