¿Cómo implementar una tabla hash bidireccional eficiente?

Python dict es una estructura de datos muy útil:

 d = {'a': 1, 'b': 2} d['a'] # get 1 

A veces también te gustaría indexar por valores.

 d[1] # get 'a' 

¿Cuál es la forma más eficiente de implementar esta estructura de datos? ¿Alguna forma oficial recomendada de hacerlo?

Aquí hay una clase para un dict bidireccional, inspirada en la búsqueda de clave del valor en el diccionario de Python y modificada para permitir lo siguiente 2) y 3).

Tenga en cuenta que :

  • 1) El directorio inverso bd.inverse actualiza automáticamente cuando se modifica el dict bd estándar.
  • 2) El directorio inverso bd.inverse[value] es siempre una lista de key tal que bd[key] == value .
  • 3) A diferencia del módulo bidict de https://pypi.python.org/pypi/bidict , aquí podemos tener 2 claves que tienen el mismo valor, esto es muy importante .

Código:

 class bidict(dict): def __init__(self, *args, **kwargs): super(bidict, self).__init__(*args, **kwargs) self.inverse = {} for key, value in self.items(): self.inverse.setdefault(value,[]).append(key) def __setitem__(self, key, value): if key in self: self.inverse[self[key]].remove(key) super(bidict, self).__setitem__(key, value) self.inverse.setdefault(value,[]).append(key) def __delitem__(self, key): self.inverse.setdefault(self[key],[]).remove(key) if self[key] in self.inverse and not self.inverse[self[key]]: del self.inverse[self[key]] super(bidict, self).__delitem__(key) 

Ejemplo de uso:

 bd = bidict({'a': 1, 'b': 2}) print(bd) # {'a': 1, 'b': 2} print(bd.inverse) # {1: ['a'], 2: ['b']} bd['c'] = 1 # Now two keys have the same value (= 1) print(bd) # {'a': 1, 'c': 1, 'b': 2} print(bd.inverse) # {1: ['a', 'c'], 2: ['b']} del bd['c'] print(bd) # {'a': 1, 'b': 2} print(bd.inverse) # {1: ['a'], 2: ['b']} del bd['a'] print(bd) # {'b': 2} print(bd.inverse) # {2: ['b']} bd['b'] = 3 print(bd) # {'b': 3} print(bd.inverse) # {2: [], 3: ['b']} 

Puede usar el mismo dictado agregando clave, par de valores en orden inverso.

 d = {'a': 1, 'b': 2}
 revd = dict ([invertido (i) para i en d.items ()])
 d.update (revd)

La tabla hash bidireccional de un hombre pobre sería usar solo dos diccionarios (estas son estructuras de datos altamente afinadas ya).

También hay un paquete bidict en el índice:

La fuente de Bidict se puede encontrar en github:

El siguiente fragmento de código implementa un mapa invertible (biyectivo):

 class BijectionError(Exception): """Must set a unique value in a BijectiveMap.""" def __init__(self, value): self.value = value msg = 'The value "{}" is already in the mapping.' super().__init__(msg.format(value)) class BijectiveMap(dict): """Invertible map.""" def __init__(self, inverse=None): if inverse is None: inverse = self.__class__(inverse=self) self.inverse = inverse def __setitem__(self, key, value): if value in self.inverse: raise BijectionError(value) self.inverse._set_item(value, key) self._set_item(key, value) def __delitem__(self, key): self.inverse._del_item(self[key]) self._del_item(key) def _del_item(self, key): super().__delitem__(key) def _set_item(self, key, value): super().__setitem__(key, value) 

La ventaja de esta implementación es que el atributo inverse de un BijectiveMap es nuevamente un BijectiveMap . Por lo tanto puedes hacer cosas como:

 >>> foo = BijectiveMap() >>> foo['steve'] = 42 >>> foo.inverse {42: 'steve'} >>> foo.inverse.inverse {'steve': 42} >>> foo.inverse.inverse is foo True 

Algo como esto, tal vez:

 import itertools class BidirDict(dict): def __init__(self, iterable=(), **kwargs): self.update(iterable, **kwargs) def update(self, iterable=(), **kwargs): if hasattr(iterable, 'iteritems'): iterable = iterable.iteritems() for (key, value) in itertools.chain(iterable, kwargs.iteritems()): self[key] = value def __setitem__(self, key, value): if key in self: del self[key] if value in self: del self[value] dict.__setitem__(self, key, value) dict.__setitem__(self, value, key) def __delitem__(self, key): value = self[key] dict.__delitem__(self, key) dict.__delitem__(self, value) def __repr__(self): return '%s(%s)' % (type(self).__name__, dict.__repr__(self)) 

Debe decidir qué desea que suceda si más de una clave tiene un valor determinado; la bidireccionalidad de un par dado podría ser fácilmente superada por algún par posterior insertado. Implementé una opción posible.


Ejemplo:

 bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'}) print bd['myvalue1'] # a print bd['myvalue2'] # b 

Primero, debe asegurarse de que la clave para el mapeo de valor sea uno a uno, de lo contrario, no es posible construir un mapa bidireccional.

Segundo, ¿qué tan grande es el conjunto de datos? Si no hay mucha información, solo use 2 mapas separados y actualícelos al actualizar. O mejor aún, use una solución existente como Bidict , que es solo un envoltorio de 2 dicts, con actualización / eliminación incorporada.

Pero si el conjunto de datos es grande, y mantener 2 dicts no es deseable:

  • Si tanto la clave como el valor son numéricos, considere la posibilidad de usar Interpolación para aproximar la asignación. Si la gran mayoría de los pares clave-valor pueden ser cubiertos por la función de mapeo (y su
    función inversa), solo necesita registrar los valores atípicos en los mapas.

  • Si la mayoría del acceso es unidireccional (clave-> valor), entonces es totalmente aceptable construir el mapa inverso de manera incremental, para cambiar el tiempo por
    espacio.

Código:

 d = {1: "one", 2: "two" } reverse = {} def get_key_by_value(v): if v not in reverse: for _k, _v in d.items(): if _v == v: reverse[_v] = _k break return reverse[v]