В python, как вы можете получить ключ из словаря?

У меня есть hashable идентификатор для размещения вещей в словаре:

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 для поиска 'Node 2' действительно требует поиска n2 в качестве промежуточного шага, поэтому это определенно возможно.

Я использую это для хранения данных на графике. У узлов есть много дополнительных данных (где я положил value ), которые не используются в хэше. Я не создал пакет графа, который я использую (networkX), но я вижу словарь, который хранит мои узлы. Я мог бы также хранить дополнительный словарь вокруг идентификаторов для узлов, но это было бы болью (мне нужно было бы обернуть класс графа и переписать весь узел добавления, удалить узел, добавить узлы из списка, удалить узлы из списка, добавить ребро и т. д., чтобы поддерживать этот словарь в актуальном состоянии).

Это довольно загадка. Любая помощь могла бы быть полезна!

Вместо

 d[n1] = 'Node 1' 

использовать:

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

Тогда у вас есть доступ к n1 независимо от того, как вы нашли значение.

Я не верю, что есть способ с словарями получить исходный ключ k1, если все, что у вас есть, – k2, равное k1.

Есть два словаря. – Всякий раз, когда вы добавляете ключ / значение в основной словарь, также добавляйте их в обратный словарь, но с измененным ключом / значением.

Например:

 # 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] 

Ниже приведен пример использования пользовательского узла с NetworkX. Если вы храните объект в словаре «атрибут узла», вы можете использовать его в качестве обратного словаря, чтобы вернуть объект, ссылаясь на идентификатор. Это немного неудобно, но это работает.

 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'} 

Вы можете, конечно, определить функцию, которая делает это проще:

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

Дело в том, что нет гарантии, что ключ является эффективным Узлом. Что делать, если вы

 d[my_id]=d[my_id] 

Теперь все будет работать отлично, за исключением того, что теперь ваш ключ является идентификатором, а не узлом. Предоставление двум классам «равных», подобных этому, действительно опасно. Если вам действительно нужно найти узел по его имени, это должно быть сделано в классе Node или внешнем, но не должно зависеть от наличия не узла в хэше.

Если вы не можете изменить это (потому что вы не можете изменить код), я думаю, вы застряли, чтобы сделать неэффективный способ

используя my_id для поиска «Node 2», на самом деле нужно искать 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 ...