bisect
— Алгоритм разрезания массива¶
Источник: 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 задает key function одного аргумента, который используется для извлечения ключа сравнения из каждого элемента массива. Для поддержки поиска сложных записей функция ключа не применяется к значению x.
Если key равен
None
, элементы сравниваются напрямую и функция key не вызывается.Изменено в версии 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.
Заметки о производительности¶
При написании чувствительного к времени кода, использующего bisect() и insort(), имейте в виду следующее:
Биссектриса эффективна для поиска диапазонов значений. Для поиска конкретных значений более эффективны словари.
Функции insort() являются O(n), поскольку логарифмический шаг поиска доминирует над линейным шагом вставки.
Функции поиска не имеют состояния и отбрасывают результаты работы ключевых функций после их использования. Следовательно, если функции поиска используются в цикле, функция key может вызываться снова и снова для одних и тех же элементов массива. Если ключевая функция не является быстрой, подумайте о том, чтобы обернуть ее в
functools.cache()
, чтобы избежать дублирования вычислений. В качестве альтернативы можно использовать поиск в массиве предварительно вычисленных ключей для нахождения точки вставки (как показано в примерах ниже).
См.также
Sorted Collections - это высокопроизводительный модуль, который использует bisect для управления отсортированными коллекциями данных.
В SortedCollection recipe используется bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой функции ключа. Ключи предварительно вычисляются, чтобы избежать ненужных обращений к функции ключа во время поиска.
Поиск в отсортированных списках¶
Приведенные выше bisect functions полезны для поиска точек вставки, но могут быть сложны или неудобны для использования в обычных задачах поиска. Следующие пять функций показывают, как преобразовать их в стандартный поиск для отсортированных списков:
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']
Функции 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, 'Spielberg'),
... Movie('Titanic', 1997, 'Cameron'),
... Movie('The Birds', 1963, 'Hitchcock'),
... Movie('Aliens', 1986, 'Cameron')
... ]
>>> # Find the first movie released 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='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]) # 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)