Wie implementiere ich eine effiziente bidirektionale Hash-Tabelle?

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?

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

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)

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:

• https://pypi.python.org/pypi/bidict

Die Quelle für Bidict finden Sie auf Github:

• https://github.com/jab/bidict

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

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        

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]

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.