Two way/reverse map

我在 Python 中做了一个交换机的工作，我需要记录谁在和谁说话，所以如果 Alice —— > Bob，那就意味着 Bob —— > Alice。

是的，我可以填充两个散列映射，但我想知道是否有人有一个想法来做它。

或者建议使用其他数据结构。

没有多重对话。假设这是一个客户服务呼叫中心，所以当爱丽丝拨打总机时，她只会和鲍勃通话。他的答复也只有她一个人。

67209 次浏览
小开

不，如果不创建两个字典，就没有办法做到这一点。如何才能实现这一点，只有一个字典，同时继续提供类似的性能？

您最好创建一个自定义类型，该类型封装两个字典并公开所需的功能。

小开

假设可以节省内存，两个散列映射实际上可能是性能最快的解决方案。我会将它们封装在一个类中——程序员的负担是确保两个散列映射正确同步。

小开

我只需要填充第二个 hash

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

In your special case you can store both in one dictionary:

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

因为你所描述的是一种对称关系

小开

你有两个不同的问题。

  1. 你有一个“对话”对象。它指的是两个人。因为 Person 可以有多个会话，所以您有一个多对多的关系。

  2. 您有一个从 Person 到一个对话列表的 Map。

Do something like this

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 )
小开

Kjbucket C 扩展模块提供了一个“图形”数据结构，我相信它可以满足您的需要。

小开
最佳答案

您可以通过子类化 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

And it works like so:

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

我确定我没有涵盖所有的案子，但这应该能让你开始。

小开

您可能能够使用 DoubleDict，如在 Python 烹饪书上的 食谱578224所示。

小开

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

There's the collections-extended library on 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
小开

我知道这是一个比较老的问题，但是我想提到另一个解决这个问题的很好的解决方案，即 Python 包 比迪克特。它使用起来非常直接:

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

下面是另一个双向字典实现，它通过扩展 python 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)

Use it as a normal python dictionary except in construction:

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

我喜欢其中一条评论中的比迪克特建议。

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

Since there aren't much docs about it. But I've got all the features I need from it working correctly.

印刷品:

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

一种不那么冗长的方式，仍然使用反向:

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

A way I like to do this kind of thing is something like:

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

提交答案