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

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

파이썬dict는 매우 유용한 데이터 구조입니다.

d = {'a': 1, 'b': 2}

d['a'] # get 1

값을 기준으로 인덱스를 작성할 수도 있습니다.

d[1] # get 'a'

이 데이터 구조를 구현하는 가장 효율적인 방법은 무엇입니까?공식적으로 추천할 만한 방법이 있습니까?

양방향에 대한 클래스입니다.dictPython 사전의 Finding from value에서 영감을 받아 다음 2)과 3)을 허용하도록 수정했습니다.

참고:

• 1. 역 디렉터리 bd.inverse표준 dict 시 자동 검색bd수정되었습니다.
• 2. 역 디렉터리 bd.inverse[value]항상 의 목록입니다.key할 정도로bd[key] == value.
• 3. 과는 달리bidict여기 https://pypi.python.org/pypi/bidict, 의 모듈은 동일한 값을 가진 두 개의 키를 가질 수 있습니다. 이것은 매우 중요합니다.

코드:

class bidict(dict):
    def __init__(self, *args, **kwargs):
        super(bidict, self).__init__(*args, **kwargs)
        self.inverse = {}
        for key, value in self.items():
            self.inverse.setdefault(value, []).append(key) 

    def __setitem__(self, key, value):
        if key in self:
            self.inverse[self[key]].remove(key) 
        super(bidict, self).__setitem__(key, value)
        self.inverse.setdefault(value, []).append(key)        

    def __delitem__(self, key):
        self.inverse.setdefault(self[key], []).remove(key)
        if self[key] in self.inverse and not self.inverse[self[key]]: 
            del self.inverse[self[key]]
        super(bidict, self).__delitem__(key)

사용 예:

bd = bidict({'a': 1, 'b': 2})  
print(bd)                     # {'a': 1, 'b': 2}                 
print(bd.inverse)             # {1: ['a'], 2: ['b']}
bd['c'] = 1                   # Now two keys have the same value (= 1)
print(bd)                     # {'a': 1, 'c': 1, 'b': 2}
print(bd.inverse)             # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print(bd)                     # {'a': 1, 'b': 2}
print(bd.inverse)             # {1: ['a'], 2: ['b']}
del bd['a']
print(bd)                     # {'b': 2}
print(bd.inverse)             # {2: ['b']}
bd['b'] = 3
print(bd)                     # {'b': 3}
print(bd.inverse)             # {2: [], 3: ['b']}

키, 값 쌍을 역순으로 추가하여 동일한 딕트 자체를 사용할 수 있습니다.

d={'a':1,'b':2}revd=messages([i는 d.sigma)의 i에 해당함)d.업데이트(revd)

가난한 사람의 양방향 해시 테이블은 사전 두 개만 사용하는 것입니다(이미 매우 조정된 데이터 구조임).

인덱스에는 이항식 패키지도 있습니다.

• https://pypi.python.org/pypi/bidict

바이딕트의 소스는 github에서 찾을 수 있습니다.

• https://github.com/jab/bidict

아래 코드 조각은 반전 가능한 (객관적) 맵을 구현합니다.

class BijectionError(Exception):
    """Must set a unique value in a BijectiveMap."""

    def __init__(self, value):
        self.value = value
        msg = 'The value "{}" is already in the mapping.'
        super().__init__(msg.format(value))


class BijectiveMap(dict):
    """Invertible map."""

    def __init__(self, inverse=None):
        if inverse is None:
            inverse = self.__class__(inverse=self)
        self.inverse = inverse

    def __setitem__(self, key, value):
        if value in self.inverse:
            raise BijectionError(value)

        self.inverse._set_item(value, key)
        self._set_item(key, value)

    def __delitem__(self, key):
        self.inverse._del_item(self[key])
        self._del_item(key)

    def _del_item(self, key):
        super().__delitem__(key)

    def _set_item(self, key, value):
        super().__setitem__(key, value)

이 구현의 장점은 다음과 같습니다.inverse의 속성BijectiveMap다시 한 번BijectiveMap따라서 다음과 같은 작업을 수행할 수 있습니다.

>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True

이와 같은 것, 아마도:

import itertools

