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

Question

给定一个字典:

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

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

注意:
1. 即使key是字符串，也应该是数值比较
2. keys可以是“negative”。

例子:

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 数据结构会是更好的方法吗？

Answer 1

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