Gibt es eine bessere Möglichkeit, ein zweiseitiges Wörterbuch zu speichern, als seine inverse separate zu speichern?

Question

eine Eins-zu-Eins-Wörterbuch Given (= Bijektion) erzeugt à la

for key, value in someGenerator: 
    myDict[key] = value 

eine inverse Lookup-Wörterbuch kann durch Zugabe von

invDict[value] = key 

zum for Schleife trivially erstellt werden. Aber ist das ein pythonischer Weg? Soll ich stattdessen eine class Bijection(dict) schreiben, die dieses invertierte Wörterbuch zusätzlich verwaltet und eine zweite Lookup-Funktion bereitstellt? Oder existiert eine solche Struktur (oder eine ähnliche) bereits?

Answer 1

Was ich in der Vergangenheit getan habe, ist eine reversedict-Funktion, die ein dict und Rückgabe der umgekehrten Zuordnung, entweder Werte zu Schlüsseln, wenn ich wusste, dass es eins zu eins war (werfen Ausnahmen beim Sehen der gleichen) erstellt Wert zweimal) oder Werte zu Schlüssellisten, wenn dies nicht der Fall war. Auf diese Weise konnte ich, anstatt jedes Mal, wenn ich die umgekehrte Suche machen wollte, zwei Dicts gleichzeitig konstruieren, meine Dicts als normal erzeugen und einfach die generische reversedict Funktion am Ende aufrufen.

Es scheint jedoch, dass die bidict Lösung, die Jon in den Kommentaren erwähnt, wahrscheinlich die bessere ist. (Meine reversedict Funktion scheint sein Bidict ~ Operator zu sein).

Answer 2

Wenn Sie O (log (n)) Zeit für den Zugriff auf Werte benötigen, benötigen Sie sowohl eine Darstellung der Karte als auch eine Darstellung der inversen Karte.

Ansonsten ist das Beste, was Sie tun können, O (log (n)) in der einen Richtung und O (n) in der anderen Richtung.

Edit: nicht O (log (n)), danke Claudiu, aber Sie werden immer noch zwei Datenstrukturen benötigen, um die Schnellzugriffszeiten zu implementieren. Und dies wird mehr oder weniger der gleiche Raum sein wie ein Diktat und ein umgekehrtes Diktat.