class BidirDict(dict):
    def __init__(self, iterable=(), **kwargs):
        self.update(iterable, **kwargs)
    def update(self, iterable=(), **kwargs):
        if hasattr(iterable, 'iteritems'):
            iterable = iterable.iteritems()
        for (key, value) in itertools.chain(iterable, kwargs.iteritems()):
            self[key] = value
    def __setitem__(self, key, value):
        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):
        value = self[key]
        dict.__delitem__(self, key)
        dict.__delitem__(self, value)
    def __repr__(self):
        return '%s(%s)' % (type(self).__name__, dict.__repr__(self))

둘 이상의 키에 지정된 값이 있는 경우 수행할 작업을 결정해야 합니다. 지정된 쌍의 양방향성은 나중에 삽입한 쌍에 의해 쉽게 손상될 수 있습니다.저는 가능한 한 가지 선택을 구현했습니다.

---

예:

bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1']   # a
print bd['myvalue2']   # b        

먼저, 가치 매핑의 핵심이 일대일인지 확인해야 합니다. 그렇지 않으면 양방향 지도를 구축할 수 없습니다.

둘째, 데이터 세트의 크기는 얼마나 됩니까?데이터가 많지 않다면 2개의 별도 맵을 사용하고, 업데이트 시 둘 다 업데이트합니다.또는 업데이트/삭제 기능이 내장된 2개의 딕트 포장지에 불과한 Bidict와 같은 기존 솔루션을 사용하는 것이 좋습니다.

그러나 데이터 세트가 크고 2개의 딕트를 유지하는 것이 바람직하지 않은 경우:

• 키와 값이 모두 숫자인 경우 보간을 사용하여 매핑을 근사화할 수 있습니다.키-값 쌍의 대부분을 매핑 함수(및 그 함수)로 커버할 수 있는 경우
  역함수), 그런 다음 지도에 특이치만 기록하면 됩니다.

• 대부분의 액세스가 단방향(키->값)인 경우, 역방향 맵을 점진적으로 구축하여 시간을 교환하는 것이 좋습니다.
  공간. 공간.

코드:

d = {1: "one", 2: "two" }
reverse = {}

def get_key_by_value(v):
    if v not in reverse:
        for _k, _v in d.items():
           if _v == v:
               reverse[_v] = _k
               break
    return reverse[v]

더 좋은 방법은 사전을 튜플 목록으로 변환한 다음 특정 튜플 필드에서 정렬하는 것입니다.

def convert_to_list(dictionary):
    list_of_tuples = []
    for key, value in dictionary.items():
        list_of_tuples.append((key, value))
    return list_of_tuples

def sort_list(list_of_tuples, field):
     return sorted(list_of_tuples, key=lambda x: x[field])

dictionary = {'a': 9, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
list_of_tuples = convert_to_list(dictionary)
print(sort_list(list_of_tuples, 1))

산출량

[('b', 2), ('c', 3), ('d', 4), ('e', 5), ('a', 9)]

가장 를 받은 답인 유스럽도게감, 가높평받대은은답를가은장가▁unfortun대,,은,bidict작동하지 않습니다.

세 가지 옵션이 있습니다.

1. 하위 클래스 딕트:다음의 하위 클래스를 만들 수 있습니다.dict하지만 조심하세요.의 사용자 정의 .update,pop,initializer,setdefault.dict에서는 구이호지않을 호출하지 .__setitem__이것이 최고 등급의 답변에 문제가 있는 이유입니다.

2. UserDict에서 상속:모든 루틴이 올바르게 호출된다는 점을 제외하면 이것은 딕트와 같습니다.그것은 후드 아래에 있는 명령어를 사용합니다, 라고 불리는 항목에서.dataPython Documentation을 읽거나 Python 3에서 작동하는 by directional 목록의 간단한 구현을 사용할 수 있습니다.말 그대로 포함하지 않아서 죄송합니다.저작권에 대해서는 잘 모르겠습니다.

3. 추상 기본 클래스에서 상속:collections.abc에서 상속하면 새 클래스에 대한 모든 올바른 프로토콜 및 구현을 얻을 수 있습니다.이는 양방향 사전이 데이터베이스에 암호화 및 캐시할 수 있는 경우를 제외하고는 오버킬입니다.

TL;DR - 코드에 사용합니다.자세한 내용은 트레이 허너의 기사를 읽으십시오.

언급URL : https://stackoverflow.com/questions/3318625/how-to-implement-an-efficient-bidirectional-hash-table