两路/反向映射[重复]

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.

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.

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

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

I would just populate a second hash, with

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

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.

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 )

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.

A less verbose way, still using reversed:

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

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

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

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

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

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

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'

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

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