Двусторонняя / обратная карта

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

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

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

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

12 71
python

12 ответов:

вы можете создать свой собственный словарь на подклассы 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'

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

73

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

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

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

35

Я бы просто заполнил второй хэш, с

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

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

6

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

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

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

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

4

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

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

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

1

другим возможным решением является реализация подкласса 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'}
1

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

0

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

использование класса биекции так же просто, как:

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
0

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

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