In Python, wie kann man einen Schlüssel aus einem Wörterbuch abrufen?

Question

Ich habe eine hashable Kennung für die Dinge in einem Wörterbuch setzen:

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

Ich habe einen Knotentyp, dass Verkapselungen für die Zwecke des Hashing und Gleichheit identifer:

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

Ich habe ein paar Knoten in ein Wörterbuch:

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'

Einige Zeit später habe ich nur noch eine Kennung:

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

Gibt es einen Weg, um den Knoten Nachschlag, die mit dieser Kennung in diesem Wörterbuch gespeichert ist?

Bitte beachten Sie, dass dies ein wenig schwieriger ist, als es klingt; Ich weiß, dass ich d[my_id] trivialer Weise die zugehörigen Artikel 'Node 2' abrufen können, aber Ich möchte effizient einen Verweis zurück zur n2 .

Ich weiß, dass ich es durch einen Blick auf jedes Element in d tun könnte, aber ich habe versucht, und es ist viel zu langsam (das Wörterbuch Tausende von Artikeln in ihm hat, und ich tue dies eine angemessene Anzahl von Malen).

Ich weiß, dass intern dict wird mit den hash und eq Betreiber für diese Kennung zu speichern Knoten n2 und die dazugehörigen Artikel, 'Node 2'. In der Tat, my_id mit Nachschlag 'Node 2' muss tatsächlich n2 als Zwischenschritt Nachschlag, so sollte dies auf jeden Fall möglich sein.

Ich verwende diese Daten in einem Graphen zu speichern. Die Knoten haben eine Menge zusätzlicher Daten (wo ich setzte value), die nicht in der Hash verwendet wird. Ich erschufen die Grafik-Paket Ich verwende (NetworkX), aber ich kann das Wörterbuch sehen, dass speichert meine Knoten. Ich könnte auch ein zusätzliches Wörterbuch halten um von Identifikatoren zu Knoten, aber dies wäre ein Schmerz (ich würde müssen Sie die Grafik-Klasse wickeln und neu schreiben alle Add-Knoten, Knoten entfernen, fügen Sie Knoten aus der Liste, entfernen Sie Knoten aus der Liste, fügen Rand usw. Typ Funktionen, die Wörterbuch zu dem Laufenden halten).

Das ist ziemlich das Rätsel. Jede Hilfe wäre wirklich dankbar!

Answer 1

Anstelle von

d[n1] = 'Node 1'

Verwendung:

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

Dann haben Sie Zugriff auf n1 unabhängig davon, wie Sie den Wert gefunden.

Ich glaube nicht, gibt es eine Möglichkeit mit Wörterbücher den Originalschlüssel k1 abrufen, wenn alles, was Sie haben, ist ein k2 k1 gleich.

Answer 2

Haben Sie zwei Wörterbücher.  -. Jedes Mal, wenn Sie einen Schlüssel / Wert auf die Primär Wörterbuch hinzuzufügen, auch sie auf der Rückseite Wörterbuch hinzuzufügen, aber mit dem Schlüssel / Wert vertauscht

Zum Beispiel:

# 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

Dies ist eine Möglichkeit, einen benutzerdefinierten Knoten Objekt mit NetworkX zu verwenden. Wenn Sie speichern das Objekt im „Knotenattribut“ Wörterbuch Sie können es als Reverse-Lexikon nutzen das bekommen Objekt durch Bezugnahme auf die ID zurück. Es ist ein wenig umständlich aber es funktioniert.

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

Sie können natürlich auch eine Funktion definieren, die diese einfacher macht:

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

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

Answer 4

Die Sache ist, gibt es keine Garantie, dass der Schlüssel tatsächlich ein Knoten ist. Was passiert, wenn Sie tun

d[my_id]=d[my_id] 

Alles wäre noch perfekt ausnehmen arbeiten jetzt, Ihr Schlüssel ist ein Identifier und kein Knoten. So dass zwei Klassen „gleich“ wie das ist wirklich gefährlich. Wenn Sie wirklich brauchen einen Knoten durch seinen Namen zu finden, die in der Klasse Node oder externaly getan werden sollen, sollten aber nicht abhängig von der Anwesenheit von nicht des Knotens in einem Hash.

Wenn Sie diese nicht ändern können (weil Sie den Code nicht ändern können), dann ich denke, Sie sind fest, die Art und Weise effizient ist

zu tun

Answer 5

  

Verwenden my_id zum Nachschlagen ‚Node 2‘ muss eigentlich als Zwischenschritt zum Nachschlagen n2

Dies ist nicht wahr . Ein Wörterbuch ist eine Hash-Tabelle: es bildet den Hash eines Elements (ein Eimer) Einträge. Wenn Sie sich für d[my_id] fragen, bekommt Python ersten hash(my_id) und sieht dann, dass bis in d. Sie sind immer verwirrt, weil Sie, dass hash(n1) == hash(id1) haben, die eine sehr schlechte Sache ist.

Sie fordern eine Zuordnung zwischen Identifikatoren und Knoten. Wenn Sie eine dieser wollen, müssen Sie selbst eine Beurteilung erstellen.

---

Sind die Identifikatoren alle mit Knoten bei der Erstellung angepasst, oder Sie bauen sie später? Das heißt, Sie wirklich fragen Sie den Knoten mit der Kennung identifier({'name':'Alex'}) finden zu können, oder hat die Kennung bereits zu einem Knoten erstellt und hinzugefügt? Wenn letzteres, könnten Sie Folgendes tun:

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