defaultdictで最も近いキーを見つける

Question

私はdefaultdictsを使って値のリストを格納しています。ここでは、keysが値を観測できる期間です。 興味のあるすべての期間のリストを調べると、私はdefaultdict（NB：すべての期間がdefaultdictに格納されているわけではありません）に最も近い期間を探したいと思います。

しかし、defaultdictsはソートされないため、以下の方法では正しい値が返されません。

defaultdictsに最も近い利用可能なキーを返す別の方法はありますか？

from collections import defaultdict 
import numpy as np 

def_dict = defaultdict(list) 
# entries that will be stored in the defaultdict 
reg_dict = {0: ["a", "b"], 2: ["c", "d"], 5: ["k", "h"], -3: ["i", "l"]} 

# store items from regular dict in defaultdict 
for k, v in reg_dict.items(): 
    def_dict[k] = v 

# Lookup periods 
periods = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8] 

for period in periods: 

    # this approach does not return the right keys as defaultdicts are not sorted 
    closest_key = np.abs(np.array(list(def_dict.keys())) - period).argmin() 

    print("period: ", period, " - looked up key: ", closest_key) 

これには次の値を返します。

period: -1 - looked up key: 0 
period: 0 - looked up key: 0 
period: 1 - looked up key: 0 
period: 2 - looked up key: 1 
period: 3 - looked up key: 1 
period: 4 - looked up key: 2 
period: 5 - looked up key: 2 
period: 6 - looked up key: 2 
period: 7 - looked up key: 2 
period: 8 - looked up key: 2 

Answer 1

私は理解して道を、あなたはこのような出力をしたいですか？

[0, 0, 0, 2, 2, 5, 5, 5, 5, 5] 

上記の場合、ロジックは、これらのような状況で有用であるPython関数に内蔵するためのオプションkeyパラメータを指定

closest_key = [min(def_dict.keys(), key = lambda x: abs(x - p)) for p in periods] 

あろう。

Answer 2

私はあなたがeuqlidean距離を必要とする@septraに同意するが、それは同様にnumpyので達成可能だ：OrderedDictとソートキーで

from collections import defaultdict 
import numpy as np 

def_dict = defaultdict(list) 
# entries that will be stored in the defaultdict 
reg_dict = {0: ["a", "b"], 2: ["c", "d"], 5: ["k", "h"], -3: ["i", "l"]} 

# store items from regular dict in defaultdict 
for k, v in reg_dict.items(): 
    def_dict[k] = v 

periods = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8] 
a = list(def_dict.keys()) 
for period in periods: 
    closest_key = np.sqrt(np.power(np.add(a, -period),2)).argmin() 
    # OR closest_key = np.abs(np.add(a, -period)).argmin() 

    print("period: ", period, " - looked up key: ", a[closest_key]) 

Answer 3

、あなたはバイナリ検索を使用することができます。 大量のキーの場合、ルックアップは現在の方法よりもはるかに高速です。

最も近いキーが必要なので、xより右下のキーとxよりも左のキーの両方を見つける必要があります。 xより右端のキーのインデックスiを見つけた後、もう1つの候補（xよりも左のキー）はインデックスi+1になります。

これらのインデックスが配列内にあることを確認する必要があります。

最後に、これらの2つの値からxまでの距離を計算するだけです。エリックが効率的に使用すると、バイナリ検索を使用する必要があり、これを行うために、言ったようにここで

はbisectとnp.searchsorted

Answer 4

ためのドキュメントです。しかし、キーの数が少ない場合、単純な線形検索で十分である。 defaultdictやOrderedDictを使用する必要はなく、キーをソートするだけです。

import numpy as np 

# entries 
reg_dict = {0: ["a", "b"], 2: ["c", "d"], 5: ["k", "h"], -3: ["i", "l"]} 

keys = np.array(sorted(reg_dict.keys())) 
print('keys', keys) 

# Lookup periods 
periods = np.arange(-1, 9) 

for period in periods: 
    closest_key = keys[np.abs(keys - period).argmin()] 
    print("period: ", period, " - looked up key: ", closest_key) 

出力

keys [-3 0 2 5] 
period: -1 - looked up key: 0 
period: 0 - looked up key: 0 
period: 1 - looked up key: 0 
period: 2 - looked up key: 2 
period: 3 - looked up key: 2 
period: 4 - looked up key: 5 
period: 5 - looked up key: 5 
period: 6 - looked up key: 5 
period: 7 - looked up key: 5 
period: 8 - looked up key: 5