两路/反向映射[重复]

问题:两路/反向映射[重复]

我在python中做这个总机,需要跟踪谁在和谁说话,所以如果Alice-> Bob,那意味着Bob-> Alice。

是的,我可以填充两个哈希图,但是我想知道是否有人想使用一个哈希图。

或建议其他数据结构。

没有多个对话。假设这是一个客户服务呼叫中心,所以当爱丽丝拨入总机时,她只会和鲍勃交谈。他的答复也只发给她。

I’m doing this switchboard thing in python where I need to keep track of who’s talking to whom, so if Alice –> Bob, then that implies that Bob –> Alice.

Yes, I could populate two hash maps, but I’m wondering if anyone has an idea to do it with one.

Or suggest another data structure.

There are no multiple conversations. Let’s say this is for a customer service call center, so when Alice dials into the switchboard, she’s only going to talk to Bob. His replies also go only to her.


回答 0

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

我确定我没有涵盖所有情况,但这应该可以帮助您入门。

You can create your own dictionary type by subclassing dict and adding the logic that you want. Here’s a basic example:

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'

I’m sure I didn’t cover all the cases, but that should get you started.


回答 1

在特殊情况下,您可以将两者存储在一个字典中:

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

由于您要描述的是对称关系。 A -> B => B -> A

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

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

Since what you are describing is a symmetric relationship. A -> B => B -> A


回答 2

我知道这是一个比较老的问题,但是我想提到另一个解决此问题的好方法,即python软件包bidict。使用起来非常简单:

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

I know it’s an older question, but I wanted to mention another great solution to this problem, namely the python package bidict. It’s extremely straight forward to use:

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

回答 3

我只是用第二个哈希填充

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

I would just populate a second hash, with

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

回答 4

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

Two hash maps is actually probably the fastest-performing solution assuming you can spare the memory. I would wrap those in a single class – the burden on the programmer is in ensuring that two the hash maps sync up correctly.


回答 5

您有两个单独的问题。

  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 )

You have two separate issues.

  1. You have a “Conversation” object. It refers to two Persons. Since a Person can have multiple conversations, you have a many-to-many relationship.

  2. You have a Map from Person to a list of Conversations. A Conversion will have a pair of Persons.

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 )

回答 6

不,没有创建两个词典,实际上是没有办法做到的。在继续提供可比性能的同时,如何仅用一个字典就能实现呢?

最好创建一个自定义类型来封装两个字典,并提供所需的功能。

No, there is really no way to do this without creating two dictionaries. How would it be possible to implement this with just one dictionary while continuing to offer comparable performance?

You are better off creating a custom type that encapsulates two dictionaries and exposes the functionality you want.


回答 7

较不冗长的方式,仍然使用反转:

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

A less verbose way, still using reversed:

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

回答 8

您可以使用一个DoubleDict如图配方578224Python的食谱

You may be able to use a DoubleDict as shown in recipe 578224 on the Python Cookbook.


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

Another possible solution is to implement a subclass of dict, that holds the original dictionary and keeps track of a reversed version of it. Keeping two seperate dicts can be useful if keys and values are overlapping.

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. 

Example:

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

回答 10

pypi上有collections-extended库: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

There’s the collections-extended library on pypi: https://pypi.python.org/pypi/collections-extended/0.6.0

Using the bijection class is as easy as:

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

回答 11

我喜欢其中一项评论中关于二分法的建议。

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

I like the suggestion of bidict in one of the comments.

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.

Prints:

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

回答 12

kjbuckets C扩展模块提供了“图形”数据结构,我相信它可以为您提供所需的内容。

The kjbuckets C extension module provides a “graph” data structure which I believe gives you what you want.


回答 13

这是通过扩展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'

Here’s one more two-way dictionary implementation by extending pythons dict class in case you didn’t like any of those other ones:

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'

回答 14

我喜欢做这种事情的一种方式是:

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

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

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