map :: lower_bound() equivalente para la clase dict de python?

Question

Estoy escribiendo un código que me obliga a buscar el límite inferior de una clave (por simplicidad, ignore las claves que se encuentran debajo de la clave más pequeña en la colección).

En C++, usando std :: map (como el tipo de datos más comparable), simplemente usaría low_bound() para devolver el iterador.

Mi Pythonfoo no es tan grande, pero estoy adivinando que (en el caso de Python no tiene ya una forma de hacer esto), esto sería un buen uso de una función lambda ...

¿Cuál es la forma Pythonic de recuperar la clave de límite inferior para un índice dado?

En caso de que la pregunta es demasiado abstracto, esto es lo que en realidad estoy tratando de hacer:

que tienen un diccionario de Python indexado por día. Quiero poder utilizar una fecha para buscar el dict y devolver el valor asociado con el límite inferior de la clave especificada.

Fragmento de la siguiente manera:

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 

que realmente no quieren colocar a través de las teclas, en busca de la primera clave < = proporcionada clave, a menos que no hay mejor alternativa ...

Answer 1

Aún no estoy seguro de cuál es el "límite inferior": ¿la última fecha antes/después de la fecha de consulta?

De todos modos, dado que un dict no impone un orden inherente en sus claves, necesita una estructura diferente. Almacene sus llaves en una estructura que las mantenga ordenadas y permita búsquedas rápidas.

La solución más simple sería simplemente almacenar las fechas ordenadas en una lista de (fecha, valor), y hacer una búsqueda binaria para acercar la región que desee. Si necesita/desea un mejor rendimiento, creo que un b-tree es lo que necesita.

Answer 2

La clase dict de Python no tiene esta funcionalidad; necesitarías escribirlo tú mismo. Seguramente sería conveniente si las claves ya estaban ordenadas, ¿no es así, por lo que podría hacer una búsqueda binaria en ellas y evitar iterar sobre todas ellas? En este sentido, echaré un vistazo a la clase sorteddict en el paquete blist. http://pypi.python.org/pypi/blist/

Answer 3

si tiene alguna fecha sobrecargada que pueda comparar cosas que se vean en el bisect module.

un entero mínimo ejemplo de codificación:

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

Cuando quiero algo que se asemeja a un mapa C++, utilizo SortedDict. Puede usar irange para obtener un iterador a una clave para la cual una tecla dada es un límite inferior, que creo que es como funciona std::lower_bound.

código:

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

de salida:

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