Em Python, como você pode recuperar uma chave de um dicionário?

Question

Eu tenho um identificador hashable para colocar as coisas em um dicionário:

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

Eu tenho um tipo de nó que encapsula o identificador para fins de hash e igualdade:

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

Eu coloquei alguns nós em um dicionário:

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'

Algum tempo depois, eu tenho apenas um identificador:

my_id = identifier({'name':'Alex'})

Existe alguma maneira de procurar com eficiência o nó que foi armazenado com esse identificador neste dicionário?

Observe que isso é um pouco mais complicado do que parece; Eu sei que posso usar trivialmente d[my_id] Para recuperar o item associado 'Node 2', mas Eu quero retornar com eficiência uma referência a n2.

Eu sei que poderia fazer isso olhando para todos os elementos em d, mas eu tentei isso e é muito lento (o dicionário tem milhares de itens e faço isso um número razoável de vezes).

Eu sei disso internamente dict está usando o hash e eq operadores para esse identificador armazenar o nó n2 e seu item associado, 'Node 2'. De fato, usando my_id procurar 'Node 2' realmente precisa procurar n2 como um passo intermediário, então Isso definitivamente deve ser possível.

Estou usando isso para armazenar dados em um gráfico. Os nós têm muitos dados adicionais (onde eu coloco value) que não é usado no hash. Não criei o pacote de gráficos que estou usando (NetworkX), mas posso ver o dicionário que armazena meus nós. Eu também poderia manter um dicionário extra em torno dos identificadores em nós, mas isso seria uma dor (eu precisaria envolver a classe do gráfico e reescrever todos Adicionar nó, remover o nó, adicionar nós da lista, remover nós da lista, adicionar borda , etc. Tipo funções para manter esse dicionário atualizado).

Este é o quebra -cabeça. Qualquer ajuda seria muito apreciada!

Answer 1

Ao invés de

d[n1] = 'Node 1'

usar:

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

Então você tem acesso ao N1, não importa como você encontrou o valor.

Não acredito que haja um caminho com os dicionários para recuperar a chave original K1 se tudo o que você tem é um K2 igual a K1.

Answer 2

Tem dois dicionários. - Sempre que você adiciona uma chave/valor ao dicionário primário, também os adicione ao dicionário reverso, mas com a chave/valor trocada.

Por exemplo:

# 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

Aqui está uma maneira de usar um objeto de nó personalizado com o NetworkX. Se você armazenar o objeto no dicionário "Nó atributo", poderá usá -lo como um dicionário reverso para recuperar o objeto, referenciando o ID. É um pouco estranho, mas funciona.

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

É claro que você pode definir uma função que simplifique isso:

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

    n=get_node(G,1)
    print n.properties

Answer 4

O problema é que não há garantia de que a chave é efetivamente um nó. E se você fizer

d[my_id]=d[my_id] 

Tudo ainda funcionaria perfeitamente, exceto agora, sua chave é um identificador e não um nó. Permitir que duas classes "iguais" como essa sejam realmente perigosas. Se você realmente precisa encontrar um nó pelo nome que deve ser feito na classe ou externa do nó, mas não deve depender da presença de não do nó em um hash.

Se você não pode modificar isso (porque não pode modificar o código), acho que você está preso a fazer da maneira ineficaz

Answer 5

Usando my_id para procurar 'nó 2' realmente precisa procurar n2 como uma etapa intermediária

Isto é Não é verdade. Um dicionário é uma hashtable: mapeia o hash de um item para (um balde de) entradas. Quando você pede d[my_id], Python primeiro recebe hash(my_id) E então parece isso d. Você está ficando confuso porque você tem isso hash(n1) == hash(id1), o que é uma coisa muito ruim.

Você está pedindo um mapeamento entre identificadores e nós. Se você quiser um desses, terá que criar um você mesmo.

---

Os identificadores são todos combinados com nós na criação, ou você os constrói mais tarde? Isto é, você é verdade pedindo para poder encontrar o nó com identificador identifier({'name':'Alex'}), ou esse identificador já foi criado e adicionado a um nó? Se este último, você pode fazer o seguinte:

class Node:
    def __init__(self, id, value):
        id.parent = self
        ...