title in python plot

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 forma limpia y 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

Compáralo con la 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

Puede obtener un mejor tiempo que el enfoque de enumerar / 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 de bisección que se muestra aquí y el que se enumera para su pregunta en los ejemplos de documento, en cuanto a 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.