bisect
— Алгоритм деления массива пополам¶
Исходный код: 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 указывает key function одного аргумента, который используется для извлечения ключа сравнения из каждого элемента массива. Для поддержки поиска сложных записей функция key не применяется к значению x.
Если ключ равен
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 указывает key function одного аргумента, который используется для извлечения ключа сравнения из каждого элемента массива. Для поддержки поиска сложных записей функция key не применяется к значению x.
Если ключ равен
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 в соответствующую позицию для сохранения порядка сортировки.Чтобы поддерживать вставку записей в таблицу, функция key (если таковая имеется) применяется к x на этапе поиска, но не на этапе вставки.
Имейте в виду, что при поиске по O(log n) преобладает медленный шаг ввода O(n).
Изменено в версии 3.10: Добавлен параметр key.
Примечания к производительности¶
При написании трудоемкого кода с использованием bisect() и insert() помните об этих соображениях:
Разделение пополам эффективно для поиска в диапазонах значений. Для поиска конкретных значений словари более эффективны.
Функции insert() имеют значение O(n), поскольку в логарифмическом шаге поиска преобладает шаг вставки по линейному времени.
Функции поиска не имеют состояния и отбрасывают результаты работы ключевых функций после их использования. Следовательно, если функции поиска используются в цикле, ключевая функция может вызываться снова и снова для одних и тех же элементов массива. Если функция key не работает быстро, попробуйте использовать для нее
functools.cache()
, чтобы избежать дублирования вычислений. В качестве альтернативы можно выполнить поиск по массиву предварительно вычисленных ключей, чтобы найти точку вставки (как показано в разделе примеров ниже).
См.также
Sorted Collections - это высокопроизводительный модуль, который использует bisect для управления отсортированными наборами данных.
В SortedCollection recipe используется bisect для создания полнофункционального класса collection с прямыми методами поиска и поддержкой функции key. Ключи предварительно вычисляются, чтобы избежать ненужных вызовов функции key во время поиска.
Поиск в отсортированных списках¶
Приведенные выше 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)