Python：指定された入力キーから辞書に最も近いキーを見つけよう

Question

私は辞書の形式でデータを持っています。 NOW私はユーザーからの入力を受け取り、それは何でもよい.. そして私は以下。 キーが存在する場合は、クール..ディクショナリから値を取得します。 もしそうでなければ、最も近いものを数値的に取り出す。ビューのアルゴリズムの観点から、今後

197,202,208... 

おそらく202が200に最も近いキーです.... .. ：入力キーexample..ifについては は200 あるなどのキーがあります。その真っ直ぐ前方..しかし、これを行うためのpythonic方法はありますか？ ありがとう

Answer 1

ここでは1行にあなたの関数です：

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

編集：キーは辞書の使用時に分を評価しないように：

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

またはdata内のすべての値がTrueと評価された場合は、

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

Answer 2

これは、あなたが望むことをしなければなりません（キーから抜くことはできませんが、それを理解することができます:)。

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) 

注：fは、this questionです。

Answer 3

あなたが持っているものがすべてPython辞書であれば、ウィルの答えのように、辞書のすべての項目をチェックするよりもうまくやることはできません。ただし、最も近いキーをそれよりも効率的に見つけたい場合（O(N)ではなくO(log N)）、ある種のバランスのとれたツリーが必要です。

残念ながら、私はPythonが標準ライブラリでそのようなデータ構造を持っているとは思っていません。Pythonの方法は代わりにdictを使うことです。あなたが大規模な地図上で多くのそのようなクエリを行うことを期待している場合は、あなたの最良の選択は、拡張ライブラリを見つけるか、またはあなた自身のロールを見つけることかもしれません...

Answer 4

この問題は、特別な順序ではありません。あなたがディクテーションをどのようにして順番に（あなたの例のように）することができ、python> = 2.7を使用すれば、OrderedDictとbisectを使ってこの雷を速くすることができます。

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

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

は、その後あなただけの要素 indと ind-1は、このように多くの、より少ない計算を行う、近いであるかを確認する必要があります。スティーブン・Gによって以下に指摘したように

---

は、のpython3に.keys（）はリストだけでなく、一つに変更しなければなりません。

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

Answer 5

むしろOrderedDictを使用して二分するよりも、sortedcontainersモジュールでSortedDictタイプを検討します。純粋なPythonで、並べ替えられたリスト、辞書、セット型のfast-as-C implementationで、100％のテストカバレッジとストレスの時間があります。あなたが目的のキーのために二等分することができますSortedDictで

。例：

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] 

PyPIを使用するのはPythonです！