Wie implementiere ich eine effiziente bidirektionale Hash-Tabelle?

82

Python dictist eine sehr nützliche Datenstruktur:

d = {'a': 1, 'b': 2}

d['a'] # get 1

Manchmal möchten Sie auch nach Werten indizieren.

d[1] # get 'a'

Welches ist der effizienteste Weg, um diese Datenstruktur zu implementieren? Gibt es eine offizielle Empfehlung?

Juanjo Conti
quelle
Wenn Sie es vorziehen, können wir davon ausgehen, dass sowohl Werte als auch Schlüssel unveränderlich sind.
Juanjo Conti
3
Was würden Sie für dieses Diktat zurückgeben: {'a': 1, 'b': 2, 'A': 1}
PaulMcG
2
@ PaulMcGuire: Ich würde wiederkommen {1: ['a', 'A'], 2: 'b'}. Siehe meine Antwort für eine solche Vorgehensweise.
Basj
4
Hinweis für den Moderator: Dies ist kein Duplikat von stackoverflow.com/questions/1456373/two-way-reverse-map . Letzteres hat 1) einen sehr vagen Wortlaut 2) kein MCVE 3) befasst sich nur mit dem Fall der bijektiven Karte (siehe ersten Kommentar in dieser Frage), die viel restriktiver ist als diese eigentliche Frage, die allgemeiner ist. Daher denke ich, dass es in diesem speziellen Fall irreführend ist, es als Duplikat zu markieren. Wenn wirklich eines ein Duplikat eines anderen sein sollte, sollte es das Gegenteil sein, da dieses hier den allgemeinen Fall abdeckt, während das andere (siehe Antworten) den nicht-bijektiven Fall nicht abdeckt.
Basj

Antworten:

65

Hier ist eine Klasse für eine bidirektionale Klasse dict, die von Finding key from value im Python-Wörterbuch inspiriert und so geändert wurde, dass die folgenden 2) und 3) zulässig sind.

Beachten Sie, dass :

  • 1) Das inverse Verzeichnis bd.inverse aktualisiert sich automatisch, wenn das Standard-Diktat bdgeändert wird.
  • 2) Das inverse Verzeichnis bd.inverse[value] ist immer eine Liste von keysolchen bd[key] == value.
  • 3) Im Gegensatz zum bidictModul von https://pypi.python.org/pypi/bidict können hier zwei Schlüssel mit demselben Wert verwendet werden. Dies ist sehr wichtig .

Code:

class bidict(dict):
    def __init__(self, *args, **kwargs):
        super(bidict, self).__init__(*args, **kwargs)
        self.inverse = {}
        for key, value in self.items():
            self.inverse.setdefault(value,[]).append(key) 

    def __setitem__(self, key, value):
        if key in self:
            self.inverse[self[key]].remove(key) 
        super(bidict, self).__setitem__(key, value)
        self.inverse.setdefault(value,[]).append(key)        

    def __delitem__(self, key):
        self.inverse.setdefault(self[key],[]).remove(key)
        if self[key] in self.inverse and not self.inverse[self[key]]: 
            del self.inverse[self[key]]
        super(bidict, self).__delitem__(key)

Anwendungsbeispiel:

bd = bidict({'a': 1, 'b': 2})  
print(bd)                     # {'a': 1, 'b': 2}                 
print(bd.inverse)             # {1: ['a'], 2: ['b']}
bd['c'] = 1                   # Now two keys have the same value (= 1)
print(bd)                     # {'a': 1, 'c': 1, 'b': 2}
print(bd.inverse)             # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print(bd)                     # {'a': 1, 'b': 2}
print(bd.inverse)             # {1: ['a'], 2: ['b']}
del bd['a']
print(bd)                     # {'b': 2}
print(bd.inverse)             # {2: ['b']}
bd['b'] = 3
print(bd)                     # {'b': 3}
print(bd.inverse)             # {2: [], 3: ['b']}
Basj
quelle
2
Sehr ordentliche Lösung des mehrdeutigen Falles!
Tobias Kienzler
2
Ich denke, diese Datenstruktur ist bei vielen praktischen Problemen sehr nützlich.
0xc0de
5
Das ist phänomenal. Es ist prägnant; es ist selbstdokumentierend; es ist ziemlich effizient; es funktioniert einfach. Mein einziges Problem wäre, die wiederholten Suchvorgänge von self[key]in __delitem__()mit einer einzigen value = self[key]Aufgabe zu optimieren, die für solche Suchvorgänge wiederverwendet wird. Aber ... ja. Das ist vernachlässigbar. Danke für das pure Genial , Basj !
Cecil Curry
1
Wie wäre es mit einer Python 3-Version?
Zelusp
1
Ich mag diese Antwort für das Beispiel. Die akzeptierte Antwort ist immer noch korrekt und ich denke, die akzeptierte Antwort sollte als akzeptierte Antwort bleiben, aber dies ist etwas expliziter, um sie selbst zu definieren, nur weil klar festgelegt ist, dass Sie die Umkehrung platzieren müssen, um das Wörterbuch umzukehren Werte in eine Liste aufnehmen, da es keine Eins-zu-Eins-Zuordnung geben kann, da ein Wörterbuch eine Eins-zu-Viele-Beziehung zu Schlüssel-zu-Werten hat.
Searchengine27
41

