En Python, ¿cómo se encuentra el índice del primer valor mayor que un umbral en una lista ordenada?

Question

En Python, ¿cómo se encuentra el índice del primer valor mayor que un umbral en una lista ordenada?

Puedo pensar en varias formas de hacer esto (búsqueda lineal, dicotomía escrita a mano, ..), pero estoy buscando una manera limpia y bastante eficiente de hacerlo. Dado que probablemente sea un problema bastante común, estoy seguro de que los SOE experimentados pueden ayudar.

Gracias!

Answer 1

Echa un vistazo a bisect.

import bisect 

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

bisect.bisect(l, 55) # returns 7 

compararlo con búsqueda lineal:

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

podría obtener un mejor momento que el enfoque de enumeración/generador usando itertools; Creo que itertools proporciona implementaciones más rápidas de los algoritmos subyacentes, para los creadores de rendimiento en todos nosotros. Pero bisect puede ser aún más rápido.

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) 

me pregunto acerca de la diferencia entre el enfoque bisect se muestra aquí y con el listado para su pregunta en los ejemplos doc, por lo que modismo/velocidad. Muestran un enfoque para encontrar el valor, pero truncado en la primera línea, devuelve el índice. Supongo que, dado que se llama "bisect_right" en lugar de "bisect", probablemente solo se ve desde una dirección. Dado que su lista está ordenada y desea mayor que, esta podría ser la mejor economía de búsqueda.

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) 

Interesante pregunta.