Wie implementiert man eine effiziente bidirektionale Hash-Tabelle?

Python dict ist 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 dafür?

Hier ist eine Klasse für eine bidirektionale dictinspiriert von Finding key from value in Python dictionary und modifiziert, um die folgenden 2) und 3) zu ermöglichen.

Beachten Sie, dass :

• 1) Die umgekehrtes Verzeichnis bd.inverse aktualisiert sich automatisch, wenn das Standard-dict bd wird modifiziert.
• 2) Die umgekehrtes Verzeichnis bd.inverse[value] ist immer ein aufführen von key so dass bd[key] == value.
• 3) Anders als die bidict Modul ab https://pypi.python.org/pypi/bidicthier können wir 2 Schlüssel mit demselben Wert haben, das 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 ein Schlüssel-Wert-Paar in umgekehrter Reihenfolge hinzufügen.

d={'a':1,'b':2}
revd=dict([reversed(i) for 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).

Da ist auch ein Gebot Paket auf dem Index:

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

Die Quelle für bidict finden Sie auf github:

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

Das folgende Code-Snippet 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 besteht darin, dass die inverse Attribut von a BijectiveMap ist wieder ein 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

Leider ist die am besten bewertete Antwort, bidict funktioniert nicht.

Es gibt drei Möglichkeiten:

1. Unterklasse Diktat: Sie können eine Unterklasse von erstellen dict, aber Vorsicht. Sie müssen benutzerdefinierte Implementierungen von schreibenupdate, pop, initializer, setdefault. Der dict Implementierungen rufen nicht auf __setitem__. Aus diesem Grund hat die am besten bewertete Antwort Probleme.

2. Von UserDict erben: Dies ist genau wie ein Diktat, außer dass alle Routinen korrekt aufgerufen werden. Es verwendet ein Diktat unter der Haube, in einem Element namens data. Sie können die lesen Python-Dokumentationoder Verwenden Sie eine einfache Implementierung einer Richtungsliste, die in Python 3 funktioniert. Entschuldigung, dass ich es nicht wörtlich aufgenommen habe: Ich bin mir nicht sicher, ob es sich um ein Urheberrecht handelt.

3. Von abstrakten Basisklassen erben: Erben von Sammlungen.abc hilft Ihnen, alle richtigen Protokolle und Implementierungen für eine neue Klasse zu erhalten. Dies ist für ein bidirektionales Wörterbuch übertrieben, es sei denn, es kann auch verschlüsseln und in einer Datenbank zwischenspeichern.

TL;DR – Verwenden Dies für deinen Code. Lesen Sie Trey Hunners Artikel für Details.

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 könnte leicht durch ein später eingefügtes Paar beeinträchtigt werden. Ich habe eine mögliche Auswahl implementiert.

Beispiel :

bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1']   # a
print bd['myvalue2']   # b        

Zunächst müssen Sie sicherstellen, dass die Schlüssel-zu-Wert-Zuordnung 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 2 separate Karten und aktualisieren Sie beide beim Aktualisieren. Oder besser, verwenden Sie eine vorhandene Lösung wie Gebotdas nur ein Wrapper von 2 Diktaten ist, mit eingebauter Aktualisierung/Löschung.

Aber wenn der Datensatz groß ist und die Pflege von 2 Diktaten nicht wünschenswert ist:

• Wenn sowohl der Schlüssel als auch der Wert numerisch sind, ziehen Sie die Möglichkeit in Betracht, Interpolation zu verwenden, um die Zuordnung zu approximieren. Wenn die überwiegende Mehrheit der Schlüssel-Wert-Paare von der Zuordnungsfunktion (und ihrer
  Reverse-Funktion), dann brauchen Sie nur noch die Ausreißer in Karten aufzeichnen.

• Wenn der größte Teil des Zugriffs unidirektional ist (Schlüssel-> Wert), ist es völlig in Ordnung, die umgekehrte Karte inkrementell zu erstellen, um Zeit dafür einzutauschen
  Platz.

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]