J'ai des données sous forme de dictionnaire .. NOUVEAU je prends l'entrée de l'utilisateur et ça peut être n'importe quoi .. Et j'essaye de faire ce qui suit. Si la clé existe, refroidissez .. récupérez la valeur dans le dictionnaire. sinon, récupérez le plus proche (au sens numérique). Par exemple ... si la clé d'entrée est 200 et les touches sont comme: ....

197,202,208...

Alors probablement 202 est la clé la plus proche de 200 .. Maintenant, du point de vue de l'algorithme. c'est simple .. mais y a-t-il une façon pythonique de le faire? Merci

18
Mohit 29 oct. 2011 à 00:28

5 réponses

Meilleure réponse

Voici votre fonction sur une seule ligne:

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

Edit: pour ne pas évaluer le min lorsque la clé est dans le dict utiliser:

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

Ou si toutes les valeurs de data correspondent à True, vous pouvez utiliser:

data.get(num) or data[min(data.keys(), key=lambda k: abs(k-num))]
27
Will 30 oct. 2011 à 01:26

Cela devrait faire ce que vous voulez (moins l'obtenir à partir d'une clé, mais vous pouvez le comprendre :).

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)

Remarque: f provient de cette question.

0
Community 23 mai 2017 à 11:54

Si tout ce que vous avez est un dictionnaire Python, vous ne pouvez pas faire mieux que de vérifier toutes les entrées du dictionnaire (comme dans la réponse de Will). Cependant, si vous voulez trouver la clé la plus proche plus efficacement que cela (c'est-à-dire dans O(log N) au lieu de O(N)), vous voulez un arbre équilibré d'une certaine sorte.

Malheureusement, je ne crois pas que Python ait une telle infrastructure de données dans sa bibliothèque standard - car la manière Pythonique est d'utiliser un dict à la place. Donc, si vous vous attendez à faire beaucoup de ces requêtes sur une grande carte, votre meilleur choix peut être de trouver une bibliothèque d'extensions, ou même de lancer la vôtre ...

1
comingstorm 28 oct. 2011 à 20:57

Plutôt que d’utiliser OrderedDict et bissect, envisagez le SortedDict dans le sortedcontainers module. Il s'agit d'une pure Python et d'une implémentation rapide en C de liste triée, types de dict triés et types de jeux triés avec une couverture de test à 100% et des heures de stress.

Avec un SortedDict, vous pouvez couper en deux pour la clé souhaitée. Par exemple:

from itertools import islice
from sortedcontainers import SortedDict

def closest(sorted_dict, key):
    "Return closest key in `sorted_dict` to given `key`."
    assert len(sorted_dict) > 0
    keys = list(islice(sorted_dict.irange(minimum=key), 1))
    keys.extend(islice(sorted_dict.irange(maximum=key, reverse=True), 1))
    return min(keys, key=lambda k: abs(key - k))

La fonction closest utilise SortedDict.irange pour créer un itérateur de clés le plus proche de la clé donnée. Les clés sont bissectées avec une complexité d'exécution log(N).

>>> sd = SortedDict({-3: 'a', 0: 'b', 2: 'c'})
>>> for num in range(-5, 5):
...     key = closest(sd, num)
...     print('Given', num, ', closest:', key)
Given -5 , closest: -3
Given -4 , closest: -3
Given -3 , closest: -3
Given -2 , closest: -3
Given -1 , closest: 0
Given 0 , closest: 0
Given 1 , closest: 2
Given 2 , closest: 2
Given 3 , closest: 2
Given 4 , closest: 2

C'est Pythonic d'utiliser PyPI!

15
GrantJ 30 août 2018 à 19:36

Ce problème est rendu beaucoup plus difficile par le fait que les clés de dict ne sont pas dans un ordre particulier. Si vous pouvez jouer avec la façon dont vous créez les dict pour qu'ils soient dans l'ordre (comme votre exemple) et utiliser python> = 2.7, vous pouvez utiliser OrderedDict et bissect pour faire ce rapide comme l'éclair.

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

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

Il vous suffit ensuite de vérifier les éléments ind et ind-1 pour voir lequel est le plus proche, ce qui permet de faire beaucoup moins de calculs.


Comme souligné ci-dessous par Steven G, en Python3, le .keys () n'est pas seulement une liste et doit être changé en une seule.

bisect.bisect_left(list(a.keys()), 45.3)
28
Brian Larsen 5 janv. 2018 à 19:49
7934547