In Python, come si può recuperare una chiave da un dizionario?
-
26-09-2019 - |
Domanda
Ho un identificatore hashable per mettere le cose in un dizionario:
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
Ho un tipo di nodo che incapsula identifer a fini di hashing e di uguaglianza:
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
ho messo alcuni nodi in un dizionario:
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'
Qualche tempo dopo, ho solo un identificatore:
my_id = identifier({'name':'Alex'})
C'è un modo per occhiata in modo efficiente il nodo che è stato memorizzato con questo identificatore in questo dizionario?
Si prega di notare che questo è un po 'più complicato di quanto non sembri; So che posso banalmente usare d[my_id]
per recuperare l'elemento 'Node 2'
associato, ma Voglio tornare in modo efficiente un riferimento alla n2
.
So che avrei potuto farlo, cercando in ogni elemento in d
, ma ho provato e che è troppo lento (il dizionario ha migliaia di articoli in esso e lo faccio un discreto numero di volte).
so che internamente dict
sta usando gli operatori hash
e eq
per questo identificativo per nodo di archivio n2
e la sua voce associato, 'Node 2'
. Infatti, utilizzando my_id
di ricercare 'Node 2'
effettivamente bisogno di ricercare n2
come fase intermedia, quindi questo deve assolutamente essere possibile.
Sto usando questo per memorizzare i dati in un grafico. I nodi hanno un sacco di dati aggiuntivi (dove ho messo value
) che non viene utilizzato nel hash. Non ho creato il pacchetto grafico che sto usando (NetworkX), ma posso vedere il dizionario che memorizza i miei nodi. Potrei anche tenere un dizionario di più intorno di identificatori a nodi, ma questo sarebbe un dolore (avrei bisogno di avvolgere la classe grafico e riscrivere tutti i nodi aggiuntivi, nodo di rimuovere, aggiungere nodi da elenco, nodi di rimuovere dalla lista, aggiungere un margine , ecc funzioni di tipo per mantenere quel dizionario fino ad oggi).
Questo è abbastanza il puzzle. Qualsiasi aiuto sarebbe molto apprezzato!
Soluzione
Al posto di
d[n1] = 'Node 1'
utilizzo:
d[n1] = ('Node 1', n1)
Poi si ha accesso a n1 non importa come hai trovato il valore.
Non credo ci sia un modo con i dizionari per recuperare la chiave originale k1 se tutto quello che hai è un k2 uguale a k1.
Altri suggerimenti
Ha due dizionari. -. Ogni volta che si aggiunge una chiave / valore al dizionario primaria, aggiungerli anche al dizionario inverso, ma con la chiave / valore scambiato
Ad esempio:
# 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]
Ecco un modo per utilizzare un oggetto nodo personalizzato con NetworkX. Se si memorizza l'oggetto nel dizionario "nodo attributo" è possibile utilizzarlo come un dizionario inverso per ottenere il oggetto nuovamente facendo riferimento l'id. E 'un po' imbarazzante ma funziona.
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'}
È possibile definire, naturalmente, una funzione che rende questo più semplice:
def get_node(G,n):
return G.node[Node(1)]['obj']
n=get_node(G,1)
print n.properties
Il fatto è che non v'è alcuna garanzia che la chiave è effettivamente un nodo. Che cosa succede se si fa
d[my_id]=d[my_id]
Tutto sarebbe ancora funzionare perfettamente solo che adesso, la chiave è un identificatore e non un nodo. Permettere due classi di "uguale" come questo è veramente pericoloso. Se davvero bisogno di trovare un nodo in base al nome di essa la che dovrebbe essere fatto nella classe Node o l'esterno sia, ma non dovrebbe dipendere dalla presenza di non di nodo in un hash.
Se non è possibile modificare tale (perché non è possibile modificare il codice), allora credo che si sono bloccati per fare il modo ineffecient
utilizzando my_id di ricerca 'Nodo 2' effettivamente bisogno di ricercare n2 come passo intermedio
Questa è non è vero . Un dizionario è una tabella hash: mappa l'hash di un elemento per (un secchio di) voci. Quando chiedete d[my_id]
, Python prima ottiene hash(my_id)
e poi guarda che fino a d
. Stai confondersi perché avete che hash(n1) == hash(id1)
, che è una cosa molto brutta.
Si sta chiedendo una mappatura tra gli identificatori e nodi. Se si desidera uno di questi, si dovrà creare uno voi stessi.
Sono gli identificatori tutti abbinati con i nodi al momento della creazione, o non li costruiscono più tardi? Cioè, stai davvero chiedendo di essere in grado di trovare il nodo con identificatore identifier({'name':'Alex'})
, o è che identificatore già stato creato e aggiunto a un nodo? In quest'ultimo caso, si potrebbe procedere come segue:
class Node:
def __init__(self, id, value):
id.parent = self
...