`bisect.md`

187 строк · 14.5 КБ · обычная страница · сырой текст · скачать
1> **Источник:** https://python-all.ru/3.13/library/bisect.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# `bisect` – алгоритм деления массива пополам89**Исходный код:** [Lib/bisect.py](https://python-all.ru/src/3.13/Lib/bisect.py)1011---1213Этот модуль позволяет поддерживать список в отсортированном виде без необходимости сортировать его после каждой вставки. Для длинных списков с дорогостоящими операциями сравнения это может быть эффективнее линейного поиска или частой пересортировки.1415Модуль называется `bisect`, потому что использует базовый алгоритм деления пополам. В отличие от других инструментов бинарного поиска, которые ищут конкретное значение, функции этого модуля предназначены для нахождения точки вставки. Соответственно, они никогда не вызывают метод [`__eq__()`](https://python-all.ru/3.13/reference/datamodel.html#object.__eq__) для проверки, найдено ли значение. Вместо этого они вызывают метод [`__lt__()`](https://python-all.ru/3.13/reference/datamodel.html#object.__lt__) и возвращают точку вставки между элементами массива.1617> **Примечание**18>19> Функции этого модуля не являются потокобезопасными. Если несколько потоков одновременно используют функции `bisect` для одной и той же последовательности, это может привести к неопределённому поведению. Аналогично, если последовательность изменяется другим потоком во время работы функции `bisect`, результат не определён. Например, использование [`insort_left()`](https://python-all.ru/3.13/library/bisect.html#bisect.insort_left) для одного списка из нескольких потоков может привести к нарушению сортировки списка.2021Предоставляются следующие функции:2223#### `bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)`2425Находит точку вставки для *x* в *a*, чтобы сохранить сортировку. Параметры *lo* и *hi* можно использовать для указания подмножества списка; по умолчанию используется весь список. Если *x* уже присутствует в *a*, точка вставки будет перед (левее) всех существующих вхождений. Возвращаемое значение можно использовать в качестве первого аргумента для `list.insert()`, если *a* уже отсортирован.2627Возвращаемая точка вставки *ip* делит массив *a* на два среза так, что `all(elem < x for elem in a[lo : ip])` истинно для левого среза, а `all(elem >= x for elem in a[ip : hi])` истинно для правого среза.2829*key* задаёт [функцию ключа](https://python-all.ru/3.13/glossary.html#term-key-function) с одним аргументом, которая извлекает ключ сравнения из каждого элемента массива. Для поддержки поиска в сложных записях функция ключа не применяется к значению *x*.3031Если *key* равно `None`, элементы сравниваются напрямую, и функция ключа не вызывается.3233Изменено в версии 3.10: Добавлен параметр *key*.3435#### `bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)`3637#### `bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)`3839Аналогично [`bisect_left()`](https://python-all.ru/3.13/library/bisect.html#bisect.bisect_left), но возвращает точку вставки, которая находится после (правее) всех существующих вхождений *x* в *a*.4041Возвращаемая точка вставки *ip* делит массив *a* на два среза так, что `all(elem <= x for elem in a[lo : ip])` истинно для левого среза, а `all(elem > x for elem in a[ip : hi])` истинно для правого среза.4243Изменено в версии 3.10: Добавлен параметр *key*.4445#### `bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)`4647Вставляет *x* в *a* в отсортированном порядке.4849Сначала эта функция запускает [`bisect_left()`](https://python-all.ru/3.13/library/bisect.html#bisect.bisect_left) для поиска точки вставки. Затем она вызывает метод [`insert()`](https://python-all.ru/3.13/library/stdtypes.html#sequence.insert) у *a*, чтобы вставить *x* в нужное место для сохранения порядка сортировки.5051Чтобы поддерживать вставку записей в таблицу, функция *key* (если задана) применяется к *x* на этапе поиска, но не на этапе вставки.5253Стоит помнить, что поиск за *O*(log *n*) уступает по скорости медленному этапу вставки за *O*(*n*).5455Изменено в версии 3.10: Добавлен параметр *key*.5657#### `bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)`5859#### `bisect.insort(a, x, lo=0, hi=len(a), *, key=None)`6061Аналогично [`insort_left()`](https://python-all.ru/3.13/library/bisect.html#bisect.insort_left), но вставляет *x* в *a* после всех существующих вхождений *x*.6263Сначала эта функция запускает [`bisect_right()`](https://python-all.ru/3.13/library/bisect.html#bisect.bisect_right) для поиска точки вставки. Затем она вызывает метод [`insert()`](https://python-all.ru/3.13/library/stdtypes.html#sequence.insert) у *a*, чтобы вставить *x* в нужное место для сохранения порядка сортировки.6465Чтобы поддерживать вставку записей в таблицу, функция *key* (если задана) применяется к *x* на этапе поиска, но не на этапе вставки.6667Стоит помнить, что поиск за *O*(log *n*) уступает по скорости медленному этапу вставки за *O*(*n*).6869Изменено в версии 3.10: Добавлен параметр *key*.7071## Примечания по производительности7273При написании кода, чувствительного ко времени, с использованием *bisect()* и *insort()*, учитывайте следующее:7475- Бинарный поиск эффективен для поиска в диапазонах значений. Для поиска конкретных значений словари более производительны.76- Функции *insort()* имеют сложность *O*(*n*), поскольку логарифмический шаг поиска перекрывается линейным шагом вставки.77- Функции поиска не имеют состояния и отбрасывают результаты ключевой функции после их использования. Следовательно, если функции поиска используются в цикле, ключевая функция может вызываться снова и снова для одних и тех же элементов массива. Если ключевая функция не быстрая, рассмотрите обёртку с помощью [`functools.cache()`](https://python-all.ru/3.13/library/functools.html#functools.cache), чтобы избежать повторных вычислений. В качестве альтернативы рассмотрите поиск по массиву предварительно вычисленных ключей для определения точки вставки (как показано в разделе примеров ниже).7879> **См. также**80>81> - [Sorted Collections](https://python-all.ru/3.13/library/bisect.html) – это высокопроизводительный модуль, использующий *bisect* для управления отсортированными коллекциями данных.82> - Рецепт [SortedCollection](https://python-all.ru/3.13/library/bisect.html) использует bisect для создания полнофункционального класса коллекции с простыми методами поиска и поддержкой ключевой функции. Ключи предварительно вычисляются, чтобы избежать лишних вызовов ключевой функции во время поиска.8384## Поиск в отсортированных списках8586Вышеупомянутые [функции bisect](https://python-all.ru/3.13/library/bisect.html#bisect-functions) полезны для нахождения точек вставки, но могут быть сложными или неудобными для типичных задач поиска. Следующие пять функций показывают, как преобразовать их в стандартные операции поиска для отсортированных списков:8788```python89def index(a, x):90    'Locate the leftmost value exactly equal to x'91    i = bisect_left(a, x)92    if i != len(a) and a[i] == x:93        return i94    raise ValueError9596def find_lt(a, x):97    'Find rightmost value less than x'98    i = bisect_left(a, x)99    if i:100        return a[i-1]101    raise ValueError102103def find_le(a, x):104    'Find rightmost value less than or equal to x'105    i = bisect_right(a, x)106    if i:107        return a[i-1]108    raise ValueError109110def find_gt(a, x):111    'Find leftmost value greater than x'112    i = bisect_right(a, x)113    if i != len(a):114        return a[i]115    raise ValueError116117def find_ge(a, x):118    'Find leftmost item greater than or equal to x'119    i = bisect_left(a, x)120    if i != len(a):121        return a[i]122    raise ValueError123```124125## Примеры126127Функция [`bisect()`](https://python-all.ru/3.13/library/bisect.html#bisect.bisect) может быть полезна для поиска в числовых таблицах. В этом примере `bisect()` используется для определения буквенной оценки за экзамен (скажем) на основе набора упорядоченных числовых порогов: 90 и выше – «A», 80–89 – «B» и так далее:128129```python130>>> def grade(score):131...     i = bisect([60, 70, 80, 90], score)132...     return "FDCBA"[i]133...134>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]135['F', 'A', 'C', 'C', 'B', 'A', 'A']136```137138Функции [`bisect()`](https://python-all.ru/3.13/library/bisect.html#bisect.bisect) и [`insort()`](https://python-all.ru/3.13/library/bisect.html#bisect.insort) также работают со списками кортежей. Аргумент *key* может служить для извлечения поля, используемого для упорядочивания записей в таблице:139140```python141>>> from collections import namedtuple142>>> from operator import attrgetter143>>> from bisect import bisect, insort144>>> from pprint import pprint145146>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))147148>>> movies = [149...     Movie('Jaws', 1975, 'Spielberg'),150...     Movie('Titanic', 1997, 'Cameron'),151...     Movie('The Birds', 1963, 'Hitchcock'),152...     Movie('Aliens', 1986, 'Cameron')153... ]154155>>> # Найти первый фильм, выпущенный после 1960 года156>>> by_year = attrgetter('released')157>>> movies.sort(key=by_year)158>>> movies[bisect(movies, 1960, key=by_year)]159Movie(name='The Birds', released=1963, director='Hitchcock')160161>>> # Вставить фильм, сохраняя порядок сортировки162>>> romance = Movie('Love Story', 1970, 'Hiller')163>>> insort(movies, romance, key=by_year)164>>> pprint(movies)165[Movie(name='The Birds', released=1963, director='Hitchcock'),166 Movie(name='Love Story', released=1970, director='Hiller'),167 Movie(name='Jaws', released=1975, director='Spielberg'),168 Movie(name='Aliens', released=1986, director='Cameron'),169 Movie(name='Titanic', released=1997, director='Cameron')]170```171172Если ключевая функция требует больших вычислительных затрат, можно избежать повторных вызовов функции, выполнив поиск по списку предварительно вычисленных ключей для нахождения индекса записи:173174```python175>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]176>>> data.sort(key=lambda r: r[1])       # Или используйте operator.itemgetter(1).177>>> keys = [r[1] for r in data]         # Предварительно вычислите список ключей.178>>> data[bisect_left(keys, 0)]179('black', 0)180>>> data[bisect_left(keys, 1)]181('blue', 1)182>>> data[bisect_left(keys, 5)]183('red', 5)184>>> data[bisect_left(keys, 8)]185('yellow', 8)186```187