Python: 在字典中找到与给定输入键最接近的键

Question

我有一份数据，是以字典的形式存储的。现在我需要从用户那里获取输入，这个输入可以是任何东西。我想做的事情是这样的：如果这个输入的键在字典里存在，那就很好，直接从字典里取出对应的值。如果不存在，那就找一个数字上最接近的键。例如，如果用户输入的键是200，而字典里的键是这样的：

197,202,208...

那么可能202是离200最近的键。从算法的角度来看，这个过程很简单，但有没有更“pythonic”的方法来实现呢？谢谢！

Answer 1

与其使用OrderedDict和bisect，不如考虑使用SortedDict类型，这个类型在sortedcontainers模块中。它是用纯Python写的，而且是速度媲美C语言的实现，支持有序列表、有序字典和有序集合，并且经过了100%的测试覆盖和长时间的压力测试。

使用SortedDict，你可以快速找到想要的键。例如：

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

closest函数利用SortedDict.irange来创建一个迭代器，这个迭代器会返回离给定键最近的键。这个过程的时间复杂度是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

在Python中使用PyPI是很符合Python风格的做法！

Answer 2

这个问题变得很复杂，因为字典里的键没有特定的顺序。如果你能调整字典的创建方式，让它们有顺序（就像你例子中的那样），并且使用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，看看哪个更接近，这样就能减少很多计算。

---

正如Steven G在下面指出的，在Python3中，.keys()并不是一个列表，必须转换成列表。

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

Answer 3

这是你的一行函数：

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