Модуль bisect обеспечивает поддержку вставки значений в отсортированный список, без необходимости сортировать этот список после каждой вставки. Для длинных списков элементов с дорогостоящими операциями сравнения это может быть улучшением по сравнению с более распространенным подходом. Модуль называется "bisect", потому что он использует базовый алгоритм деления пополам для выполнения своей работы. Исходный код может быть наиболее полезным в качестве рабочего примера алгоритма.
При написании чувствительного ко времени кода с использованием bisect.bisect() и bisect.insort() имейте в виду следующие мысли:
insort() равны O(n), потому что на этапе логарифмического поиска преобладает этап вставки с линейным временем.functools.cache(), чтобы избежать дублирования вычислений. В качестве альтернативы рассмотрите возможность поиска в массиве предварительно вычисленных ключей, чтобы найти точку вставки (как показано в разделе примеров ниже).Функции модуля bisect полезны для поиска точек вставки, но могут быть сложными или неудобными в использовании для общих задач поиска. Следующие пять функций показывают, как преобразовать их в стандартные поисковые запросы для отсортированных списков:
def index(a, x): 'Находит крайнее левое значение, точно равное x' i = bisect_left(a, x) if i != len(a) and a[i] == x: return i raise ValueError def find_lt(a, x): 'Находит крайнее правое значение меньшее, чем x' i = bisect_left(a, x) if i: return a[i-1] raise ValueError def find_le(a, x): 'Находит крайнее правое значение меньше или равно x' i = bisect_right(a, x) if i: return a[i-1] raise ValueError def find_gt(a, x): 'Находит крайнее левое значение больше, чем x' i = bisect_right(a, x) if i != len(a): return a[i] raise ValueError def find_ge(a, x): 'Находит крайний левый элемент больше или равен x' i = bisect_left(a, x) if i != len(a): return a[i] raise ValueError
bisect:# test.py from bisect import bisect_left def binary_search(a, x, lo=0, hi=None): if hi is None: hi = len(a) # поиск индекса `x` pos = bisect_left(a, x, lo, hi) # проверка и возврат результата return pos if pos != hi and a[pos] == x else -1 # запускаем: $python3 -i test.py >>> lst = [0, 1, 2, 5, 6, 8] >>> binary_search(lst, 5) # 3 >>> binary_search(lst, 4) # -1
Аргументы функции binary_search() следуют тому же шаблону, что и функции в модуле bisect . То есть - ищем значение x в списке a между индексами lo и hi .
Единственная интересная строка - это оператор return, где проверяется, действительно ли значение x находится в списке, если да, то возвращаем его позицию, в противном случае мы возвращаем -1.
Функция bisect.bisect() может быть полезна для поиска в числовой таблице. В этом примере используется bisect() для поиска буквенной оценки за экзамен (скажем) на основе набора упорядоченных числовых точек останова: 90 и выше - это "A", от 80 до 89 - "B" и так далее:
# test.py from bisect import bisect def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'): i = bisect(breakpoints, score) return grades[i] # Запускаем `$python3 -i test.py` >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] # ['F', 'A', 'C', 'C', 'B', 'A', 'A']
Представим, что есть ряд интервалов, и необходимо вычислить соответствующее значение для каждого интервала. Первое решение, что приходит на ум:
def interval_to_value(val): if val <= 100: return 0 elif 100 < val <= 300: return 1 elif 300 < val <= 500: return 2 elif 500 < val <= 800: return 3 elif 800 < val <= 1000: return 4 elif val > 1000: return 5
Есть гораздо более приятное решение, использующее bisect.bisect_left():
# test.py from bisect import bisect_left def interval_to_value(interval, val): return bisect_left(interval, val)
Это не только чистое решение, но и очень быстрое. Его можно расширить, если потребуется неестественный порядок или, например, если необходимо вернуть что-то другое, например строку:
# запускаем: $python3 -i test.py >>> interval = [100, 300, 500, 800, 1000] >>> znachenie = ['absent', 'low', 'average', 'high', 'very high', 'extreme'] >>> val = 325 >>> i = interval_to_value(interval, val) >>> znachenie[i] # average >>> val = 32 >>> i = interval_to_value(interval, val) >>> znachenie[i] # 'absent'
Еще одна вещь, для которой можно использовать bisect - это поиск по префиксу. Предположим, есть очень большой список слов и нужно искать слова на основе заданного префикса:
# test.py from bisect import bisect_left def prefix_search(wordlist, prefix): try: # находим индекс слова в списке `wordlist`, # содержащие `prefix` index = bisect_left(wordlist, prefix) # возвращаем слово return wordlist[index] except IndexError: # или возвращаем False return False
Функцию prefix_search() можно легко изменить, чтобы зацикливаться на индексе и возвращать все слова, начинающиеся с префикса.
# запускаем `$python3 -i test.py` >>> words = ['another', 'data', 'date', 'hello', 'text', 'word'] >>> prefix_search(words, 'dat') # 'data' >>> prefix_search(words, 'he') # 'hello' >>> prefix_search(words, 'xa') # False
Если имеется достаточно большой список слов, то использование bisect становится намного быстрее по сравнению с простым перебором списка.
Например, имеем список вида [(val, key), (val1, key1), ...].
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)] # предварительно отсортируем список по цифровым ключам. >>> data.sort(key=lambda r: r[1]) >>> data # [('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)] # предварительно вычислим список ключей. >>> keys = [r[1] for r in data] >>> keys # [0, 1, 5, 8] >>> 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)