9

I have a dictionary with a bunch of integer keys. for keys I don't have, I'd like to be able to retrieve the smallest and largest keys right before and after they key I want to retrieve but that does not exist.
The Treemap class in java has two methods doing exactly this: ceilingkey() and floorkey().

How can I do this with python?

As an example I have a dictionary like this:

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

If I ask for key 1, I'll retrieve "1", but if I look for key 3, I should get KeyError and hence be able to get floor(3) = 1 and ceil(3) = 4.

4

3 回答 3

7 
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请注意，如果您要求低于/高于字典中任何内容的键的地板/天花板，这将引发异常 ( )。

于 2013-07-25T17:04:52.590 回答
6

您可以在这里使用bisect模块，以防找不到密钥，然后它可以及时找到 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}
于 2013-07-25T17:14:41.970 回答
2

这是一个有趣的使用 bisect 的方法。

import bisect

def ceiling_key(d, key):
    keys = sorted(d.keys())
    idx = bisect.bisect_left(keys, key)
    if key in d:
        idx += 1
    return keys[idx]

def floor_key(d, key):
    keys = sorted(d.keys())
    idx = bisect.bisect_left(keys, key) - 1
    return keys[idx]


...

>>> ceiling_key(d, 1)
4
>>> ceiling_key(d, 2)
4
>>> ceiling_key(d, 4)
6
>>> ceiling_key(d, 3)
4
>>> ceiling_key(d, 2)
4
>>> ceiling_key(d, 1)
4
>>> ceiling_key(d, 0)
1
>>> ceiling_key(d, 6)
100
>>> floor_key(d, 6)
4
>>> floor_key(d, 7)
6
>>> floor_key(d, 101)
100
>>> floor_key(d, 100)
6
于 2013-07-25T17:22:31.790 回答