Python：从给定的输入键中查找字典中最接近的键

Question

Python：从给定的输入键中查找字典中最接近的键

28

我有一个字典形式的数据... 现在，我从用户那里获取输入，它可以是任何东西。我正在尝试做以下事情。如果键存在，则从字典中提取该值。如果不存在，则提取最接近的（按数字意义）。例如，如果输入键为200，并且键如下：....

197,202,208...

那么可能202是离200最近的键。

从算法的角度来看，这是很简单的。但是有没有一种Pythonic的方法来实现呢？

谢谢

- frazman

5

需要使用“字典”还是类似于字典的对象就足够了？如果您使用二叉树或排序列表，则可以使用二分查找以O(log n)时间找到最接近的键。 - Daniel Pryden

2

从算法的角度来看，这是很直接的。我理解你对O(n)的解决方案没有问题，因为O(log n)的解决方案相对来说不太直接。 - Laurence Gonsalves

6个回答

33

这是您的函数单行显示：

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

- Will

3

不幸的是，每次查找都会评估min(data.keys()...)，即使键存在于数据中。也许可以将get的逻辑分解为三元运算符：data[num] if num in data else data[min(data.keys(), key=lambda k: abs(k-num))]。 - PaulMcG

1

很高兴能帮忙，但是if d.has_key(k)已经被弃用，推荐使用if k in d。 - PaulMcG

19

不要使用OrderedDict和bisect，考虑使用sortedcontainers模块中的SortedDict类型。它是一个纯Python实现且快如C的实现，包括有序列表、有序字典和有序集合类型，100％测试覆盖率和数小时压力测试。

使用SortedDict可以为所需的键执行bisect。例如：

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

该函数使用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是符合Python风格的！

- GrantJ

SortedDict() 如何处理负数键值？ - cosmictypist

@christylynn002 请在 https://github.com/grantjenks/sorted_containers/issues 上开一个问题。 - GrantJ

这个问题解决了吗？ - Paebbels

1

@Paebbels 没有问题被打开。我自己从来没有复现过。 - GrantJ

1

@ogurets 很好的观察！我现在明白了之前的代码在 index 等于 0 时可能会包含最大的键。我已经更新了 sortedcontainers 的第二个版本的代码。最好使用 irange 而不是被弃用的 iloc。 - GrantJ

显示剩余2条评论

1

如果你只有一个Python字典，那么你最好的选择就是检查字典中的所有条目（就像Will的答案一样）。然而，如果你想以比这更高效的方式找到最接近的键（即在O(log N)而不是O(N)中），你需要某种平衡树。

不幸的是，我认为Python标准库中没有这样的数据结构——因为Pythonic的方法是使用字典。因此，如果你希望在大型映射上进行多个这样的查询，你最好的选择可能是找到一个扩展库，甚至自己编写...

- comingstorm

1

请查看 bisect 以获取您所描述的内容。创建一个具有键的 bisect 和键值映射的 dict 的类。使用 bisect 在键列表中查找新键的适当插入点，然后检查相邻值以查看哪个更接近。 - PaulMcG

0

这应该做你想要的事情（除了从键中获取它，但你可以自己找出来：)。

f = lambda a,l:min(l,key=lambda x:abs(x-a))
numbers = (100, 200, 300, 400)
num = int(raw_input())
print 'closest match:', f(num, numbers)

注意：f 来自于这个问题。

- John Doe

0

使用sortedcontainers.SortedDict，您可以像这样做：

def closest_item(sdict, key):
    if len(sdict) == 0:
        raise KeyError('No items in {sdict.__class__.__name__}')

    if len(sdict) == 1:
        return next(iter(sdict.items()))

    idx_before = next(sdict.irange(minimum=key), None)
    idx_after = next(sdict.irange(maximum=key, reverse=True), None)

    if idx_before is None:
        idx = idx_after

    elif idx_after is None:
        idx = idx_before
    else:
        idx = min(idx_before, idx_after, key=lambda x: abs(x - key))

    return idx, sdict[idx]

- MaxNoe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brian Larsen · Accepted Answer

由于字典键没有特定的顺序，因此这个问题变得更加困难。如果您可以调整字典的制作方式，使它们有序（就像您的示例一样），并且使用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)