В Python, как вы находите индекс первого значения, превышающего пороговое значение в отсортированном списке?
Я могу придумать несколько способов сделать это (линейный поиск, рукописная дихотомия,..), но я ищу чистый, достаточно эффективный способ сделать это. Поскольку это, вероятно, довольно распространенная проблема, я уверен, что опытные SOers могут помочь!
Спасибо!
Посмотрите bisect.
import bisect
l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
bisect.bisect(l, 55) # returns 7
Сравните его с линейным поиском:
timeit bisect.bisect(l, 55)
# 375ns
timeit next((i for i,n in enumerate(l) if n > 55), len(l))
# 2.24us
timeit next((l.index(n) for n in l if n > 55), len(l))
# 1.93us
Вы можете получить лучшее время, чем метод enumerate/generator, используя itertools; Я думаю, что itertools обеспечивает более быструю реализацию базовых алгоритмов, для разработчиков производительности во всех нас. Но bisect все еще может быть быстрее.
from itertools import islice, dropwhile
threshold = 5
seq = [1,4,6,9,11]
first_val = islice(dropwhile(lambda x: x<=threshold, seq),0,1)
result = seq.index(first_val)
Интересно, какая разница между приведенным здесь методом бисекции и тем, который указан для вашего вопроса в примерах doc, в отношении идиомы/скорости. Они показывают подход для нахождения значения, но усеченный в первую строку, он возвращает индекс. Я предполагаю, что, поскольку он называется "bisect_right" вместо "bisect", он, вероятно, только смотрит с одного направления. Учитывая, что ваш список отсортирован, и вы хотите больше, чем, это может быть самая большая поисковая экономика.
from bisect import bisect_right
def find_gt(a, x):
'Find leftmost value(switching this to index) greater than x'
return bisect_right(a, x)
Интересный вопрос.