W Pythonie, jak znaleźć indeks pierwszej wartości większej niż próg w posortowanej liście?

Question

W Pythonie, jak znaleźć indeks pierwszej wartości większej niż próg w posortowanej liście?

Mogę wymyślić kilka sposobów na zrobienie tego (wyszukiwanie liniowe, ręcznie napisana dychotomia, ...), ale szukam czystego i racjonalnie wydajnego sposobu na zrobienie tego. Ponieważ jest to prawdopodobnie dość powszechny problem, jestem pewien, że doświadczeni pracownicy SOFT mogą pomóc!

Dzięki!

Answer 1

Spójrz na bisect.

import bisect 

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] 

bisect.bisect(l, 55) # returns 7 

porównać go z przeszukiwanie liniowe:

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

można dostać lepszego czasu niż wyliczyć podejścia generatora/Korzystanie itertools; Myślę, że itertools zapewnia szybsze implementacje podstawowych algorytmów, dla twórców wydajności w każdym z nas. Ale bisect może być jeszcze szybszy.

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) 

Zastanawiam się o różnicy między podejściem przepoławiać pokazanej tu i wymieniony na swoje pytanie w przykładach doc miarę idiom/prędkości. Pokazują one podejście do znalezienia wartości, ale obcięte do pierwszej linii, zwracają indeks. Domyślam się, że skoro nazywa się "bisect_right" zamiast "bisect", prawdopodobnie patrzy tylko z jednego kierunku. Biorąc pod uwagę, że twoja lista jest posortowana i chcesz większej niż ta, może to być największa gospodarka wyszukiwania.

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) 

Interesujące pytanie.