파이썬에서 어떻게 사전에서 키를 검색 할 수 있습니까?

Question

사전에 물건을 넣을 수있는 해시 가능한 식별자가 있습니다.

class identifier(): 
    def __init__(self, d): 
     self.my_dict = d 
     self.my_frozenset = frozenset(d.items()) 
    def __getitem__(self, item): 
     return self.my_dict[item] 
    def __hash__(self): 
     return hash(self.my_frozenset) 
    def __eq__(self, rhs): 
     return self.my_frozenset == rhs.my_frozenset 
    def __ne__(self, rhs): 
     return not self == rhs 

해시 및 평등을 위해 식별자를 캡슐화하는 노드 형식이 있습니다.

class node: 
    def __init__(self, id, value): 
     # id is of type identifier 
     self.id = id 
     self.value = value 
     # define other data here... 
    def __hash__(self): 
     return hash(self.id) 
    def __eq__(self, rhs): 
     if isinstance(rhs, node): 
      return self.id == rhs.id 
     ### for the case when rhs is an identifier; this allows dictionary 
     ### node lookup of a key without wrapping it in a node 
     return self.id == rhs 
    def __ne__(self, rhs): 
     return not self == rhs 

일부 노드를 사전에 넣습니다.

d = {} 
n1 = node(identifier({'name':'Bob'}), value=1) 
n2 = node(identifier({'name':'Alex'}), value=2) 
n3 = node(identifier({'name':'Alex', 'nationality':'Japanese'}), value=3) 
d[n1] = 'Node 1' 
d[n2] = 'Node 2' 
d[n3] = 'Node 3' 

얼마 후, 나는 유일한 식별자가 있습니다.

my_id = identifier({'name':'Alex'}) 

이 사전에이 식별자와 함께 저장된 노드를 효율적으로 검색하는 방법이 있습니까?

이것은 소리보다 조금 까다 롭습니다. 나는 쉽게 d[my_id]을 사용하여 관련 항목 'Node 2'를 검색 할 수 있지만 는 n2에 대한 참조를 효율적으로 반환하고자합니다.

d의 모든 요소를 ​​살펴봄으로써이 작업을 수행 할 수 있음을 알고 있습니다.하지만 시도해 보았습니다. 너무 느립니다 (사전에 수천 개의 항목이 있으며 시간이 많이 걸립니다).

내부적으로 dict가 해당 식별자에 대해 hash 및 eq 연산자를 사용하여 노드 n2 및 관련 항목 'Node 2'을 저장한다는 것을 알고 있습니다. 사실, my_id을 찾기 위해 my_id을 사용하면 실제로 n2를 중간 단계로 검색해야하므로 이 가능해야합니다.

이 데이터를 그래프에 저장하는 데 사용하고 있습니다. 노드에는 해시에 사용되지 않는 추가 데이터가 많이 있습니다 (여기서 value을 넣습니다). 나는 (networkX) 사용하고있는 그래프 패키지를 만들지 않았지만 내 노드를 저장하는 사전을 볼 수있다. 나는 또한 노드에 대한 식별자 주위에 여분의 사전을 유지할 수 있지만 이것은 고통이 될 것이다 (나는 그래프 클래스를 래핑하고 모든 노드를 다시 작성해야한다. 노드를 제거하고 목록에서 노드를 추가하고 목록에서 노드를 제거하고 가장자리를 추가해야한다. , 등등은 해당 사전을 최신 상태로 유지하는 기능).

이것은 꽤 수수께끼입니다. 어떤 도움이라도 정말 감사 할 것입니다!

Answer 1

:

d[n1] = ('Node 1', n1) 

그런 다음 당신은 상관없이 가치를 발견하는 방법 (N1)에 액세스 할 수 없습니다.

당신이 가지고있는 모든 키가 k1 인 경우 원래 키 k1을 검색하는 방법이 있다고 생각하지 않습니다.

Answer 2

