Mapa bidirecional / reverso [duplicado]

Estou fazendo essa coisa de mesa telefônica em python em que preciso manter o controle de quem está falando com quem, então se Alice -> Bob, isso implica que Bob -> Alice.

Sim, eu poderia preencher dois mapas hash, mas estou me perguntando se alguém tem uma ideia de fazer isso com um.

Ou sugira outra estrutura de dados.

Não existem várias conversas. Digamos que isso seja para um call center de atendimento ao cliente, então, quando Alice discar para a mesa telefônica, ela falará apenas com Bob. Suas respostas também vão apenas para ela.

Você pode criar seu próprio tipo de dicionário criando uma subclasse dicte adicionando a lógica que deseja. Aqui está um exemplo 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

E funciona assim:

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

Tenho certeza de que não cobri todos os casos, mas isso deve ajudar você a começar.

No seu caso especial, você pode armazenar ambos em um dicionário:

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

Já que o que você está descrevendo é uma relação simétrica. A -> B => B -> A

Eu sei que é uma pergunta mais antiga, mas gostaria de mencionar outra ótima solução para esse problema, ou seja, o bidict do pacote python . É extremamente simples de usar:

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

Eu apenas preencheria um segundo hash, com

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

Dois mapas de hash são provavelmente a solução de desempenho mais rápido, supondo que você possa poupar memória. Eu os envolveria em uma única classe - a responsabilidade do programador é garantir que dois mapas de hash sejam sincronizados corretamente.

Você tem dois problemas separados.

1. Você tem um objeto "Conversa". Refere-se a duas Pessoas. Como uma pessoa pode ter várias conversas, você tem um relacionamento de muitos para muitos.

2. Você tem um mapa de pessoa para uma lista de conversas. Uma conversão terá um par de pessoas.

Faça algo assim

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 )

Não, realmente não há como fazer isso sem criar dois dicionários. Como seria possível implementar isso com apenas um dicionário e, ao mesmo tempo, oferecer desempenho comparável?

É melhor criar um tipo personalizado que encapsule dois dicionários e exponha a funcionalidade desejada.

Uma forma menos prolixa, ainda usando o reverso:

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

Você pode usar um DoubleDictconforme mostrado na receita 578224 do Python Cookbook .

Outra solução possível é implementar uma subclasse de dict, que contém o dicionário original e mantém o controle de uma versão reversa dele. Manter dois dictes separados pode ser útil se as chaves e os valores estiverem sobrepostos.

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. 

Exemplo:

>>> 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 a biblioteca de coleções estendidas em pypi: https://pypi.python.org/pypi/collections-extended/0.6.0

Usar a classe bijection é tão fácil quanto:

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

Gostei da sugestão do bidict em um dos comentários.

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

Já que não há muitos documentos sobre isso. Mas tenho todos os recursos de que preciso funcionando corretamente.

Impressões:

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

O módulo de extensão kjbuckets C fornece uma estrutura de dados em "gráfico" que acredito dar a você o que você deseja.

Aqui está mais uma implementação de dicionário bidirecional, estendendo a dictclasse pythons , caso você não goste de nenhuma das outras:

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)

Use-o como um dicionário python normal, exceto na construção:

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

Uma maneira que gosto de fazer esse tipo de coisa é algo como:

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