de la lista de enteros, obtener el número más cercano a un valor dado

Dada una lista de 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 

¿Hay alguna forma rápida de hacer esto?

Si no estamos seguros de que la lista esté ordenada, podríamos usar la función min() incorporada , para encontrar el elemento que tiene la distancia mínima desde el número especificado.

 >>> min(myList, key=lambda x:abs(x-myNumber)) 4 

Tenga en cuenta que también funciona con dicts con teclas int, como {1: "a", 2: "b"} . Este método lleva tiempo O (n).


Si la lista ya está ordenada, o puede pagar el precio de ordenar la matriz solo una vez, use el método de bisección ilustrado en la respuesta de @Luritz, que solo toma O (log n) tiempo (sin embargo, compruebe que la lista ya está clasificada como O (n) y la clasificación es O (n log n).

Si te refieres a la ejecución rápida en lugar de la escritura rápida, min no debe ser tu arma preferida, excepto en un caso de uso muy estrecho. La solución min necesita examinar cada número en la lista y hacer un cálculo para cada número. Usar bisect.bisect_left en bisect.bisect_left lugar es casi siempre más rápido.

El “casi” viene del hecho de que bisect_left requiere 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 en paz. Incluso si no, siempre y cuando no tenga que ordenar antes cada vez que llame a takeClosest , es probable que el módulo takeClosest salga a la cabeza. Si tiene dudas, pruebe ambos y observe la diferencia del mundo real.

 from bisect import bisect_left def takeClosest(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 a la mitad repetidamente una lista y descubriendo en qué mitad de myNumber debe estar mirando el valor medio. Esto significa que tiene un tiempo de ejecución de O (log n) en oposición al tiempo de ejecución de O (n) de la respuesta más votada . Si comparamos los dos métodos y suministramos ambos con un myList ordenado, estos son los resultados:

 $ python -m timeit -s "
 de la importación más cercana takeClosest
 de la importación aleatoria randint
 a = rango (-1000, 1000, 10) "" takeClosest (a, randint (-1100, 1100)) "

 100000 bucles, lo mejor de 3: 2.22 usec por bucle

 $ python -m timeit -s "
 de la importación más cercana with_min
 de la importación aleatoria randint
 a = rango (-1000, 1000, 10) "" with_min (a, randint (-1100, 1100)) "

 10000 bucles, lo mejor de 3: 43.9 usec por bucle

Entonces, en esta prueba en particular, la bisect es casi 20 veces más rápida. Para listas más largas, la diferencia será mayor.

¿Qué sucede si nivelamos el campo de juego eliminando la condición previa de que myList debe ordenarse? Digamos que takeClosest una copia de la lista cada vez que se llama a takeClosest , mientras que no modificamos la solución min . Utilizando la lista de 200 elementos en la prueba anterior, la solución bisect sigue siendo la más rápida, aunque solo en 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 la que min sigue perdiendo es que la clasificación se realiza en un código c altamente optimizado, mientras que min tiene que avanzar para llamar una función lambda para cada elemento. A medida que myList crece en tamaño, la solución min eventualmente será más rápida. Tenga en cuenta que tuvimos que astackr todo a su favor para que la solución min ganara.

 >>> takeClosest = lambda num,collection:min(collection,key=lambda x:abs(x-num)) >>> takeClosest(5,[4,1,88,44,3]) 4 

Un lambda es una forma especial de escribir una función “anónima” (una función que no tiene nombre). Puede asignarle el nombre que desee porque una lambda es una expresión.

La forma “larga” de escribir lo anterior sería:

 def takeClosest(num,collection): return min(collection,key=lambda x:abs(x-num)) 
 def closest(list, Number): aux = [] for valor in list: aux.append(abs(Number-valor)) return aux.index(min(aux)) 

Este código le dará el índice del número de número más cercano en la lista.

La solución dada por KennyTM es la mejor en general, pero en los casos en que no puede usarla (como brython), esta función hará el trabajo.

Iterar sobre la lista y comparar el número más cercano actual con abs(currentNumber - myNumber) :

 def takeClosest(myList, myNumber): closest = myList[0] for i in range(1, len(myList)): if abs(i - myNumber) < closest: closest = i return closest 

Es importante tener en cuenta que la idea de la sugerencia de Lauritz de utilizar bisect no encuentra realmente el valor más cercano en MyList a MyNumber. En su lugar, bisect encuentra el siguiente valor en orden después de MyNumber en MyList. Entonces, en el caso de OP, obtendrías la posición de 44 en lugar de la posición de 4.

 >>> myList = [1, 3, 4, 44, 88] >>> myNumber = 5 >>> pos = (bisect_left(myList, myNumber)) >>> myList[pos] ... 44 

Para obtener el valor más cercano a 5, puede intentar convertir la lista a una matriz y usar argmin de numpy como tal.

 >>> import numpy as np >>> myNumber = 5 >>> myList = [1, 3, 4, 44, 88] >>> myArray = np.array(myList) >>> pos = (np.abs(myArray-myNumber)).argmin() >>> myArray[pos] ... 4 

No sé qué tan rápido sería esto, sin embargo, mi conjetura sería “no muy”.

Ampliando la respuesta de Gustavo Lima. Lo mismo se puede hacer sin crear una lista completamente nueva. Los valores de la lista se pueden reemplazar con los diferenciales a medida que avanza el ciclo FOR .

 def f_ClosestVal(v_List, v_Number): """Takes an unsorted LIST of INTs and RETURNS INDEX of value closest to an INT""" for _index, i in enumerate(v_List): v_List[_index] = abs(v_Number - i) return v_List.index(min(v_List)) 
 myList = [1, 88, 44, 4, 4, -2, 3] v_Num = 5 print(f_ClosestVal(myList, v_Num)) ## Gives "3," the index of the first "4" in the list. 

Si puedo agregar a la respuesta de Lauritz

Para no tener un error de ejecución, no olvide agregar una condición antes de la línea bisect_left :

 if (myNumber > myList[-1] or myNumber < myList[0]): return False 

para que el código completo se vea como

 from bisect import bisect_left def takeClosest(myList, myNumber): """ Assumes myList is sorted. Returns closest value to myNumber. If two numbers are equally close, return the smallest number. If number is outside of min or max return False """ if (myNumber > myList[-1] or myNumber < myList[0]): return False 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