Sie können dasselbe Diktat selbst verwenden, indem Sie das Schlüssel-Wert-Paar in umgekehrter Reihenfolge hinzufügen.

d = {'a': 1, 'b': 2}
revd = dict ([umgekehrt (i) für i in d.items ()])
d.update (revd)
Emil
quelle
5
+1 Eine schöne, praktische Lösung. Eine andere Art, es zu schreiben : d.update( dict((d[k], k) for k in d) ).
FMc
4
+1 Für den sauberen Gebrauch von umgekehrt (). Ich bin unentschlossen, ob es besser lesbar ist als das explizite dict((v, k) for (k, v) in d.items()). In jedem Fall können Sie Paare direkt an .update übergeben : d.update(reversed(i) for i in d.items()).
Beni Cherniavsky-Paskin
22
Beachten Sie, dass dies zB fürd={'a':1, 'b':2, 1: 'b'}
Tobias Kienzler
3
Leichte Änderung : dict(map(reversed, a_dict.items())).
0xc0de
13
Das Hinzufügen von umgekehrten Zuordnungen zum ursprünglichen Wörterbuch ist eine schreckliche Idee. Wie die obigen Kommentare zeigen, ist dies im allgemeinen Fall nicht sicher. Pflegen Sie einfach zwei separate Wörterbücher. Da die ersten beiden Zeilen dieser Antwort, in denen das Nachlaufen ignoriert d.update(revd)wird, großartig sind, denke ich immer noch über eine positive Abstimmung nach. Lassen Sie uns darüber nachdenken.
Cecil Curry
34

Die bidirektionale Hash-Tabelle eines armen Mannes würde darin bestehen, nur zwei Wörterbücher zu verwenden (dies sind bereits hochgradig abgestimmte Datenstrukturen).

Es gibt auch ein Bidict- Paket im Index:

Die Quelle für Bidict finden Sie auf Github:

miku
quelle
1
2 Diktate erfordern doppelte Einfügungen und Löschungen.
Juanjo Conti
12
@Juanjo: Fast jede bidirektionale / reversible Hash-Tabelle beinhaltet "doppelte Einfügungen und Löschungen", entweder als Teil der Implementierung der Struktur oder als Teil ihrer Verwendung. Das Beibehalten von zwei Indizes ist wirklich der einzig schnelle Weg, AFAIK.
Walter Mundt
7
Natürlich; Ich meinte, dass es das Problem ist, den 2-Index von Hand zu pflegen.
Juanjo Conti
1
@Basj Ich denke, es ist richtig, dass es nicht akzeptiert wird, da mehr als ein Wert bedeutet, dass es keine Bijektion mehr ist und für die umgekehrte Suche nicht eindeutig ist.
user193130
1
@Basj Nun, ich kann verstehen, dass es Anwendungsfälle geben würde, die nützlich wären, wenn mehr als ein Wert pro Schlüssel vorhanden wäre. Daher sollte diese Art von Datenstruktur möglicherweise als Unterklasse von Bidict existieren. Da ein normales Diktat jedoch einem einzelnen Objekt zugeordnet ist, ist es meiner Meinung nach viel sinnvoller, auch das Gegenteil zu tun. (Nur um zu verdeutlichen, obwohl der Wert auch eine Sammlung sein kann, meinte ich, dass der Schlüssel des ersten Diktats vom gleichen Typ sein sollte wie der Wert des umgekehrten Diktats)
user193130
3

Der folgende Codeausschnitt implementiert eine invertierbare (bijektive) Karte:

class BijectionError(Exception):
    """Must set a unique value in a BijectiveMap."""

    def __init__(self, value):
        self.value = value
        msg = 'The value "{}" is already in the mapping.'
        super().__init__(msg.format(value))


class BijectiveMap(dict):
    """Invertible map."""

    def __init__(self, inverse=None):
        if inverse is None:
            inverse = self.__class__(inverse=self)
        self.inverse = inverse

    def __setitem__(self, key, value):
        if value in self.inverse:
            raise BijectionError(value)

        self.inverse._set_item(value, key)
        self._set_item(key, value)

    def __delitem__(self, key):
        self.inverse._del_item(self[key])
        self._del_item(key)

    def _del_item(self, key):
        super().__delitem__(key)

    def _set_item(self, key, value):
        super().__setitem__(key, value)

Der Vorteil dieser Implementierung ist, dass das inverseAttribut von a BijectiveMapwieder a ist BijectiveMap. Daher können Sie Dinge tun wie:

>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True
jme
quelle
1

So etwas vielleicht:

import itertools

