双向/反向映射

Question

我在python中做这个交换机的事情，我需要跟踪谁在跟谁说话，所以如果Alice - > Bob，那么这意味着Bob - > Alice。

是的，我可以填充两个哈希映射，但我想知道是否有人有一个想法做一个。

或者建议另一个数据结构。

没有多个对话。假设这是针对客户服务呼叫中心的，所以当Alice拨入交换台时，她只会和Bob通话。他的答复也仅限于她。

Answer 1

您可以通过继承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' 

我敢肯定，我没有涵盖所有的情况，但应该让你开始。

Answer 2

不，如果不创建两个字典，实在没有办法做到这一点。如何用一本词典实现这一点，同时继续提供可比较的性能？

你最好创建一个封装两个字典并展示你想要的功能的自定义类型。

Answer 3

假设您可以节省内存，两个哈希映射实际上可能是性能最快的解决方案。我会将这些包装在一个类中 - 程序员的负担是确保两个哈希映射正确同步。

Answer 4

我只想填充第二散列，与

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

Answer 5

在你的特殊情况下，你可以同时存储在一个字典：

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

因为你所描述的对称关系。 A -> B => B -> A

Answer 6

你有两个单独的问题。

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) 

Answer 7

的kjbuckets C扩展模块提供了一个“图”的数据结构，我相信给你你想要的东西。

Answer 8

您可以使用DoubleDict，如Python Cookbook上的recipe 578224所示。

Answer 9

另一种可能的解决方案是实现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'} 

Answer 10

有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 

Answer 11

我知道这是一个老问题，但我想提出另一个很好的解决方案，即python包bidict。这是非常直接的使用：

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