Mapa bidireccional / inverso

Estoy haciendo esto en Python, donde necesito hacer un seguimiento de quién está hablando con quién, así que si Alice -> Bob, eso implica que Bob -> Alice.

Sí, podría poblar dos mapas hash, pero me pregunto si alguien tiene una idea para hacerlo con uno.

O sugerir otra estructura de datos.

No hay conversaciones múltiples. Digamos que esto es para un centro de llamadas de servicio al cliente, de modo que cuando Alicia marca en la centralita, solo hablará con Bob. Sus respuestas también van solo a ella.

Puede crear su propio tipo de diccionario subclasificando dict y agregando la lógica que desee. Aquí hay un ejemplo básico:

 class TwoWayDict(dict): def __setitem__(self, key, value): # Remove any previous connections with these values 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): dict.__delitem__(self, self[key]) dict.__delitem__(self, key) def __len__(self): """Returns the number of connections""" return dict.__len__(self) // 2 

Y funciona así:

 >>> d = TwoWayDict() >>> d['foo'] = 'bar' >>> d['foo'] 'bar' >>> d['bar'] 'foo' >>> len(d) 1 >>> del d['foo'] >>> d['bar'] Traceback (most recent call last): File "", line 7, in  KeyError: 'bar' 

Estoy seguro de que no cubrí todos los casos, pero eso debería comenzar.

En su caso especial puede almacenar ambos en un diccionario:

 relation = {} relation['Alice'] = 'Bob' relation['Bob'] = 'Alice' 

Ya que lo que estás describiendo es una relación simétrica. A -> B => B -> A

Simplemente rellenaría un segundo hash, con

 reverse_map = dict((reversed(item) for item in forward_map.items())) 

Sé que es una pregunta antigua, pero quería mencionar otra gran solución a este problema, a saber, el paquete de python bidict . Es extremadamente sencillo de usar:

 from bidict import bidict map = bidict(Bob = "Alice") print(map["Bob"]) print(map.inv["Alice"]) 

Dos mapas hash es en realidad la solución de más rápido rendimiento, suponiendo que puede ahorrar la memoria. Los envolvería en una sola clase: la carga para el progtwigdor es garantizar que dos de los mapas hash se sincronicen correctamente.

Tienes dos problemas separados.

  1. Tienes un objeto de “Conversación”. Se refiere a dos personas. Como una persona puede tener múltiples conversaciones, tienes una relación de muchos a muchos.

  2. Tienes un Mapa de Persona a una lista de Conversaciones. Una conversión tendrá un par de personas.

Hacer algo como esto

 from collections import defaultdict switchboard= defaultdict( list ) x = Conversation( "Alice", "Bob" ) y = Conversation( "Alice", "Charlie" ) for c in ( x, y ): switchboard[c.p1].append( c ) switchboard[c.p2].append( c ) 

No, realmente no hay manera de hacer esto sin crear dos diccionarios. ¿Cómo sería posible implementar esto con un solo diccionario mientras continúa ofreciendo un rendimiento comparable?

Es mejor crear un tipo personalizado que encapsule dos diccionarios y exponga la funcionalidad que desea.

Es posible que pueda usar un DoubleDict como se muestra en la receta 578224 en el Libro de cocina de Python .

Otra solución posible es implementar una subclase de dict , que contiene el diccionario original y realiza un seguimiento de una versión invertida del mismo. Mantener dos dicts separados puede ser útil si las claves y los valores se superponen.

 class TwoWayDict(dict): def __init__(self, my_dict): dict.__init__(self, my_dict) self.rev_dict = {v : k for k,v in my_dict.iteritems()} def __setitem__(self, key, value): dict.__setitem__(self, key, value) self.rev_dict.__setitem__(value, key) def pop(self, key): self.rev_dict.pop(self[key]) dict.pop(self, key) # The above is just an idea other methods # should also be overridden. 

Ejemplo:

 >>> d = {'a' : 1, 'b' : 2} # suppose we need to use d and its reversed version >>> twd = TwoWayDict(d) # create a two-way dict >>> twd {'a': 1, 'b': 2} >>> twd.rev_dict {1: 'a', 2: 'b'} >>> twd['a'] 1 >>> twd.rev_dict[2] 'b' >>> twd['c'] = 3 # we add to twd and reversed version also changes >>> twd {'a': 1, 'c': 3, 'b': 2} >>> twd.rev_dict {1: 'a', 2: 'b', 3: 'c'} >>> twd.pop('a') # we pop elements from twd and reversed version changes >>> twd {'c': 3, 'b': 2} >>> twd.rev_dict {2: 'b', 3: 'c'} 

El módulo de extensión kjbuckets C proporciona una estructura de datos “gráfica” que creo que le proporciona lo que desea.

Hay la biblioteca de colecciones extendidas en pypi: https://pypi.python.org/pypi/collections-extended/0.6.0

Usar la clase bijection es tan fácil como:

 RESPONSE_TYPES = bijection({ 0x03 : 'module_info', 0x09 : 'network_status_response', 0x10 : 'trust_center_device_update' }) >>> RESPONSE_TYPES[0x03] 'module_info' >>> RESPONSE_TYPES.inverse['network_status_response'] 0x09 

Aquí hay una implementación de diccionario bidireccional más extendiendo la clase dict pythons en caso de que no te haya gustado ninguno de esos otros:

 class DoubleD(dict): """ Access and delete dictionary elements by key or value. """ def __getitem__(self, key): if key not in self: inv_dict = {v:k for k,v in self.items()} return inv_dict[key] return dict.__getitem__(self, key) def __delitem__(self, key): if key not in self: inv_dict = {v:k for k,v in self.items()} dict.__delitem__(self, inv_dict[key]) else: dict.__delitem__(self, key) 

Úsalo como un diccionario de python normal, excepto en la construcción:

 dd = DoubleD() dd['foo'] = 'bar' 

Me gusta la sugerencia de licitante en uno de los comentarios.

pip install bidict

Uso:

 # This normalization method should save hugely as aDaD ~ yXyX have the same form of smallest grammar. # To get back to your grammar's alphabet use trans def normalize_string(s, nv=None): if nv is None: nv = ord('a') trans = bidict() r = '' for c in s: if c not in trans.inverse: a = chr(nv) nv += 1 trans[a] = c else: a = trans.inverse[c] r += a return r, trans def translate_string(s, trans): res = '' for c in s: res += trans[c] return res if __name__ == "__main__": s = "bnhnbiodfjos" n, tr = normalize_string(s) print(n) print(tr) print(translate_string(n, tr)) 

Ya que no hay mucha documentación al respecto. Pero tengo todas las características que necesito para que funcione correctamente.

Huellas dactilares:

 abcbadefghei bidict({'a': 'b', 'b': 'n', 'c': 'h', 'd': 'i', 'e': 'o', 'f': 'd', 'g': 'f', 'h': 'j', 'i': 's'}) bnhnbiodfjos