python: получение ключа потолка и слово в словаре или наборе

Question

У меня есть словарь с кучей целых ключей. для ключей, которых у меня нет, я бы хотел получить самые маленькие и самые большие ключи прямо до и после того, как они будут сохранены, но этого не существует.
Класс Treemap в java имеет два метода, которые выполняют именно это: 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), если вы просите пол/потолок ключа, который ниже/выше, чем что-либо в dict.

Answer 2

Вы можете использовать bisect модуль здесь, в случае, если клавишу не найдено, то он может найти значение потолка и пола в 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 

Для 3 и потолке и полу доклада доступен:

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

0 меньше наименьшего ключа, так что это будет возвращать только ceil:

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

Для ключей больше, чем самый большой ключ только floor значение будет не возвращается:

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

Answer 3

Здесь вы найдете веселый, используя 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