python: odzyskiwanie klucza sufitu i klucza podłogowego w słowniku lub zestawie

Question

Mam słownik zawierający kilka klawiszy całkowitych. dla kluczy, których nie mam, chciałbym móc pobrać najmniejsze i największe klucze tuż przed i po kluczu, który chcę odzyskać, ale to nie istnieje.
Klasa Treemap w java ma dwie metody dokładnie to: ceilingkey() i floorkey().

Jak mogę to zrobić w pythonie?

Jako przykład mam słownika tak:

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

Jeśli mogę prosić o klucz 1, będę pobierać "1", ale jeśli spojrzeć na klucz 3, powinienem dostać KeyError i stąd można uzyskać floor(3) = 1 i 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) 

Nie jestem pewien, jak chcesz obsługiwać warunki brzegowe. Zauważ, że spowoduje to wyjątek (ValueError), jeśli pytasz o podłogę/sufit klucza, który jest niższy/wyższy niż cokolwiek w dyktafonie.

Answer 2

można użyć modułu bisect tutaj, w przypadku, gdy klawisz nie znaleziono potem może znaleźć wartości suficie i podłodze w O(log N) czasie .:

>>> 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} 

Tworzenie posortowaną listę kluczy dla bisect:

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

teraz korzystać z funkcji:

>>> get_value(dic, 4) 
5 

Dla 3 zarówno suficie i podłodze są dostepne:

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

0 jest mniejszy niż najmniejszy klucz, więc ten powróci tylko ceil:

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

Dla kluczy większych niż największy klucz tylko wartość floor będzie być zwrócony:

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

Answer 3

Oto zabawa z wykorzystaniem 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