Python: encuentre la clave más cercana en un diccionario de la clave de entrada dada

Question

Tengo una información en un diccionario ... NOw Tomo la entrada del usuario y puede ser cualquier cosa ... Y estoy tratando de hacer siguiendo. Si la clave existe, entonces genial ... recupera el valor del diccionario. si no, luego busque el más cercano (en el sentido numérico). Para example..if la tecla de entrada es de 200 y las teclas son como: ....

197,202,208... 

Entonces probablemente 202 es la clave más cercano a 200 .. Ahora, desde el punto de vista algoritmo. es directo ... pero ¿hay una manera pitónica de hacer esto? Gracias

Answer 1

aquí es su función en una línea:

data.get(num, data[min(data.keys(), key=lambda k: abs(k-num))]) 

de edición: a no evaluar el min cuando la llave está en el uso dict:

data[num] if num in data else data[min(data.keys(), key=lambda k: abs(k-num))] 

o si todos los valores en data evalúan a True puede usar:

data.get(num) or data[min(data.keys(), key=lambda k: abs(k-num))] 

Answer 2

Esto debería hacer lo que quiera (sin obtenerlo de una clave, pero puede averiguarlo :).

f = lambda a,l:min(l,key=lambda x:abs(x-a)) 
numbers = (100, 200, 300, 400) 
num = int(raw_input()) 
print 'closest match:', f(num, numbers) 

Nota: f es de this question.

Answer 3

Si todo lo que tiene es un diccionario de Python, no puedes hacer nada mejor que verificar todas las entradas en el diccionario (como en la respuesta de Will). Sin embargo, si quiere encontrar la clave más cercana de manera más eficiente que eso (es decir, en O(log N) en lugar de O(N)), quiere un árbol equilibrado de algún tipo.

Desafortunadamente, no creo que Python tenga esa estructura de datos en su biblioteca estándar, ya que la manera Pythonic es usar un dict en su lugar. Por lo tanto, si espera hacer muchas consultas de este tipo en un mapa grande, su mejor opción puede ser encontrar una biblioteca de extensión, o incluso hacer su propia ...

Answer 4

Este problema se hace mucho más difícil al ser las claves dict sin ningún orden en particular. Si puede jugar con la forma en que hace el dict para que estén en orden (como su ejemplo) y use python> = 2.7, puede usar OrderedDict y bisect para hacer que este rayo sea rápido.

import collections 
a = collections.OrderedDict() 
for i in range(100): 
    a[i] = i 

import bisect 
ind = bisect.bisect_left(a.keys(), 45.3) 

Entonces sólo tiene que comprobar elemento ind y ind-1 a ver que está más cerca, haciendo así mucho menos cálculos.

---

Como se ha señalado a continuación por Steven G, en python3 los .keys() no es sólo una lista y debe ser cambiado en uno.

bisect.bisect_left(list(a.keys()), 45.3) 

Answer 5

En lugar de utilizar OrderedDict y dividir en dos, considerar el tipo SortedDict en el módulo sortedcontainers. Se trata de un Python puro y fast-as-C implementation de listas ordenadas, dict y tipos de conjuntos con una cobertura de prueba del 100% y horas de estrés.

Con un SortedDict puede dividir en dos para obtener la clave deseada. Por ejemplo:

from sortedcontainers import SortedDict 
sd = SortedDict((key, value) for key, value in data) 

# Bisect for the index of the desired key. 
index = sd.bisect(200) 

# With that index, lookup the key. 
key = sd.iloc[index] 

# You can also look ahead or behind to find the nearest key. 
behind = sd.iloc[index - 1] 
ahead = sd.iloc[index + 1] 

¡Es Pythonic usar PyPI!