En Python, ¿cómo se puede recuperar una clave de un diccionario?

Question

Tengo un identificador hashable para poner las cosas en un diccionario:

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

Tengo un tipo de nodo que encapsula identificador para fines de hash y la igualdad:

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

Pongo algunos nodos en un diccionario:

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'

Un tiempo después, sólo tengo un identificador:

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

¿Hay alguna manera de las operaciones de búsqueda de manera eficiente el nodo que se ha almacenado con este identificador en este diccionario?

Tenga en cuenta que este es un poco más difícil de lo que parece; Sé que puedo usar trivialmente d[my_id] para recuperar el 'Node 2' elemento asociado, pero Quiero volver eficaz una referencia a n2 .

Yo sé que podría hacerlo examinado todos los elementos de d, pero lo he intentado y es demasiado lento (el diccionario tiene miles de artículos en ella y hago esto un buen número de veces).

Yo sé que dict internamente está utilizando los operadores hash y eq para ese identificador para n2 el nodo de almacén y su elemento asociado, 'Node 2'. De hecho, el uso de my_id para buscar 'Node 2' realmente necesita para buscar n2 como un paso intermedio, por lo que esta debe ser definitivamente posible.

Estoy usando esto para almacenar datos en un gráfico. Los nodos tienen una gran cantidad de datos adicional (donde pongo value) que no se utiliza en el hash. Yo no he creado el paquete gráfico que estoy usando (NetworkX), pero puedo ver el diccionario que almacena mis nodos. También podría mantener un diccionario adicional alrededor de los identificadores a los nodos, pero esto sería un dolor (que iba a necesitar para envolver la clase gráfica y volver a escribir toda la adición de nodos, el nodo eliminar, añadir nodos de la lista de nodos, eliminar de la lista, agregar bordes , etc. funciones de tipo para mantener ese diccionario al día).

Esto es bastante rompecabezas. Cualquier ayuda sería muy apreciada!

Answer 1

En lugar de

d[n1] = 'Node 1'

uso:

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

A continuación, se tiene acceso a n1 no importa cómo se encuentra el valor.

No creo que hay una manera de diccionarios para recuperar la clave k1 original si todo lo que tienes es un k2 son iguales a k1.

Answer 2

Tiene dos diccionarios.  -. Cada vez que se agrega una clave / valor al diccionario principal, también agregarlos al diccionario inverso, pero con la clave / valor intercambiado

Por ejemplo:

# 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

Esta es una manera de utilizar un objeto nodo personalizado con NetworkX. Si almacena el objeto en el diccionario "nodo de atributo" se puede usar como un diccionario inverso para obtener la volver a objetos haciendo referencia a la ID. Es un poco incómodo pero 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'}

Se puede definir, por supuesto, una función que hace que este simple:

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

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

Answer 4

La cosa es que no hay ninguna garantía de que la clave es efectivamente un nodo. ¿Y si lo hace

d[my_id]=d[my_id] 

Todo sería todavía funcionan perfectamente excepto que ahora, su clave es un identificador y no un nodo. Permitiendo dos clases de "iguales" como este es realmente peligroso. Si realmente necesita para encontrar un nodo por su nombre que se debe hacer en la clase de nodo o externaly, pero no debe depender de la presencia de no del nodo en un hash.

Si no puede modificar ese (porque no se puede modificar el código), entonces supongo que está pegado a hacer el camino ineficiente

Answer 5

  

Uso my_id a las operaciones de búsqueda 'Nodo 2' realmente necesita para buscar n2 como un paso intermedio

Este es no es verdad . Un diccionario es una tabla hash: se asigna el hash de un elemento para (un cubo de entradas). Cuando pide d[my_id], Python primero se hash(my_id) y luego se ve que en d. Usted se está confundiendo porque tienes que hash(n1) == hash(id1), que es una cosa muy mala.

Se solicita una asignación entre los identificadores y los nodos. Si quieres uno de estos, tendrá que crear una.

---

¿Son los identificadores de todos los emparejados con los nodos sobre la creación, o no se construyen más tarde? Es decir, estás realmente pidiendo que sea capaz de encontrar el nodo con identificador identifier({'name':'Alex'}), o tiene que ya identificador sido creado y añadido a un nodo? En este último caso, se puede hacer lo siguiente:

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