두 개의 사전이 있습니다. - 키/값을 기본 사전에 추가 할 때마다 역 사전에도 키/값을 바꿔서 추가하십시오.예를 들어

는 :

# When adding a value: 
d[n2] = value; 
# Must also add to the reverse dictionary: 
rev[value] = d 

# This means that: 
value = d[n2] 
# Will be able to efficiently find out the key used with: 
key = rev[value] 

Answer 3

건이며, 키가 효과적으로 노드입니다 아무 보증도 없다. 당신이 할 경우 무엇

d[my_id]=d[my_id] 

지금은 제외하고 모든 것이 여전히 완벽하게 작동합니다. 귀하의 키는 노드가 아니라 식별자입니다. 2 개의 클래스가 이와 같이 "동일"하도록 허용하는 것은 실제로 위험합니다. Node 클래스에서 수행해야하는 이름으로 Node를 찾으려면 실제로 필요하지만 해시에있는 노드가 아닌 노드의 존재 여부에 의존해서는 안됩니다. 당신이를 수정할 수없는 경우 (코드를 수정할 수 없기 때문에)

, 나는 당신이 '노드 2'를 조회 할 MY_ID를 사용하여 ineffecient 방법

Answer 4

을 할 붙어 추측 실제로 필요 중간 단계

같은 룩업 (N2)이 참아니다. 사전은 해시 테이블입니다. 항목의 해시를 항목 (버켓)으로 매핑합니다. d[my_id]을 요청하면 Python은 먼저 hash(my_id)을 얻은 다음 d을 찾습니다. hash(n1) == hash(id1)을 가지고 있기 때문에 혼란스러워집니다. 이것은 매우 나쁜 일입니다.

식별자와 노드 간의 매핑을 요청하고 있습니다. 이 중 하나가 필요하면 자신을 만들어야합니다.

---

식별자가 모두 생성시 노드와 일치합니까? 아니면 나중에 구성합니까? 다시 말하면 식별자가 identifier({'name':'Alex'}) 인 노드를 찾을 수 있도록 요청했거나 식별자가 이미 만들어져 노드에 추가되어 있습니까? 후자의 경우 다음을 수행 할 수 있습니다.

class Node: 
    def __init__(self, id, value): 
     id.parent = self 
     ... 

Answer 5

다음은 NetworkX에서 사용자 정의 노드 객체를 사용하는 방법입니다. "node attribute"사전 에 객체를 저장하는 경우 역방향 사전으로 사용하여 객체를 가져오고 id를 참조 할 수 있습니다. 조금 어색한 이지만 작동합니다.

import networkx as nx 

class Node(object): 

    def __init__(self,id,**attr): 
     self.id=id 
     self.properties={} 
     self.properties.update(attr) 

    def __hash__(self): 
     return self.id 

    def __eq__(self,other): 
     return self.id==other.id 

    def __repr__(self): 
     return str(self.id) 

    def __str__(self): 
     return str(self.id) 


G=nx.Graph() 
# add two nodes 
n1=Node(1,color='red') # the node id must be hashable 
n2=Node(2,color='green') 
G.add_node(n1,obj=n1) 
G.add_node(n2,obj=n2) 

# check what we have 
print G.nodes() # 1,2 
print n1,n1.properties['color'] # 1,red 
print n1==n2 # False 
for n in G: 
    print n.properties['color'] 
print Node(1) in G # True 
# change color of node 1 
n1.properties['color']='blue' 
for n in G: 
    print n.properties 

# use "node attribute" data in NetworkX to retrieve object 
n=G.node[Node(1)]['obj'] 
print type(n) # <class '__main__.Node'> 
print n # 1 
print n.id # 1 
print n.properties # {'color': 'blue'} 

당신은 물론이 간단하게 함수 정의 할 수 있습니다 : 실제로 사용할 수 있습니다있는 "노드 속성"의 내부 사전을 보관하지 NetworkX의

def get_node(G,n): 
     return G.node[Node(1)]['obj'] 

    n=get_node(G,1) 
    print n.properties