14 подписчиков

Бинарный поиск и MultiSet своими руками

26 февраля 202126 фев 2021

2 мин

Оглавление

Действительно ли бинарный поиск так хорош?
Обзор модуля bisect
bisect_left(a: list, x : int, lo=0, hi=len(a)): int

Всем здравствуйте!

Наверное, вы где-то слышали о бинарном поиске. Если нет, то скажу кратко: это такой алгоритм, позволяющий нам быстро находить элементы в отсортированном массиве. В действительности же это понятие более емко, но для рассмотрения нашей темы этого достаточно. Если хотите подробную статью про бин. поиск обязательно оставьте комментарий.

Действительно ли бинарный поиск так хорош?

Сложность данного алгоритма O(log(n)) против O(n) при обыкновенном линейном поиске. Для сравнения, пусть вам дан массив из 100000 элементов, при линейном поиске в худшем случае придется совершить 100000 условных операций, в то время как при бинарном примерно 17!

Обзор модуля bisect

Bisect содержит следующие функции:

bisect_left(a: list, x : int, lo=0, hi=len(a)): int

Возвращает такой индекс, что все элементы a[:i] меньше x, а элементы a[i:] больше или равны x. Иными словами, мы получаем индекс первого элемента большего или равного x.

bisect_right(a: list, x : int, lo=0, hi=len(a)): int

Результатом работы данной функции будет такой индекс, что для любого v, принадлежащего a[:i], выполняется v <= x, а для v в a[i:], v > x. То есть мы получаем индекс первого элемента, большего x.

Сравнение bisect_left и bisect_right

insort_left(a: list, x: int, lo=0, hi=len(a)): int

Эквивалентно a.insert(bisect.bisect_left(a, x, lo, hi), x). По-человечески: вставляем элемент в отсортированный массив как можно левее так, чтобы сохранить отсортированность, так сказать.

insort_right(a: list, x: int, lo=0, hi=len(a)): int

То же самое, что и предыдущее, но вставлять будем как можно правее.

!!! Важно помнить, что вставка элемента в лист работает за O(n)

Как применить? Давайте сделаем multiset!

Начнем с того, что мы хотим делать, используя нашу структуру данных.

Мы хотим:

Быстро узнавать, есть ли элемент во множестве и в каком количестве
Хранить несколько одинаковых элементов

Итак, способность быстро получать информацию о наличии какого-либо предмета в нашей структуре данных нам позволит bisect. Хранить же элементы будем в обыкновенном листе.

Приступим!

Импорты

Конструктор

Объявим класс Multiset и реализуем для него конструктор. Заприватим внутренний массив, чтобы никакой дурачок не испортил.

Операторы

Перегрузим несколько операторов.

Основные методы

Перейдем к главным методам.

Что мы хотим:

insert(e) - вставить элемент E
erase(e) - удалить элемент E
pop(e) - удалить и вернуть E
lower(e) - получить самый левый E
upper(e) - получить самый правый E
count(e) - получить кол-во элементов
max() - получить максимальный
min() - получить минимальный
count_of_greater_than(e) - количество элементов больше E
count_of_less_than(e) - количество элементов меньше E

Insert O(n)

Erase O(n)

Pop O(n)

Зачем? Нуууу... нееееваааажжжжжнооооо........... может пригодиться.... честно......... потому что..... могут быть разные объекты, но с, интересным образом перегруженными, операторами сравнения......