Python:如何从给定的键中获取最接近的键？

给定字典:

sample = {
    '123': 'Foo',
    '456': 'Bar',
    '789': 'Hello',
    '-111': 'World'
}

从字典中获取最接近(或更少)键的最高效方法(方法和/或数据结构)是什么？

笔记:
1.即使键是字符串，比较也应该是数字。
2.键可以是“负”键。

例子:

get_nearest_less_element(sample, '456') # returns 'Bar'
get_nearest_less_element(sample, '235') # returns 'Foo'
get_nearest_less_element(sample, '455') # returns 'Foo'
get_nearest_less_element(sample, '999') # returns 'Hello'
get_nearest_less_element(sample, '0') # returns 'World'
get_nearest_less_element(sample, '-110') # returns 'World'
get_nearest_less_element(sample, '-999') # should return an error since it is beyond the lower bound

附加问题:
给定相同的数据集，sorted OrderedDict或List of Tuples或任何其他python数据结构会是更好的方法吗？

最佳答案

def get_nearest_less_element(d, k):
    k = int(k)
    return d[str(max(key for key in map(int, d.keys()) if key <= k))]

编辑以使用@Paul Hankin的代码进行更新，但是使用<=我不确定它根本不需要分支。将所有键转换为数字，找到小于或等于k的键，获得最大的键-如果k在其中，您将得到它，否则将得到下一个最大的键-转换回字符串并在字典。

测试:https://repl.it/C2dN/0

我不知道这是否是最有效的主意。由于获取的字典是无序的，因此您必须遍历每个元素，因为它们中的任何一个都可能是下一个最大的，并且由于需要数字比较，因此必须将它们全部转换为整数。在我看来，任何其他结构都将花费更多的初始化成本，因为您必须先仔细检查每一项，然后才能将其放入您的结构中。

但这取决于您的用例-如果k很可能出现在字典中，则将我的代码更改为if k in d: return d[k] else: ...分支是有意义的，因为在这种情况下不执行生成器表达式会更快。如果它很可能不在字典中，那将无济于事。

下面是对它们的键进行排序的伪代码(未经测试的)版本-使用一次会较慢，但查询很多时可能会更快:

# cache to store sorted keys between function calls
# nb. you will have to invalidate this cache (reset to [])
# when you get a new dictionary
sorted_keys = []

def get_nearest_less_element(d, k):
    if k in d:               # quick return if key is in dict
        return d[k]
    else:

        # costly sort of the keys, only do this once
        if not sorted_keys:
            sorted_keys = sorted(int(key) for key in d.keys())

        # quick run through the sorted key list up
        # to latest item less than k
        k = int(k)
        nearest = sorted_keys[0]
        for item in sorted_keys:
            if item < k:
                nearest = item
            else:
                break

         return d[str(item)]

关于Python:如何从给定的键中获取最接近的键？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37851131/