Mapa dwukierunkowa / odwrotna [duplikat]

Robię tę funkcję przełącznika w Pythonie, gdzie muszę śledzić, kto z kim rozmawia, więc jeśli Alice -> Bob, to oznacza, że ​​Bob -> Alice.

Tak, mógłbym wypełnić dwie mapy skrótów, ale zastanawiam się, czy ktoś ma pomysł, aby to zrobić z jedną.

Lub zasugeruj inną strukturę danych.

Nie ma wielu rozmów. Powiedzmy, że dotyczy to centrum obsługi klienta, więc kiedy Alicja wybierze numer z centrali, będzie rozmawiać tylko z Bobem. Jego odpowiedzi również trafiają tylko do niej.

Możesz utworzyć własny typ słownika, tworząc podklasy dicti dodając odpowiednią logikę. Oto podstawowy przykład:

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

I to działa tak:

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

Jestem pewien, że nie omówiłem wszystkich przypadków, ale to powinno zacząć.

W twoim szczególnym przypadku możesz przechowywać oba w jednym słowniku:

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

Ponieważ to, co opisujesz, jest relacją symetryczną. A -> B => B -> A

Wiem, że to starsze pytanie, ale chciałem wspomnieć o innym świetnym rozwiązaniu tego problemu, a mianowicie o pakiecie python bidict . Jest niezwykle prosty w użyciu:

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

Po prostu zapełniłbym drugi hash za pomocą

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

Dwie mapy skrótów są prawdopodobnie najszybszym rozwiązaniem przy założeniu, że można zaoszczędzić pamięć. Umieściłbym je w jednej klasie - obciążenie programisty polega na zapewnieniu prawidłowej synchronizacji dwóch map skrótów.

Masz dwa oddzielne problemy.

1. Masz obiekt „Rozmowa”. Odnosi się do dwóch osób. Ponieważ osoba może prowadzić wiele rozmów, istnieje relacja „wiele do wielu”.

2. Masz mapę od osoby do listy konwersacji. Nawrócenie będzie miało parę Osób.

Zrób coś takiego

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 )

Nie, naprawdę nie da się tego zrobić bez utworzenia dwóch słowników. Jak można by to zaimplementować za pomocą tylko jednego słownika, jednocześnie oferując porównywalną wydajność?

Lepiej jest utworzyć niestandardowy typ, który zawiera dwa słowniki i udostępnia żądaną funkcjonalność.

Mniej rozwlekły sposób, nadal używający odwrócenia:

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

Możesz być w stanie użyć, DoubleDictjak pokazano w przepisie 578224 w książce kucharskiej języka Python .

Innym możliwym rozwiązaniem jest zaimplementowanie podklasy dict, która przechowuje oryginalny słownik i śledzi jego odwróconą wersję. Przechowywanie dwóch oddzielnych poleceń może być przydatne, jeśli klucze i wartości nakładają się.

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. 

Przykład:

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

Na pypi znajduje się rozszerzona biblioteka kolekcji: https://pypi.python.org/pypi/collections-extended/0.6.0

Korzystanie z klasy bijection jest tak proste, jak:

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

Podoba mi się sugestia licytanta w jednym z komentarzy.

pip install bidict

Zastosowanie:

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

Ponieważ nie ma na ten temat wielu dokumentów. Ale wszystkie funkcje, których potrzebuję, działają poprawnie.

Wydruki:

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

Moduł rozszerzenia kjbuckets C zapewnia strukturę danych "grafową", która moim zdaniem daje ci to, czego chcesz.

Oto jeszcze jedna dwukierunkowa implementacja słownika poprzez rozszerzenie dictklasy Pythona na wypadek, gdybyś nie lubił żadnego z tych innych:

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)

Użyj go jako normalnego słownika Pythona, z wyjątkiem konstrukcji:

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

Sposób, w jaki lubię robić tego typu rzeczy, jest taki:

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