class BidirDict(dict):
    def __init__(self, iterable=(), **kwargs):
        self.update(iterable, **kwargs)
    def update(self, iterable=(), **kwargs):
        if hasattr(iterable, 'iteritems'):
            iterable = iterable.iteritems()
        for (key, value) in itertools.chain(iterable, kwargs.iteritems()):
            self[key] = value
    def __setitem__(self, key, value):
        if key in self:
            del self[key]
        if value in self:
            del self[value]
        dict.__setitem__(self, key, value)
        dict.__setitem__(self, value, key)
    def __delitem__(self, key):
        value = self[key]
        dict.__delitem__(self, key)
        dict.__delitem__(self, value)
    def __repr__(self):
        return '%s(%s)' % (type(self).__name__, dict.__repr__(self))

Sie müssen entscheiden, was passieren soll, wenn mehr als ein Schlüssel einen bestimmten Wert hat. Die Bidirektionalität eines bestimmten Paares kann leicht durch ein späteres Paar, das Sie eingefügt haben, beeinträchtigt werden. Ich habe eine mögliche Wahl getroffen.


Beispiel:

bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1']   # a
print bd['myvalue2']   # b        
Matt Anderson
quelle
1
Ich bin nicht sicher, ob dies ein Problem ist, aber würde es bei Verwendung der obigen Implementierung keine Probleme geben, wenn sich die Schlüssel und Werte überschneiden? Also dict([('a', 'b'), ('b', 'c')]); dict['b']-> 'c'statt des Schlüssels 'a'.
Tgray
1
Es ist kein Problem für das Beispiel des OP, könnte aber ein guter Haftungsausschluss sein.
Tgray
Wie können wir diese print bd['myvalue2']Antworten b, c(oder [b, c]oder (b, c)oder irgendetwas anderes) tun ?
Basj
0

Zunächst müssen Sie sicherstellen, dass der Schlüssel für die Wertzuordnung eins zu eins ist. Andernfalls ist es nicht möglich, eine bidirektionale Zuordnung zu erstellen.

Zweitens, wie groß ist der Datensatz? Wenn nicht viele Daten vorhanden sind, verwenden Sie einfach zwei separate Karten und aktualisieren Sie beide beim Aktualisieren. Oder verwenden Sie besser eine vorhandene Lösung wie Bidict , bei der es sich nur um einen Wrapper aus 2 Dicts handelt , in die Aktualisierung / Löschung integriert ist.

Wenn der Datensatz jedoch groß ist und die Aufrechterhaltung von 2 Diktaten nicht wünschenswert ist:

  • Wenn sowohl Schlüssel als auch Wert numerisch sind, sollten Sie die Möglichkeit in Betracht ziehen, die Zuordnung mithilfe der Interpolation zu approximieren. Wenn die überwiegende Mehrheit der Schlüssel-Wert-Paare von der Zuordnungsfunktion (und ihrer
    Umkehrfunktion) abgedeckt werden kann, müssen Sie nur die Ausreißer in Zuordnungen aufzeichnen.

  • Wenn der größte Teil des Zugriffs unidirektional ist (Schlüssel-> Wert), ist es völlig in Ordnung, die umgekehrte Karte schrittweise zu erstellen, um Zeit gegen
    Raum zu tauschen.

Code:

d = {1: "one", 2: "two" }
reverse = {}

def get_key_by_value(v):
    if v not in reverse:
        for _k, _v in d.items():
           if _v == v:
               reverse[_v] = _k
               break
    return reverse[v]
NeoWang
quelle
0

Leider bidictfunktioniert die am höchsten bewertete Antwort nicht.

Es gibt drei Möglichkeiten:

  1. Unterklassen-Diktat : Sie können eine Unterklasse von erstellen dict, aber Vorsicht. Sie müssen benutzerdefinierte Implementierungen von schreiben update, pop, initializer, setdefault. Die dictImplementierungen rufen nicht auf __setitem__. Aus diesem Grund weist die am höchsten bewertete Antwort Probleme auf.

  2. Von UserDict erben : Dies ist wie ein Diktat, außer dass alle Routinen korrekt aufgerufen werden. Es verwendet ein Diktat unter der Haube in einem Gegenstand namens data. Sie können die Python-Dokumentation lesen oder eine einfache Implementierung einer Richtungsliste verwenden, die in Python 3 funktioniert . Es tut mir leid, dass ich es nicht wörtlich aufgenommen habe: Ich bin mir nicht sicher, ob es urheberrechtlich geschützt ist.

  3. Von abstrakten Basisklassen erben: Durch das Erben von collection.abc erhalten Sie alle korrekten Protokolle und Implementierungen für eine neue Klasse. Dies ist ein Overkill für ein bidirektionales Wörterbuch, es sei denn, es kann auch eine Datenbank verschlüsseln und zwischenspeichern.

TL; DR - Verwenden Sie dies für Ihren Code. Lesen Sie den Artikel von Trey Hunner für Details.

Charles Merriam
quelle