В 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. Если вы храните объект в словаре "атрибут узла" Вы можете использовать его в качестве обратного словаря, чтобы получить Возвратите объект, ссылаясь на идентификатор. Это немного неловко но это работает.

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

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

Answer 5

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

d[my_id]=d[my_id] 

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

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