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

Question

我有一个字典形式的数据..没有我从用户输入,它可以是任何东西..我试图做以下.如果密钥存在则冷却..从字典中获取值.如果没有,则获取最近的(在数字意义上).例如..如果输入键是200,键是这样的:....

197,202,208...

然后可能202是最接近200的键.现在,从算法的角度来看.它直截了当..但有一种pythonic方式来做到这一点？谢谢

Answer 1

由于dict键没有特定的顺序,这个问题变得更加困难.如果你可以玩你如何制作dict以便它们按顺序(就像你的例子)并使用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 2

这是你在一行上的功能:

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

编辑:当键在dict使用时不评估min:

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 3

而不是使用OrderedDict和bisect,请考虑sortedcontainers模块中的SortedDict类型.它是排序列表,排序字典和排序集类型的纯Python和快速实现,具有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

使用PyPI是Pythonic!