Python中的自定义字典查找

Question

如果我有一个字典，像这样：

>>> d = {10: 3, 100: 2, 1000: 1}

我可以输入类似这样的内容：

>>> d.get(10), d.get(100), d.get(1000)
(3, 2, 1)

不过我希望，如果找不到给定的键，能返回与给定键最接近的那个键对应的值：

>>> d.get(20), d.get(60), d.get(200)
(3, 2, 2)

但在Python中，结果是这样的：

(None, None, None)

有没有什么Python的好方法可以实现我描述的这种行为？

谢谢

Answer 1

看看这个教程 模糊匹配字典。

Answer 2

bisect模块可以快速找到一个有序列表中插入新元素的位置。

from bisect import bisect_right

def closest_matches(data, query):
    keys = sorted(data)
    return [data[i] for i in (min(map(abs, (keys[p-1], keys[p]))) for p in (bisect_right(keys, k) for k in query))]

>>> d = {10: 3, 100: 2, 1000: 1}
>>> closest_matches(d, [20, 60, 200])
[3, 3, 2]

Answer 3

你可以从 dict 这个字典类型去派生一个新的类型，这样就可以改变 get() 方法的行为：

class ClosestDict(dict):
    def get(self, key):
        key = min(self.iterkeys(), key=lambda x: abs(x - key))
        return dict.get(self, key)

d = ClosestDict({10: 3, 100: 2, 1000: 1})
print (d.get(20), d.get(60), d.get(200))

打印输出

(3, 2, 2)

需要注意的是，get() 方法的复杂度不再是 O(1)，而变成了 O(n)。