De la lista de números enteros, obtenga el número más cercano a un valor dado
Dada una lista de números enteros, quiero encontrar qué número es el más cercano a un número que doy en la entrada:
>>> myList = [4, 1, 88, 44, 3]
>>> myNumber = 5
>>> takeClosest(myList, myNumber)
...
4
¿Existe alguna forma rápida de hacer esto?
Si no estamos seguros de que la lista esté ordenada, podríamos usar la función incorporadamin() para encontrar el elemento que tiene la distancia mínima del número especificado.
>>> min(myList, key=lambda x:abs(x-myNumber))
4
Tenga en cuenta que también funciona con dictados con claves int, como {1: "a", 2: "b"}. Este método lleva O(n) tiempo.
Si la lista ya está ordenada, o si podría pagar el precio de ordenar la matriz solo una vez, use el método de bisección ilustrado en la respuesta de @Lauritz , que solo toma O(log n) tiempo (tenga en cuenta, sin embargo, verificar si una lista ya está ordenada es O (n) y la clasificación es O(n log n).)
Cambiaré el nombre de la función take_closestpara que cumpla con las convenciones de nomenclatura de PEP8.
Si te refieres a ejecución rápida en lugar de escritura rápida, nomin debería ser tu arma preferida, excepto en un caso de uso muy limitado. La solución necesita examinar cada número de la lista y hacer un cálculo para cada número. Usarlo en su lugar es casi siempre más rápido.minbisect.bisect_left
El "casi" proviene del hecho de que bisect_leftrequiere que la lista esté ordenada para funcionar. Con suerte, su caso de uso es tal que puede ordenar la lista una vez y luego dejarla como está. Incluso si no es así, siempre que no necesite ordenar antes cada vez que llame take_closest, bisectes probable que el módulo salga primero. Si tiene dudas, pruebe ambos y observe la diferencia en el mundo real.
from bisect import bisect_left
def take_closest(myList, myNumber):
"""
Assumes myList is sorted. Returns closest value to myNumber.
If two numbers are equally close, return the smallest number.
"""
pos = bisect_left(myList, myNumber)
if pos == 0:
return myList[0]
if pos == len(myList):
return myList[-1]
before = myList[pos - 1]
after = myList[pos]
if after - myNumber < myNumber - before:
return after
else:
return before
Bisect funciona dividiendo repetidamente a la mitad una lista y descubriendo en qué mitad myNumberdebe estar mirando el valor medio. Esto significa que tiene un tiempo de ejecución de O(log n) en contraposición al tiempo de ejecución O(n) de la respuesta más votada . Si comparamos los dos métodos y les proporcionamos a ambos un sorted myList, estos son los resultados:
$ python -m tiempo -s " desde la importación más cercana take_closest de randint de importación aleatoria a = rango(-1000, 1000, 10)" "take_closest(a, randint(-1100, 1100))" 100.000 bucles, lo mejor de 3: 2,22 usec por bucle $ python -m tiempo -s " desde la importación más cercana con_min de randint de importación aleatoria a = rango(-1000, 1000, 10)" "with_min(a, randint(-1100, 1100))" 10.000 bucles, lo mejor de 3: 43,9 usos por bucle
Así que en esta prueba en concreto, bisectes casi 20 veces más rápido. Para listas más largas, la diferencia será mayor.
¿Qué pasa si nivelamos el campo de juego eliminando la condición previa que myListdebe resolverse? Digamos que ordenamos una copia de la lista cada vez que take_closest se llama, sin minmodificar la solución. Utilizando la lista de 200 elementos de la prueba anterior, la bisectsolución sigue siendo la más rápida, aunque sólo en aproximadamente un 30%.
¡Este es un resultado extraño, considerando que el paso de clasificación es O(n log(n)) ! La única razón por minla que todavía se está perdiendo es que la clasificación se realiza en código C altamente optimizado, mientras que mintiene que seguir llamando a una función lambda para cada elemento. A medida que myListcrezca en tamaño, la minsolución eventualmente será más rápida. Tenga en cuenta que tuvimos que apilar todo a su favor para que minganara la solución.
