En python, comment pouvez-vous récupérer une clé dans un dictionnaire?

Question

J'ai un identifiant hashable pour mettre les choses dans un dictionnaire:

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

J'ai un type de noeud qui encapsule identifer à des fins de hachage et de l'égalité:

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

Je mis quelques noeuds dans un dictionnaire:

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'

Quelque temps plus tard, j'ai seulement un identificateur:

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

Y at-il moyen de rechercher efficacement le nœud qui a été stocké avec cet identifiant dans ce dictionnaire?

S'il vous plaît noter que ceci est un peu plus délicat qu'il n'y paraît; Je sais que je peux utiliser trivialement d[my_id] pour récupérer le 'Node 2' d'élément associé, mais Je veux retourner efficacement une référence à n2 .

Je sais que je pouvais le faire en regardant chaque élément d, mais je l'ai essayé et il est beaucoup trop lent (le dictionnaire a des milliers d'articles en elle et je fais un numéro de juste de fois).

je sais que dict interne utilise les opérateurs de hash et eq pour cet identificateur de noeud de magasin n2 et son élément associé, 'Node 2'. En fait, en utilisant my_id pour rechercher 'Node 2' a réellement besoin de rechercher n2 comme une étape intermédiaire, donc cela devrait certainement être possible.

J'utilise ceci pour stocker des données dans un graphique. Les nœuds ont beaucoup de données supplémentaires (où je mets value) qui n'est pas utilisé dans le hachage. Je n'ai pas créé le paquet graphique J'utilise (NetworkX), mais je peux voir le dictionnaire qui stocke mes nœuds. Je pourrais aussi garder un dictionnaire supplémentaire autour des identificateurs aux noeuds, mais ce serait une douleur (je aurais besoin d'envelopper la classe graphique et réécrire tout noeud ajouter, supprimer noeud, ajouter des nœuds de la liste, supprimer des nœuds de la liste, ajoutez bord , etc. fonctions de type pour garder ce dictionnaire à jour).

Ceci est tout à fait le casse-tête. Toute aide serait vraiment apprécié!

Answer 1

Au lieu de

d[n1] = 'Node 1'

utilisation:

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

Ensuite, vous avez accès à n1, peu importe comment vous avez trouvé la valeur.

Je ne crois pas qu'il y ait un moyen de dictionnaires pour récupérer la clé k1 d'origine si tout ce que vous avez est un égale à k1 k2.

Answer 2

Avoir deux dictionnaires.  -. Chaque fois que vous ajoutez une clé / valeur au dictionnaire principal, ajoutez également au dictionnaire inverse, mais avec la permutés clé / valeur

Par exemple:

# 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

Voici un moyen d'utiliser un objet noeud personnalisé avec NetworkX. Si vous stockez l'objet dans le dictionnaire « attribut noeud » vous pouvez l'utiliser comme un dictionnaire inverse pour obtenir le objet en arrière en faisant référence à l'identifiant. Il est un peu maladroit mais cela fonctionne.

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

Vous pouvez définir de bien sûr une fonction qui rend ce plus simple:

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

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

Answer 4

La chose est, il n'y a aucune garantie que la clé est effectivement un nœud. Que faire si vous faites

d[my_id]=d[my_id] 

Tout fonctionne encore parfaitement excepter maintenant, votre clé est un identificateur et non un nœud. Permettre à deux classes « égal » comme celui-ci est vraiment dangereux. Si vous avez vraiment besoin de trouver un nœud par ce nom qui devrait être fait dans la classe Node ou externaly, mais ne doit pas dépendre de la présence non du nœud dans un hachage.

Si vous ne pouvez pas modifier ce (parce que vous ne pouvez pas modifier le code), alors je suppose que vous êtes coincé à faire le chemin ineffecient

Answer 5

  

en utilisant my_id de recherche « arbre 2 » a réellement besoin de rechercher n2 comme une étape intermédiaire

pas vrai . Un dictionnaire est un Hashtable: elle transforme le hachage d'un élément à (un seau) d'entrées. Lorsque vous demandez d[my_id], Python obtient d'abord hash(my_id) et regarde alors que dans d. Vous se confondre parce que vous avez cette hash(n1) == hash(id1), ce qui est une très mauvaise chose.

Vous demandez une correspondance entre des identificateurs et des noeuds. Si vous voulez un de ces derniers, vous devrez créer un vous-même.

---

sont les identifiants tous jumelés à des noeuds lors de la création, ou avez-vous les construire plus tard? C'est, vous vraiment demandez à être en mesure de trouver le noeud avec identifiant identifier({'name':'Alex'}), ou cet identifiant a déjà été créé et ajouté à un noeud? Dans ce dernier cas, vous pouvez faire ce qui suit:

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