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

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

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

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

Answer 1

Вместо

d[n1] = 'Node 1'

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

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

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

Я не верю, что есть способ с словарями для извлечения оригинального ключа K1, если все, что у вас есть, является K2, равный 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

Вот способ использовать пользовательский объект узла с 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

Answer 4

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

d[my_id]=d[my_id] 

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

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

Answer 5

Использование 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
        ...