Модуль bisect - сортировка в моменте

Курс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs

Стандартная библиотека языка Python содержит модуль bisect, который позволяет поддерживать в отсортированном порядке любую изменяемую упорядоченную последовательность. Чаще всего – это списки языка Python. Давайте посмотрим на конкретном примере, как это работает.

Предположим, имеется пустой список:

sd = []

в который нужно последовательно занести следующие числа:

data = (4, 3, -1, 0, 10, 5, 4)

так, чтобы они располагались по возрастанию (неубыванию) своих значений. Если это делать стандартными методами языка Python, используя сортировку после каждого нового добавления:

for x in data:
    sd.append(x)
    sd.sort()
    print(sd)

то вычислительная сложность алгоритма будет быстро нарастать с увеличением длины последовательности. Поэтому в таких задачах лучше применять более тонкие алгоритмы, которые добавляют новые элементы не в конец, а сразу в нужную позицию, сохраняя порядок следования от наименьшего к наибольшему значению. Именно это делает функция insort() модуля bisect:

for x in data:
    bisect.insort(sd, x)
    print(sd)

Функция insort вначале анализирует данные списка sd, вычисляет индекс позиции добавляемого элемента x, и сразу ставит новый элемент так, чтобы сохранялся порядок сортировки. В итоге в консоли увидим следующий процесс формирования списка sd:

[4]
[3, 4]
[-1, 3, 4]
[-1, 0, 3, 4]
[-1, 0, 3, 4, 10]
[-1, 0, 3, 4, 5, 10]
[-1, 0, 3, 4, 4, 5, 10]

Мало того, с помощью функции bisect() можно отдельно вычислить индекс добавляемого элемента:

for x in data:
    pos = bisect.bisect(sd, x)
    bisect.insort(sd, x)
    print(pos, sd)

Получим:

0 [4]
0 [3, 4]
0 [-1, 3, 4]
1 [-1, 0, 3, 4]
4 [-1, 0, 3, 4, 10]
4 [-1, 0, 3, 4, 5, 10]
4 [-1, 0, 3, 4, 4, 5, 10]

Конечно, если используется функция insort(), то вызывать функцию bisect() не имеет смысла, т.к. insort() самостоятельно вычисляет эту позицию. Функция bisect() имеет смысл тогда, когда алгоритм вставки реализуется нами самостоятельно и нужно просто знать, куда добавить новый элемент, сохраняя порядок сортировки.

На самом деле функции insort() и bisect() – это псевдонимы (алиасы) функций:

• insort_right(list, x[, lo=0, hi=len(a)]) – вставка элемента x справа от повторяющихся значений;
• bisect_right(list, x[, lo=0, hi=len(a)]) – определение позиции вставляемого значения x справа от повторяющихся значений.

Например, при выполнении программы:

data = (2, 3, 4, 2, 3, 4)
sd = []
 
for x in data:
    pos = bisect.bisect_right(sd, x)
    bisect.insort_right(sd, x)
    print(pos, sd)

Увидим следующие позиции вставки элементов с дублями:

0 [2]
1 [2, 3]
2 [2, 3, 4]
1 [2, 2, 3, 4]
3 [2, 2, 3, 3, 4]
5 [2, 2, 3, 3, 4, 4]

А если заменить методы bisect_right() и insort_right() на bisect_left() и insort_left():

for x in data:
    pos = bisect.bisect_left(sd, x)
    bisect.insort_left(sd, x)
    print(pos, sd)

то увидим немного другой результат:

0 [2]
1 [2, 3]
2 [2, 3, 4]
0 [2, 2, 3, 4]
2 [2, 2, 3, 3, 4]
4 [2, 2, 3, 3, 4, 4]

Теперь дублирующие значения вставляются слева от соответствующих повторяющихся цепочек данных.

Итак, использование модуля bisect позволяет значительно повысить производительность операций для поддержания порядка сортировки длинных упорядоченных последовательностей. Короткие последовательности (до 100 элементов) можно каждый раз сортировать и обычным методом sort(). Это не сильно скажется на объеме вычислений. Однако при длинных списках использование модуля bisect позволяет значительно повышать производительность, особенно если операция сравнения двух элементов списка требует значительных вычислительных затрат.

Курс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs

Видео по теме

#1. Тип данных complex

#2. Множество frozenset

#3. Перечисления (enum). Класс Enum

#4. Классы IntEnum и StrEnum

#5. Именованные кортежи namedtuple модуля collections

#6. Словарь defaultdict модуля collections

#7. Упорядоченный словарь OrderedDict

#8. Класс Counter модуля collections

#9. Класс ChainMap модуля collections

#10. Функции pprint() и pformat(). Класс PrettyPrinter

#11. Очереди типов FIFO и LIFO

#12. Очередь deque модуля collections

#13. Класс Queue модуля queue

#14. Классы LifoQueue и PriorityQueue модуля queue

#15. Понятие кучи (heap). Модуль heapq

#16. Класс array. Методы класса array

#17. Модуль bisect - сортировка в моменте

#18. Функции copy() и deepcopy() модуля copy

#19. Магические методы __copy__() и __deepcopy__()

#20. Декораторы partial и partialmethod модуля functools

#21. Функция update_wrapper() и декоратор wraps

#22. Декоратор lru_cache модуля functools

#23. Функция reduce() модуля functools

#24. Декоратор singledispatch модуля functools

#25. Модуль abc (Abstract Base Classes)

#26. Модуль itertools. Функция chain()

#27. Функции zip_longest(), islice() и tee()

#28. Комбинаторные функции модуля itertools

#29. Функции фильтрации из модуля itertools

#30. Функции-генераторы модуля itertools

#31. Функции groupby() и starmap() модуля itertools

#32. Функции модуля operator. Классы itemgetter и attrgetter

#33. Функция methodcaller() модуля operator

#34. Функции модуля time. Функции time() и ctime()

#35. Функции monotonic(), perf_counter() и process_time()

#36. Функции localtime(), gmtime(), mktime(), strftime() и strptime()

#37. Модуль datetime. Классы time и date

#38. Арифметика дат. Класс timedelta

#39. Класс datetime модуля datetime

#40. Модуль calendar. Основные функции, классы и методы

#41. Модуль math (часть 1)

#42. Модуль math (часть 2)

#43. Модуль math (часть 3)

#44. Класс Decimal для точного представления вещественных чисел

#45. Методы класса Decimal

#46. Функции с числами Decimal. Глобальный и локальный контексты

#47. Класс Fraction модуля fractions

#48. Стандартные функции с объектами класса Fraction

#49. Модуль random стандартной библиотеки

#50. Введение в модуль statistics

#51. Вычисление дисперсий и ковариаций с помощью модуля statistics

#52. Введение в модуль re. Символьные классы

#53. Квантификаторы регулярных выражений

#54. Группировка и сохранение в регулярных выражениях

#55. Опережающие (lookahead) проверки. Флаги

#56. Ретроспективные (lookbehind) проверки

#57. Объект Match. Методы search(), finditer() и findall()

#58. Методы match(), split(), sub(), subn(), compile()

#59. Функции модуля os.path для анализа файловых маршрутов

#60. Дополнительные функции модуля os.path

#61. Классы PurePosixPath и PureWindowsPath модуля pathlib

#62. Классы PosixPath и WindowsPath модуля pathlib