python:检索字典或集合中的天花板键和楼层键

Question

我有一串带整数键的字典.对于我没有的密钥,我希望能够在它想要检索的密钥之前和之后检索最小和最大的密钥,但这不存在.
java中的Treemap类有两个方法正是这样做的:ceilingkey()和floorkey().

我怎么能用python做到这一点？

作为一个例子,我有一个这样的字典:

 { 1: "1", 4: "4", 6: "6" ..., 100: "100" } 

如果我要求钥匙1,我会检索"1",但如果我找钥匙3,我应该得到KeyError,因此能够得到floor(3) = 1和ceil(3) = 4.

Answer 1

def floor_key(d, key):
    if key in d:
        return key
    return max(k for k in d if k < key)

def ceil_key(d, key):
    if key in d:
        return key
    return min(k for k in d if k > key)

我不确定您要如何处理边界条件。请注意，ValueError如果您要求低于或高于该字典中任何内容的键的下限/上限，则会引发异常（）。

Answer 2

你可以在这里使用bisect模块，如果找不到 key，那么它可以及时找到 ceil 和 floor 值。O(log N)：

>>> import bisect
>>> from random import randint
def get_value(dic, key):
    if key in dic:
        return dic[key]
    else:
        ind = bisect.bisect(keys, key)
        d = {}
        if ind > 0:
            d["floor"] = dic[keys[ind-1]]
        if ind < len(keys):
            d["ceil"] = dic[keys[ind]]
        return d
...     
>>> dic = {randint(0,100) : x  for x in xrange(10)}
>>> dic
{65: 6, 4: 5, 1: 7, 40: 8, 10: 4, 50: 0, 68: 2, 27: 9, 61: 3}

创建一个排序的键列表bisect：

>>> keys = sorted(dic)
>>> keys
[1, 4, 10, 27, 40, 50, 61, 65, 68]

现在使用函数：

>>> get_value(dic, 4)
5

对于3ceil 和 floor 都可用：

>>> get_value(dic, 3)
{'ceil': 5, 'floor': 7}

0小于最小的键，所以这将只返回ceil：

>>> get_value(dic, 0)
{'ceil': 7}

对于大于最大键的键，只会floor返回值：

>>> get_value(dic, 70)
{'floor': 2}