파이썬에 대한 리버 서블 사전

Question

파이썬에서 사전에 비슷한 형식으로 데이터를 저장하고 싶습니다. {1:'a', 2:'b'}. 모든 값은 다른 값 중에서뿐만 아니라 키 사이에서도 고유합니다.

'키'또는 '값'을 사용하여 질문하는 경우에도 해당 객체를 가져올 수있는 간단한 데이터 구조가 있습니까? 예를 들어

>>> a = {1:'a', 2:'b'} 
>>> a[1] 
'a' 
>>> a['b'] 
2 
>>> a[3] 
KeyError 

'키는'표준 파이썬의 int가있다 값은 (< 256char) 문자열 짧다.

내가 원래 사전에서 결과를 찾을 수없는 경우 반전 된 사전을 만들고 그것을 검색하는 내 현재 솔루션 :이 두 배의 공간을 사용

pointsreversed = dict((v, k) for k, v in points.iteritems()) 
def lookup(key): 
    return points.get(key) or pointsreversed.key() 

, 잘되지 않습니다 (내 사전 수 백 메가까지 가능) 평균적으로 50 % 더 느립니다.

EDIT : 몇 개의 답변에서 언급했듯이 두 개의 dict은 중복 된 항목이 아닌 사전 만 사용하므로 메모리 사용량을 두 배로 늘리지는 않습니다.

해결 방법이 있습니까?

Answer 1

관련 게시물 :

Python mapping inverse

물론

Python 1:1 mappings

, 모든 값 및 키가 고유 경우, 당신은 단지 하나의 사전을 사용하고, 키를 모두 삽입 할 수 있습니다 : 가치와 가치를 : 처음에는 열쇠? 당신이 필요

a = {1:'a', 2:'b'} 
a.update(dict((v, k) for k, v in a.iteritems())) 

그런 다음 당신은 둘 다 할 수있을 것입니다 : 당신의 키와 값 인 경우

print a[1] 
print a['a'] 

Answer 2

삽입 같은 DICT에 (키, 값) 쌍을 반전 겹쳐지지 않는 한 가지 명백한 접근법은 단순히 동일한 사전에 이들을 저장하는 것입니다. 예 :

class BidirectionalDict(dict): 
    def __setitem__(self, key, val): 
     dict.__setitem__(self, key, val) 
     dict.__setitem__(self, val, key) 

    def __delitem__(self, key): 
     dict.__delitem__(self, self[key]) 
     dict.__delitem__(self, key) 

d = BidirectionalDict() 
d['foo'] = 4 
print d[4] # Prints 'foo' 

(당신은 또한 아마 __init__, update 및 iter* 방법 같은 것들을 당신이 필요로 얼마나 많은 기능에 따라 실제 딕셔너리처럼 행동 구현하려는 것이다).

이것은 하나의 조회 만 포함해야하지만 많은 메모리를 절약 할 수는 없습니다 (결국 dict 항목의 수는 두 배입니다). 그러나 이것도 원본은 두 배나 많은 공간을 사용하지 않습니다. 사전은 참조 공간 (유효 포인터)과 전체 오버 헤드 오버 헤드를 차지합니다. 데이터 자체가 차지하는 공간은 동일한 객체를 가리키고 있기 때문에 두 번 반복되지 않습니다.

Answer 3

Answer 4

다음은 사용자 정의 클래스를 사용하는 another solution입니다.

코드 ...

# search a dictionary for key or value 
# using named functions or a class 
# tested with Python25 by Ene Uran 01/19/2008 

def find_key(dic, val): 
    """return the key of dictionary dic given the value""" 
    return [k for k, v in symbol_dic.iteritems() if v == val][0] 

def find_value(dic, key): 
    """return the value of dictionary dic given the key""" 
    return dic[key] 

class Lookup(dict): 
    """ 
    a dictionary which can lookup value by key, or keys by value 
    """ 
    def __init__(self, items=[]): 
     """items can be a list of pair_lists or a dictionary""" 
     dict.__init__(self, items) 

    def get_key(self, value): 
     """find the key(s) as a list given a value""" 
     return [item[0] for item in self.items() if item[1] == value] 

    def get_value(self, key): 
     """find the value given a key""" 
     return self[key] 

Answer 5

컴퓨터 프로그래밍의 기술에서 Vokume 3 Knuth는 보조 키를 조회하는 섹션을 가지고 있습니다. 귀하의 질문에 대한 목적으로이 값은 보조 키로 간주 될 수 있습니다.

첫 번째 제안은 수행 한 작업을 수행하는 것입니다. 값으로 키의 효율적인 색인을 만드십시오.

두 번째 제안은 분기 노드가 값을 포함하고 리프에 키 데이터와 큰 레코드에 대한 포인터가있는 클러스터 된 데이터의 복합 인덱스 인 큰 b 트리를 설정하는 것입니다 (

).

데이터가 기하학적 인 경우 (귀하의 것으로 보이는 것처럼) 우체국 나무라고하는 것이 있습니다. 그것은 x를 가리키는 가장 가까운 대상이 무엇인지 같은 질문에 대답 할 수 있습니다. 다음은 몇 가지 예입니다. http://simsearch.yury.name/russir/01nncourse-hand.pdf이 종류의 쿼리에 대한 또 다른 간단한 옵션은 quadtree 및 k-d 트리입니다. http://en.wikipedia.org/wiki/Quadtree

또 다른 마지막 옵션은 키와 값을 특별한 종류의 해시로 결합하는 조합 해싱입니다.이 두 가지 값이 모두없는 경우에도 해시를 효율적으로 조회 할 수 있습니다. 온라인에서 좋은 조합 해시 설명을 찾을 수는 없지만, 573 페이지의 제 3 권 제 2 판, TAoCP에 있습니다.

승인되었습니다. 일부는 사용자 자신의 코드를 작성해야 할 수도 있습니다. 그러나 메모리 또는 성능이 정말로 핵심이라면 시간을 투자 할 수 있습니다.

Answer 6

"두 배의 공간"을 사용해서는 안됩니다. 사전은 데이터 자체가 아닌 데이터에 대한 참조를 저장합니다. 따라서 10 억 바이트를 초과하는 백만 개의 문자열이있는 경우 각 사전은 아마도 10-20 억 바이트를 추가로 차지하게됩니다. 이는 전체 저장 공간의 아주 작은 부분입니다. 두 개의 사전을 사용하는 것이 올바른 일입니다.