Python dict
은 매우 유용한 데이터 구조입니다.
d = {'a': 1, 'b': 2}
d['a'] # get 1
때로는 값으로 인덱싱하고 싶을 수도 있습니다.
d[1] # get 'a'
이 데이터 구조를 구현하는 가장 효율적인 방법은 무엇입니까? 공식적으로 권장하는 방법이 있습니까?
답변
다음은 Python 사전의 값에서 키 찾기dict
에서 영감을 받아 다음 2) 및 3)을 허용하도록 수정 된 양방향 클래스입니다 .
참고 :
- 1) 역 디렉토리
bd.inverse
는 표준 dictbd
가 수정 되면 자동으로 업데이트됩니다 . - 2) 역 디렉토리
bd.inverse[value]
는 항상 다음 과key
같은 목록 입니다bd[key] == value
. - 3) https://pypi.python.org/pypi/bidict 의
bidict
모듈 과 달리 여기서는 동일한 값을 가진 2 개의 키를 가질 수 있습니다 . 이것은 매우 중요 합니다.
암호:
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 = dict ([reversed (i) for i in d.items ()]) d. 업데이트 (revd)
답변
가난한 사람의 양방향 해시 테이블은 두 개의 사전 만 사용하는 것입니다 (이는 이미 고도로 조정 된 데이터 구조입니다).
색인에 bidict 패키지 도 있습니다 .
bidict의 소스는 github에서 찾을 수 있습니다.
답변
아래 코드 스 니펫은 반전 가능한 (용사) 맵을 구현합니다.
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
a 속성 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 개의 dict 의 래퍼 인 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]
답변
불행히도 가장 높은 등급의 답변 bidict
은 작동하지 않습니다.
세 가지 옵션이 있습니다.
-
하위 클래스 사전 :의 하위 클래스를 만들 수
dict
있지만주의해야합니다. 당신의 사용자 정의 구현을 작성해야합니다update
,pop
,initializer
,setdefault
.dict
구현은 호출하지 않습니다__setitem__
. 이것이 가장 높은 등급의 답변에 문제가있는 이유입니다. -
UserDict에서 상속 : 이것은 모든 루틴이 올바르게 호출된다는 점을 제외하면 dict와 같습니다. 라는 항목에서 내부적으로 dict를 사용합니다
data
. Python 문서를 읽 거나 Python 3에서 작동하는 방향 별 목록의 간단한 구현을 사용할 수 있습니다 . 그대로 포함하지 않아서 죄송합니다. 저작권이 확실하지 않습니다. -
추상 기본 클래스 에서 상속 : collections.abc 에서 상속 하면 새 클래스에 대한 모든 올바른 프로토콜과 구현을 얻을 수 있습니다. 이것은 데이터베이스에 암호화하고 캐시 할 수없는 한 양방향 사전의 경우 과잉입니다.
TL; DR- 코드에 이것을 사용하십시오 . 자세한 내용은 Trey Hunner 의 기사 를 읽어보십시오 .