Tabla hash bidireccional eficiente en Python?

Question

Python dict es una estructura de datos muy útiles:

d = {'a': 1, 'b': 2} 

d['a'] # get 1 

veces También desea que el índice de valores.

d[1] # get 'a' 

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

Gracias!

Answer 1

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

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

• https://pypi.python.org/pypi/bidict

La fuente de bidict se puede encontrar en GitHub:

• https://github.com/jab/bidict

Answer 2

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

Usted tiene que decidir lo que desea que suceda si más de una clave tiene un valor determinado; la bidireccionalidad de un par determinado podría ser golpeada fácilmente por algún par posterior que hayas insertado. Implementé una posible elección.

---

Ejemplo:

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

Answer 3

Usted puede utilizar el mismo en sí dict mediante la adición de clave, par de valores en orden inverso.

 
d={'a':1,'b':2} 
revd=dict([reversed(i) for i in d.items()]) 
d.update(revd) 

Answer 4

Aquí es una clase para un bidireccional dict, inspirado por Finding key from value in Python dictionary y modificado para permitir la siguiente 2) y 3).

Tenga en cuenta que:

• 1) El directorio inversabd.inverse actualizaciones automáticas a sí mismo cuando el dict estándar bd se modifica
• 2) El directorio inversabd.inverse[value] es siempre una lista de key tal que bd[key] == value
• 3) A diferencia del módulo bidict desde https://pypi.python.org/pypi/bidict, aquí podemos tener 2 claves con 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.iteritems(): 
      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']} 

Answer 5

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

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 BijectiveMap es nuevamente un BijectiveMap. Por lo tanto usted puede hacer cosas como:

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

Answer 6

En primer lugar, usted tiene que asegurarse de que la clave para la asignación de valores es uno a uno, de lo contrario, no es posible construir un mapa bidireccional.

En segundo lugar, ¿qué tan grande es el conjunto de datos? Si no hay mucha información, simplemente use 2 mapas separados y actualícelos al actualizar. O mejor, usar una solución existente como Bidict, que es sólo un envoltorio de 2 predice, con actualización/eliminación construida en

Pero si el conjunto de datos es grande, y el mantenimiento de 2 predice no es deseable:.

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

• Si la mayoría de acceso es unidireccional (número-> valor), entonces es totalmente bien para construir el mapa inversa de forma incremental, con el comercio de tiempo para
  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]