In Python, come si trova l'indice del primo valore maggiore di una soglia in una lista ordinata?

Question

In Python, come si trova l'indice del primo valore maggiore di una soglia in una lista ordinata?

Posso pensare a diversi modi di fare questo (ricerca lineare, dicotomia scritta a mano, ..), ma sto cercando un modo pulito e ragionevolmente efficiente per farlo. Dato che probabilmente è un problema abbastanza comune, sono sicuro che SOers con esperienza può aiutare!

Grazie!

Answer 1

Dai un'occhiata allo bisect.

import bisect 

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

bisect.bisect(l, 55) # returns 7 

confrontarlo con ricerca lineare:

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

si potrebbe ottenere un tempo migliore rispetto al/approccio generatore enumerate utilizzando itertools; Penso che itertools fornisca implementazioni più veloci degli algoritmi sottostanti, per i venditori di prestazioni in tutti noi. Ma il bisect potrebbe essere ancora più veloce.

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) 

mi chiedo circa la differenza tra l'approccio bisect mostrato qui e quello elencato per la tua domanda negli esempi doc, per quanto linguaggio/velocità. Mostrano un approccio per trovare il valore, ma troncato in prima linea, restituisce l'indice. Immagino che dal momento che si chiama "bisect_right" invece di "bisect", probabilmente guarda solo da una direzione. Dato che la tua lista è ordinata e vuoi maggiore di, questa potrebbe essere la più grande economia di ricerca.

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) 

Interessante domanda.