В Python, как вы можете получить ключ от словаря?
-
26-09-2019 - |
Вопрос
У меня есть хешарный идентификатор для положения вещей в словаре:
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. Если вы храните объект в словаре «Атрибут Node», вы можете использовать его в качестве обратного словаря, чтобы вернуть объект, ссылающийся на идентификатор. Это немного неловко, но это работает.
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]
Все равно все равно будет работать, кроме сейчас, ваш ключ - идентификатор, а не узел. Позволяя двух классам «равным», как это, действительно опасно. Если вам действительно нужно найти узел, имеющее имя, которое должно быть сделано в классе узла или внешности, но не следует зависеть от наличия не у узла в хеш.
Если вы не можете изменить это (потому что вы не можете изменить код), то я думаю, вы застряли, чтобы сделать неэффективное значение
Использование My_id для поиска «узла 2» на самом деле необходимо дойти в поиску N2 в качестве промежуточного шага
Это не правда. Отказ Словарь - это hashtable: он отображает хеш элемента для (ведро) записей. Когда вы просите 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
...