Python dictionary – binario busca una clave?

Quiero escribir una clase contenedora que actúe como un diccionario (en realidad se deriva de un dictado). Las claves de esta estructura serán las fechas.

Cuando se usa una clave (es decir, la fecha) para recuperar un valor de la clase, si la fecha no existe, la siguiente fecha disponible que precede a la clave se usa para devolver el valor.

Los siguientes datos deberían ayudar a explicar el concepto aún más:

Date (key) Value 2001/01/01 123 2001/01/02 42 2001/01/03 100 2001/01/04 314 2001/01/07 312 2001/01/09 321 

Si bash obtener el valor asociado con la clave (fecha) ‘2001/01/05’ debería obtener el valor almacenado bajo la clave 2001/01/04, ya que esa clave aparece antes de la clave ‘2001/01/05’ Se si existiera en el diccionario.

Para hacer esto, necesito poder hacer una búsqueda (idealmente binario, en lugar de hacer un bucle ingenuo a través de cada clave en el diccionario). He buscado bsearch dictionary key searchups en los diccionarios de Python, pero no he encontrado nada útil.

De todos modos, quiero escribir una clase como esa que encapsula este comportamiento.

Esto es lo que tengo hasta ahora (no mucho):

 # class NearestNeighborDict(dict): # """ # a dictionary which returns value of nearest neighbor if specified key not found # """ def __init__(self, items={}): dict.__init__(self, items) def get_item(self, key): # returns the item stored with the key (if key exists) # else it returns the item stored with the key 

Realmente no desea dict subclase de dict porque realmente no puede reutilizar ninguna de sus funciones. En su lugar, subclase las collections.Mapping clase base abstracta. El MutableMapping (o MutableMapping si también quiere poder modificar una instancia después de la creación), implemente los métodos especiales indispensables para el propósito, y obtendrá otros métodos similares a dict “de forma gratuita “de la ABC.

Los métodos que necesita para codificar son __getitem__ (y __setitem__ y __delitem__ si desea la mutabilidad), __len__ , __iter__ y __contains__ .

El módulo bisect de la biblioteca estándar le brinda todo lo que necesita para implementar estos de manera eficiente en la parte superior de una lista ordenada. Por ejemplo…:

 import collections import bisect class MyDict(collections.Mapping): def __init__(self, contents): "contents must be a sequence of key/value pairs" self._list = sorted(contents) def __iter__(self): return (k for (k, _) in self._list) def __contains__(self, k): i = bisect.bisect_left(self._list, (k, None)) return i < len(self._list) and self._list[i][0] == k def __len__(self): return len(self._list) def __getitem__(self, k): i = bisect.bisect_left(self._list, (k, None)) if i >= len(self._list): raise KeyError(k) return self._list[i][1] 

Probablemente querrá tocar el __getitem__ dependiendo de lo que quiera devolver (o si quiere subir) para varios casos de esquina como ” k mayor que todas las claves en self “.

El módulo sortedcontainers proporciona un tipo SortedDict que mantiene las claves en orden ordenado y admite la división en esas claves. El módulo es implementaciones de Python puro y rápido como C con 100% de cobertura de prueba y horas de estrés.

Por ejemplo:

 from sortedcontainers import SortedDict sd = SortedDict((date, value) for date, value in data) # Bisect for the index of the desired key. index = sd.bisect('2001/01/05') # Lookup the real key at that index. key = sd.iloc[index] # Retrieve the value associated with that key. value = sd[key] 

Debido a que SortedDict admite la indexación rápida, también es fácil mirar hacia adelante o hacia atrás de su clave. SortedDict también es un MutableMapping, por lo que debería funcionar bien en su sistema de tipos.

Extendería un dict , y anularía el método __getitem__ y __setitem__ para almacenar una lista ordenada de claves.

 from bisect import bisect class NearestNeighborDict(dict): def __init__(self): dict.__init__(self) self._keylist = [] def __getitem__(self, x): if x in self: return dict.__getitem__(self, x) index = bisect(self._keylist, x) if index == len(self._keylist): raise KeyError('No next date') return dict.__getitem__(self, self._keylist[index]) def __setitem__(self, x, value): if x not in self: index = bisect(self._keylist, x) self._keylist.insert(index, value) dict.__setitem__(self, x, value) 

Es cierto que es mejor heredar de MutableMapping , pero el principio es el mismo, y el código anterior se puede adaptar fácilmente.

¿Por qué no simplemente mantener una lista ordenada de dict.keys () y buscar eso? Si está creando una subclase de dictado, puede incluso idear una oportunidad para realizar una inserción binaria en esa lista cuando se agreguen valores.

Utilice el método floor_key en bintrees.RBTree: https://pypi.python.org/pypi/bintrees/2.0.1