map :: lower_bound() equivalente per la classe dict di python?

Question

Sto scrivendo un codice che richiede di recuperare il limite inferiore di una chiave (per semplicità, ignorare le chiavi che si trovano sotto la chiave più piccola nella raccolta).

In C++, utilizzando std :: map (come il tipo di dati più comparabile) vorrei semplicemente utilizzare lower_bound() per restituire l'iteratore.

mio Pythonfoo che non è grande, ma sto indovinando che (nel caso in cui Python non dispone già di un modo di fare questo), questo sarebbe un buon uso di una funzione lambda ...

Che cosa è il modo Python di recuperare la chiave con limite inferiore per un dato indice?

Nel caso in cui la domanda è troppo astratto, questo è quello che sto effettivamente cercando di fare:

Ho un dict Python indicizzato in base alla data. Voglio poter usare una data per cercare il dict e restituire il valore associato al lowerbound della chiave specificata.

Snippet segue:

mymap = { datetime.date(2007, 1, 5): 'foo', 
      datetime.date(2007, 1, 10): 'foofoo', 
      datetime.date(2007, 2, 2): 'foobar', 
      datetime.date(2007, 2, 7): 'foobarbar' } 

mydate = datetime.date(2007, 1, 7) 

# fetch lbound key for mydate from mymap 
def mymap_lbound_key(orig): 
    pass # return the lbound for the key 

Non voglio veramente un ciclo tra i tasti, cercando la prima chiave < = condizione chiave, a meno che non v'è alcuna alternativa migliore ...

Answer 1

Ancora Non sei sicuro di cosa sia il "limite inferiore": l'ultima data prima/dopo la data della query?

In ogni caso, poiché un ditt non impone un ordine intrinseco sulle sue chiavi, è necessaria una struttura diversa. Memorizza le tue chiavi in ​​una struttura che le mantiene ordinate e consente ricerche veloci.

La soluzione più semplice sarebbe quella di memorizzare le date ordinate in un elenco di (data, valore) e fare una ricerca binaria per ingrandire l'area desiderata. Se hai bisogno/vuoi prestazioni migliori, penso che un b-tree sia ciò di cui hai bisogno.

Answer 2

La classe Python dict non ha questa funzionalità; avresti bisogno di scriverlo da solo Sarebbe sicuramente conveniente se le chiavi fossero già ordinate, non è così, quindi si potrebbe fare una ricerca binaria su di esse ed evitare di scorrere tutte su di esse? In questo senso, darei un'occhiata alla classe sorteddict nel pacchetto blist. http://pypi.python.org/pypi/blist/

Answer 3

se si dispone di una data in qualche modo sovraccaricata che è possibile confrontare le cose con lo bisect module.

un intero minimo esempio di codifica:

from bisect import bisect_left 

data = { 
    200 : -100, 
    -50 : 0, 
    51 : 100, 
    250 : 200 
} 

keys = list(data.keys()) 

print data[ keys[ bisect_left(keys, -79) ] ] 

Answer 4

Quando voglio qualcosa che assomiglia ad una mappa C++, io uso SortedDict. È possibile utilizzare irange per ottenere un iteratore su una chiave per la quale una determinata chiave è un limite inferiore, il che credo sia il modo in cui funziona std::lower_bound.

codice:

from sortedcontainers import SortedDict 
sd = SortedDict() 
sd[105] = 'a' 
sd[102] = 'b' 
sd[101] = 'c' 

#SortedDict is sorted on insert, like std::map 
print(sd) 

# sd.irange(minimum=<key>) returns an iterator beginning with the first key not less than <key> 
print("min = 100", list(sd.irange(minimum=100))) 
print("min = 102", list(sd.irange(minimum=102))) 
print("min = 103", list(sd.irange(minimum=103))) 
print("min = 106", list(sd.irange(minimum=106))) 

uscita:

SortedDict(None, 1000, {101: 'c', 102: 'b', 105: 'a'}) 
min = 100 [101, 102, 105] 
min = 102 [102, 105] 
min = 103 [105] 
min = 106 []