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

Question

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

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

Спасибо!

Answer 1

Посмотрите на пополам .

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

Answer 2

Вы можете получить лучшее время, чем метод перечисления / генератора, использующий itertools; Я думаю, что itertools обеспечивает более быструю реализацию базовых алгоритмов для разработчиков производительности во всех нас. Но пополам может быть еще быстрее.

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)

Я удивляюсь разнице между подходом, описанным здесь, и подходом, указанным для вашего вопроса в примерах документации, в отношении идиомы / скорости. Они показывают подход для нахождения значения, но усеченные до первой строки возвращают индекс. Я предполагаю, что поскольку он называется «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)

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