Двухсторонняя / обратная карта
Я делаю это переключение в Python, где мне нужно отслеживать, кто с кем разговаривает, так что если Алиса -> Боб, то это подразумевает, что Боб -> Алиса.
Да, я мог бы заполнить две хеш-карты, но мне интересно, есть ли у кого-нибудь идея сделать это с одной.
Или предложить другую структуру данных.
Там нет многократных разговоров. Допустим, это для колл-центра обслуживания клиентов, поэтому, когда Алиса набирает номер на коммутаторе, она только собирается поговорить с Бобом. Его ответы также относятся только к ней.
13 ответов
Вы можете создать свой собственный тип словаря путем создания подклассов 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
Я бы просто заполнил второй хеш, с
reverse_map = dict((reversed(item) for item in forward_map.items()))
Две хеш-карты - это, вероятно, самое быстрое решение, при условии, что вы можете сэкономить память. Я бы обернул их в один класс - бремя для программиста заключается в обеспечении правильной синхронизации двух хэш-карт.
Менее подробный способ, по-прежнему использующий обратный:
dict(map(reversed, my_dict.items()))
У вас есть две отдельные проблемы.
У вас есть объект "Разговор". Это относится к двум лицам. Поскольку у человека может быть несколько разговоров, у вас есть отношения многие ко многим.
У вас есть карта от человека до списка разговоров. Конверсия будет иметь пару человек.
Сделать что-то подобное
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 )
Нет, на самом деле нет способа сделать это без создания двух словарей. Как можно было бы реализовать это с помощью всего одного словаря, продолжая предлагать сопоставимую производительность?
Вам лучше создать пользовательский тип, который инкапсулирует два словаря и предоставляет желаемую функциональность.
Вы можете использовать DoubleDict как показано в рецепте 578224 в кулинарной книге Python.
Мне нравится предложение о бидике в одном из комментариев.
pip install bidict
Useage:
# 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
Другим возможным решением является реализация подкласса 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
Вот еще одна двусторонняя реализация словаря, расширяющая питонов 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'
Модуль расширения kjbuckets C предоставляет "графическую" структуру данных, которая, я считаю, дает вам то, что вы хотите.
Мне нравится делать такие вещи примерно так:
{my_dict[key]: key for key in my_dict.keys()}