In Python, come si può recuperare una chiave da un dizionario?

Question

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!

Answer 1

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.

Answer 2

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]

Answer 3

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

Answer 4

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

Answer 5

  

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
        ...