Двусторонняя / обратная карта [дубликат]

Я делаю этот коммутатор на Python, где мне нужно отслеживать, кто с кем разговаривает, поэтому, если Алиса -> Боб, то это означает, что Боб -> Алиса.

Да, я мог бы заполнить две хеш-карты, но мне интересно, есть ли у кого-нибудь идея сделать это с одной.

Или предложите другую структуру данных.

Нет нескольких разговоров. Допустим, это для центра обслуживания клиентов, поэтому, когда Алиса набирает номер на коммутаторе, она будет говорить только с Бобом. Его ответы тоже идут только ей.

Вы можете создать свой собственный тип словаря, создав подклассы dictи добавив нужную логику. Вот простой пример:

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

А работает это так:

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

Я уверен, что не рассмотрел все случаи, но это должно помочь вам начать.

В вашем особом случае вы можете хранить оба в одном словаре:

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

Поскольку то, что вы описываете, является симметричным отношением. A -> B => B -> A

Я знаю, что это более старый вопрос, но я хотел бы упомянуть еще одно отличное решение этой проблемы, а именно двунаправленный пакет python . Очень просто использовать:

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

Я бы просто заполнил второй хеш с помощью

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

Две хэш-карты - это, вероятно, самое быстрое решение, если вы можете сэкономить память. Я бы обернул их в один класс - задача программиста состоит в том, чтобы обеспечить правильную синхронизацию двух хэш-карт.

У вас есть две разные проблемы.

1. У вас есть объект «Разговор». Это относится к двум лицам. Поскольку человек может вести несколько разговоров, у вас есть отношения «многие ко многим».

2. У вас есть карта от человека к списку разговоров. Конверсия будет иметь пару Лиц.

Сделай что-нибудь вроде этого

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 )

Нет, без создания двух словарей это сделать невозможно. Как можно было бы реализовать это с помощью всего одного словаря, сохраняя при этом сопоставимую производительность?

Лучше создать собственный тип, который инкапсулирует два словаря и предоставляет желаемую функциональность.

Менее подробный способ с использованием обратного:

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

Вы можете использовать a, DoubleDictкак показано в рецепте 578224 в Python Cookbook .

Другое возможное решение - реализовать подкласс dict, который содержит исходный словарь и отслеживает его обратную версию. Хранение двух отдельных диктовок может быть полезно, если ключи и значения перекрываются.

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. 

Пример:

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

На pypi есть расширенная библиотека коллекций: https://pypi.python.org/pypi/collections-extended/0.6.0

Использовать класс bijection так же просто, как:

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

Мне нравится предложение бидикта в одном из комментариев.

pip install bidict

Использование:

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

Поскольку об этом не так много документов. Но у меня есть все необходимые мне функции, которые работают правильно.

Печать:

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

Модуль расширения kjbuckets C предоставляет «графическую» структуру данных, которая, как мне кажется, дает вам то, что вы хотите.

Вот еще одна реализация двустороннего словаря путем расширения dictкласса pythons на случай, если вам не понравился какой-либо из них:

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)

Используйте его как обычный словарь Python, за исключением конструкции:

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

Мне нравится делать такие вещи примерно так:

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