После атмосферных дождей весна в Калифорнии была великолепной. Надеюсь, ваша весна тоже будет прекрасной!
Модуль bisect поддерживает ведение списка в отсортированном порядке без необходимости сортировки списка после каждой вставки.
Ниже приведены функции, предоставляемые модулем:
0) bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
Параметры lo и hi могут использоваться для указания подмножества списка, которое следует учитывать; по умолчанию используется весь список.
key указывает ключевую функцию одного аргумента, которая используется для извлечения ключа сравнения из каждого элемента в массиве.
a массив отсортирован.
Возвращенная точка вставки i делит массив a на две половины, так что all(val < x for val in a[lo: i]) для левой части, а all(val >= x for val in a[i: hi]) для правой.
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(), но возвращает точку вставки i, которая идет после любых существующих записей x в a.
Возвращенная точка вставки i делит массив a на две половины, так что all(val <= x for val in a[lo: i]) для левой стороны и all(val > x for val in a[i: hi]) для правой стороны.
3) bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
Сначала функция запускает bisect_left(), чтобы найти точку вставки, i. Далее вставляется x в i для сохранения порядка сортировки.
4) bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
5) bisect.insort(a, x, lo=0, hi=len(a), *, key=None)
Подобно insert_right() для поиска точки вставки, i . Далее вставляется x в i для сохранения порядка сортировки.
Параметр ** key добавлен в Python 3.10.
Поиск в отсортированных списках:
Функции bisect() полезны для поиска точек вставки. Следующие пять функций показывают, как преобразовать их в стандартный поиск для отсортированного списка.
0) Поиск индекса
from bisect import bisect_left
def index(a, x):
'Locate the leftmost value equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
a = [7, 10, 54, 61, 67, 83, 85, 90, 93, 99]
idx = index(a, 85)
print(idx) # prints 6
- Нахождение меньше чем
from bisect import bisect_left
def find_lt(a, x):
'Find right most value less than x'
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
a = [7, 10, 54, 61, 67, 83, 85, 90, 93, 99]
lt_ele = find_lt(a, 67)
print(lt_ele) # 61
2) Нахождение меньше или равно
from bisect import bisect_right
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
a = [7, 10, 54, 61, 67, 83, 85, 90, 93, 99]
lte_ele = find_le(a, 68)
print(lte_ele) # prints 67
3) Нахождение большего, чем
from bisect import bisect_right
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
a = [7, 10, 54, 61, 67, 83, 85, 90, 93, 99]
gt_ele = find_gt(a, 93)
print(gt_ele) # prints 99
4) Нахождение больше или равно
from bisect import bisect_left
def find_gte(a, x):
'Find the leftmost value greater than or equal to x'
i = bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueError
a = [7, 10, 54, 61, 67, 83, 85, 90, 93, 99]
gte_ele = find_gt(a, 90)
print(gte_ele) # prints 90
Еще примеры применения алгоритма:
Пусть у нас есть измеритель обзора фильма:
import bisect
def tomatometer(rating: int, breakpoints: List[int]: [60, 70, 80, 90],\
stars: List[str]: ['*', '**', '***', '****', '*****']):
i = bisect.bisect(breakpoints, rating)
return stars[i]
print(tomatometer(69)) # prints '**'
print(tomatometer(70)) # prints '***'
В заключение, у python есть модуль bisect, который позволяет нам вставлять в упорядоченную коллекцию или поисковый индекс значения.
Поздравляем с завершением! 🎈 Спасибо, что читаете.
Увидимся в моем следующем посте. А пока ✨.
Вдохновение:
Вы можете поддержать меня на Патреоне!
