양방향/역방향 지도

양방향/역방향 지도

이 질문에는 이미 다음과 같은 답이 있습니다.

효율적인 양방향 해시 테이블을 구현하는 방법은 무엇입니까? (8개 답변)

마감됨2년 전에.

저는 python에서 교환기 작업을 하고 있습니다. 누가 누구와 이야기하고 있는지 추적해야 합니다. 그래서 만약 앨리스가 --> 밥이라면, 그것은 밥이 --> 앨리스라는 것을 암시합니다.

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

또는 다른 데이터 구조를 제안합니다.

다중 대화가 없습니다.여기가 고객 서비스 콜센터라고 가정해 보겠습니다. 그래서 앨리스가 교환대에 전화를 걸 때, 그녀는 밥에게만 말을 걸 것입니다.그의 대답은 또한 그녀에게만 전달됩니다.

하위 분류를 통해 자신만의 사전 유형을 만들 수 있습니다.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

오래된 질문인 것은 알지만, 저는 이 문제에 대한 또 다른 훌륭한 해결책, 즉 파이썬 패키지 바이딕트를 언급하고 싶었습니다.사용법은 매우 간단합니다.

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

두 번째 해시를 채우면 됩니다.

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

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

덜 장황한 방법, 여전히 반대로 사용:

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

두 가지 문제가 있습니다.

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 )

아니요, 사전 두 개를 만들지 않고는 이 작업을 수행할 수 없습니다.유사한 성능을 지속적으로 제공하면서 사전 하나로 이를 구현하는 것이 어떻게 가능합니까?

두 개의 사전을 캡슐화하고 원하는 기능을 표시하는 사용자 정의 유형을 만드는 것이 좋습니다.

을 사용할 도 있습니다.DoubleDict파이썬 쿡북의 레시피 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'}

pypi에는 컬렉션 라이브러리가 있습니다. 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

저는 댓글 중 하나에서 바이딕트의 제안이 마음에 듭니다.

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

kjbuckets C 확장 모듈은 당신이 원하는 것을 제공하는 "그래프" 데이터 구조를 제공합니다.

여기 파이썬을 확장하여 한 가지 더 양방향 사전 구현이 있습니다.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)

구성을 제외하고 일반 파이썬 사전으로 사용:

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

제가 이런 종류의 일을 하는 방법은 다음과 같습니다.

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

언급URL : https://stackoverflow.com/questions/1456373/two-way-reverse-map