python - Mapa bidireccional/inverso

subplot title python

Question

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

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

O sugerir otra estructura de datos.

No hay múltiples conversaciones Digamos que esto es para un centro de llamadas de atención al cliente, por lo que cuando Alice marca el conmutador, solo hablará con Bob. Sus respuestas también van solo a ella.

Answer 1

Aquí hay una implementación de diccionario bidireccional más ampliando la clase de dict pitones en caso de que no le hayan gustado ninguno de los 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)

Úselo como un diccionario python normal, excepto en construcción:

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

Answer 2

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

Answer 3

El módulo de extensión kjbuckets C proporciona una estructura de datos "gráfica" que, en mi opinión, le brinda lo que desea.

Answer 4

En su caso especial, puede almacenar ambos en un diccionario:

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

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

Answer 5

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

Answer 6

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

Usar la clase de biyección 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

Answer 7

Me gustaría llenar un segundo hash, con

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

Answer 8

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

Es mejor que cree un tipo personalizado que encapsula dos diccionarios y expone la funcionalidad que desea.

Answer 9

Otra solución posible es implementar una subclase de dict , que contenga el diccionario original y haga un seguimiento de una versión invertida de la misma. 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''}

Answer 10

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

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

Answer 11

Tienes dos problemas separados.

1. Usted tiene un objeto de "Conversación". Se refiere a dos personas. Como una Persona puede tener múltiples conversaciones, usted tiene 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.

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

Answer 12

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 "<stdin>", line 7, in <module>
KeyError: ''bar''

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