В Python, как вы находите индекс первого значения, превышающего пороговое значение в отсортированном списке?

Я могу придумать несколько способов сделать это (линейный поиск, рукописная дихотомия,..), но я ищу чистый, достаточно эффективный способ сделать это. Поскольку это, вероятно, довольно распространенная проблема, я уверен, что опытные SOers могут помочь!

Ответы

Ответ 1

Посмотрите 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

Ответ 2

Вы можете получить лучшее время, чем метод 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)

Интересный вопрос.