Mapa bidireccional / inverso [duplicado]

Estoy haciendo esta cosa de centralita 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 completar dos mapas hash, pero me pregunto si alguien tiene una idea para hacerlo con uno.

O sugiera otra estructura de datos.

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

Puede crear su propio tipo de diccionario subclasificando dicty agregando la lógica que desee. Aquí tienes 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 ayudarlo a comenzar.

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

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

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

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

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

Solo rellenaría un segundo hash, con

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

En realidad, dos mapas hash es probablemente la solución de rendimiento más rápido, suponiendo que pueda ahorrar memoria. Los envolvería en una sola clase: la carga del programador es asegurarse de que dos mapas hash se sincronicen correctamente.

Tienes dos problemas distintos.

1. Tienes un objeto "Conversación". Se refiere a dos personas. Dado que una persona puede tener varias conversaciones, tienes una relación de varios a varios.

2. Tiene 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 )

No, realmente no hay forma de hacer esto sin crear dos diccionarios. ¿Cómo sería posible implementar esto con un solo diccionario sin dejar de ofrecer un rendimiento comparable?

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

Una forma menos detallada, todavía usando invertida:

dict(map(reversed, my_dict.items()))

Es posible que pueda usar un DoubleDictcomo se muestra en la receta 578224 del Python Cookbook .

Otra posible solución es implementar una subclase de dict, que contiene el diccionario original y realiza un seguimiento de una versión inversa del mismo. Mantener dos dictados separados puede resultar ú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'}

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

Me gusta la sugerencia de bidict 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))    

Dado que no hay muchos documentos al respecto. Pero tengo todas las características que necesito para que funcionen correctamente.

Huellas dactilares:

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

El módulo de extensión kjbuckets C proporciona una estructura de datos de "gráfico" que creo que le da lo que desea.

Aquí hay una implementación más de diccionario bidireccional al extender la dictclase de pitones en caso de que no le guste 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 de Python normal, excepto en la construcción:

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

Una forma en la que me gusta hacer este tipo de cosas es algo como:

{my_dict[key]: key for key in my_dict.keys()}