В Python, как вы можете получить ключ из словаря?
У меня есть хешируемый идентификатор для размещения вещей в словаре:
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), но вижу словарь, в котором хранятся мои узлы. Я мог бы также сохранить дополнительный словарь вокруг идентификаторов для узлов, но это было бы болезненно (мне нужно было обернуть класс графа и переписать все, добавить узел, удалить узел, добавить узлы из списка, удалить узлы из списка, добавить ребро и т. д. введите функции, чтобы поддерживать этот словарь в актуальном состоянии).
Это довольно загадка. Любая помощь могла бы быть полезна!
5 ответов
Вместо
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
использование my_id для поиска "Узел 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
...
Дело в том, что нет никакой гарантии, что ключ фактически является Узлом. Что делать, если вы делаете
d[my_id]=d[my_id]
Все по-прежнему будет работать отлично, за исключением того, что ваш ключ является Идентификатором, а не Узлом. Позволить двум классам "равняться", как это действительно опасно. Если вам действительно нужно найти Node по его имени, это должно быть сделано в классе Node или внешним образом, но не должно зависеть от присутствия узла в хэше.
Если вы не можете изменить это (потому что вы не можете изменить код), то я думаю, что вы застряли, чтобы сделать неэффективный путь