在defaultdi中查找最近的键

Question

我使用defaultdicts来存储值列表，其中keys是可以观察到值的时段。 从所有感兴趣的时段列表中查找时，我希望在defaultdict中找到最接近的时段（注意：并非所有时段都存储在defaultdict中）。你知道吗

但是，由于defaultdict没有排序，下面的方法不会返回正确的值。你知道吗

是否有其他方法返回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]

对于上述情况，逻辑是

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

在这种情况下，为内置python函数指定可选的key参数非常有用。你知道吗

Answer 2

使用OrderedDict和排序键，可以使用二进制搜索。 对于大量的键，查找将比当前的方法快得多。你知道吗

因为需要最接近的键，所以需要同时找到最右边的键低于x和最左边的键高于x。找到最右边的键低于x的索引i后，另一个候选键（最左边的键高于x）将位于索引i+1。你知道吗

您需要确保这些索引仍在数组中。你知道吗

最后，您只需要计算从这两个值到x的距离。你知道吗

这是^{}和^{}的文件

Answer 3

我同意“septra”的说法，你需要euqlidean距离，但这在numpy身上也是可以实现的：

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])