Python dictionary - binary search for a key?

Question

Quiero escribir una clase de contenedor que actúa como un diccionario (en realidad se deriva de un dict), Las claves para esta estructura serán las fechas.

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

Los siguientes datos deben ayudar a explicar el concepto más lejos:

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 trato de buscar el valor asociado con la clave (fecha) '01/05/2001' que debería obtener el valor almacenado en la clave 2001/01/04 ya que esa clave ocurre antes donde la clave '2001/01/05' sería si existiera en el diccionario.

Para hacer esto, necesito poder hacer una búsqueda (idealmente binaria, en lugar de ingenuamente recorrer cada tecla en el diccionario). He buscado las búsquedas de claves del diccionario bsearch 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 

Answer 1

Usted realmente no quiere subclase dict porque realmente no se puede volver a utilizar cualquiera de su funcionalidad. Más bien, subclasifique la clase base abstracta collections.Mapping (o MutableMapping si también desea poder modificar una instancia después de la creación), implemente los métodos especiales indispensables para tal fin y obtendrá otros métodos similares a dict "de forma gratuita" de el ABC.

Los métodos que necesita código son __getitem__ (y __setitem__ y __delitem__ si quieres mutabilidad), __len__, __iter__ y __contains__.

El módulo bisect de la biblioteca estándar le ofrece 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] 

usted probablemente querrá que violín __getitem__ dependiendo de lo que desea devolver (o si desea aumentar) para diversos casos de esquina como "k mayor que todas las llaves en self ".

Answer 2

Ampliaría 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 que hereda de MutableMapping, pero el principio es el mismo, y el código anterior se puede adaptar fácilmente.

Answer 3

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

Answer 4

El módulo sortedcontainers proporciona un tipo SortedDict que mantiene las claves en orden ordenado y admite la bisección en esas teclas.El módulo es puro-Python y fast-as-C implementations 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 SortedDict soporta la indexación rápida, es fácil mirar hacia delante o detrás de su clave. SortedDict también es MutableMapping, por lo que debería funcionar muy bien en su sistema de tipos.

Answer 5

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