양방향 / 역지도

양방향 / 역지도

---

저는 파이썬에서이 스위치 보드 작업을하고 있습니다. 여기서 누가 누구와 이야기하고 있는지 추적해야합니다. 따라서 Alice-> Bob이라면 이는 Bob-> Alice를 의미합니다.

예, 두 개의 해시 맵을 채울 수 있지만 누군가 하나로 할 아이디어가 있는지 궁금합니다.

또는 다른 데이터 구조를 제안하십시오.

여러 대화가 없습니다. 이것이 고객 서비스 콜 센터 용이라고 가정 해 보겠습니다. Alice가 스위치 보드에 전화를 걸면 그녀는 Bob 과만 대화 할 것입니다. 그의 대답은 그녀에게만 전달됩니다.

---

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

---

나는 그것이 오래된 질문이라는 것을 알고 있지만이 문제에 대한 또 다른 훌륭한 해결책, 즉 python package bidict 를 언급하고 싶었 습니다 . 사용하는 것은 매우 간단합니다.

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

---

메모리를 절약 할 수 있다고 가정하면 두 개의 해시 맵이 실제로 가장 빠른 성능의 솔루션 일 것입니다. 나는 그것들을 단일 클래스로 래핑 할 것입니다. 프로그래머의 부담은 두 개의 해시 맵이 올바르게 동기화되도록하는 것입니다.

---

두 가지 문제가 있습니다.

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 )

---

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.

---

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'

참고URL : https://stackoverflow.com/questions/1456373/two-way-reverse-map