Рубрики
Без рубрики

bisect – поддерживать списки в отсортированном порядке

Автор оригинала: Doug Hellmann.

Цель:

Поддерживает список в отсортированном порядке без необходимости вызывать sort каждый раз, когда элемент добавляется в список.

Модуль bisect реализует алгоритм вставки элементов в список при сохранении списка в отсортированном порядке.

Вставка в отсортированном порядке

Вот простой пример, в котором insort () используется для вставки элементов в список в отсортированном порядке.

bisect_example.py

import bisect

# A series of random numbers
values  [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('New  Pos  Contents')
print('---  ---  --------')

l  []
for i in values:
    position  bisect.bisect(l, i)
    bisect.insort(l, i)
    print('{:3}  {:3}'.format(i, position), l)

Первый столбец выходных данных показывает новое случайное число. Второй столбец показывает позицию, в которой номер будет вставлен в список. Остаток каждой строки – это текущий отсортированный список.

$ python3 bisect_example.py

New  Pos  Contents
---  ---  --------
 14    0 [14]
 85    1 [14, 85]
 77    1 [14, 77, 85]
 26    1 [14, 26, 77, 85]
 50    2 [14, 26, 50, 77, 85]
 45    2 [14, 26, 45, 50, 77, 85]
 66    4 [14, 26, 45, 50, 66, 77, 85]
 79    6 [14, 26, 45, 50, 66, 77, 79, 85]
 10    0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
  3    0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84    9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 77    8 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
  1    0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]

Это простой пример. Фактически, учитывая объем обрабатываемых данных, может быть быстрее просто создать список, а затем один раз отсортировать его. Напротив, для длинных списков значительная экономия времени и памяти может быть достигнута с использованием такого алгоритма сортировки вставкой, как этот, особенно когда операция сравнения двух элементов списка требует дорогостоящих вычислений.

Обработка дубликатов

Показанный ранее набор результатов включает повторяющееся значение, 77 . Модуль bisect предоставляет два способа обработки повторов: новые значения могут быть вставлены либо слева от существующих значений, либо справа. Функция insort () на самом деле является псевдонимом для insort_right () , который вставляет элемент после существующего значения. Соответствующая функция insort_left () вставляет элемент перед существующим значением.

bisect_example2.py

import bisect

# A series of random numbers
values  [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('New  Pos  Contents')
print('---  ---  --------')

# Use bisect_left and insort_left.
l  []
for i in values:
    position  bisect.bisect_left(l, i)
    bisect.insort_left(l, i)
    print('{:3}  {:3}'.format(i, position), l)

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

$ python3 bisect_example2.py

New  Pos  Contents
---  ---  --------
 14    0 [14]
 85    1 [14, 85]
 77    1 [14, 77, 85]
 26    1 [14, 26, 77, 85]
 50    2 [14, 26, 50, 77, 85]
 45    2 [14, 26, 45, 50, 77, 85]
 66    4 [14, 26, 45, 50, 66, 77, 85]
 79    6 [14, 26, 45, 50, 66, 77, 79, 85]
 10    0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
  3    0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84    9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 77    7 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
  1    0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]

Смотрите также