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

Question

鉴于字典:

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

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

注意:
1.即使key是一个字符串,比较也应该是数字.
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数据结构是更好的方法吗？

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

Answer 2

如果键存在,则下面的模块返回值,否则它在小于输入键的键列表中找到最大键.

def get_nearest_less_element(sample,key):
  if key in sample:
    return sample[key]
  else:
    return sample[str(max(x for x in sample.keys() if int(x) < int(key)))]

print get_nearest_less_element(sample, '456')
print get_nearest_less_element(sample, '235')
print get_nearest_less_element(sample, '455')
print get_nearest_less_element(sample, '999')

输出:

酒吧

富

富

你好

编辑: 根据保罗的评论编辑答案.