Jak zaimplementować wydajną dwukierunkową tablicę skrótów?

Python dictto bardzo przydatna struktura danych:

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

d['a'] # get 1

Czasami chcesz również indeksować według wartości.

d[1] # get 'a'

Jaki jest najbardziej efektywny sposób implementacji tej struktury danych? Jakiś oficjalny sposób, aby to zrobić?

Oto klasa dla dwukierunkowego dict, zainspirowana szukaniem klucza z wartości w słowniku Pythona i zmodyfikowana, aby umożliwić następujące 2) i 3).

Zauważ, że:

• 1) Odwrotny katalog bd.inverse aktualizuje się automatycznie po bdzmodyfikowaniu standardowego dyktowania .
• 2) katalog odwrotna bd.inverse[value] jest zawsze lista z keytakimi, które bd[key] == value.
• 3) W przeciwieństwie do bidictmodułu z https://pypi.python.org/pypi/bidict , tutaj możemy mieć 2 klucze o tej samej wartości, jest to bardzo ważne .

Kod:

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)

Przykład użycia:

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

Możesz użyć tego samego dyktu, dodając parę klucz, wartość w odwrotnej kolejności.

d = {'a': 1, 'b': 2}
revd = dict ([odwrócony (i) for i in d.items ()])
d.update (revd)

Dwukierunkowa tablica mieszająca biedaka polegałaby na wykorzystaniu tylko dwóch słowników (są to już wysoce dostrojone struktury danych).

W indeksie znajduje się również pakiet ofert :

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

Źródło bidict można znaleźć na github:

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

Poniższy fragment kodu implementuje odwracalną (bijective) mapę:

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)

Zaletą tej implementacji jest to, że inverseatrybut a BijectiveMapjest ponownie a BijectiveMap. Dlatego możesz robić takie rzeczy, jak:

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

Niestety najwyżej oceniona odpowiedź bidictnie działa.

Istnieją trzy opcje:

1. Dykt podklasy : Możesz utworzyć podklasę dict, ale uważaj. Musisz napisać niestandardowe implementacje update, pop, initializer, setdefault. W dictimplementacje nie nazywają __setitem__. Dlatego najwyżej oceniana odpowiedź zawiera problemy.

2. Dziedzicz po UserDict : To jest jak dict, z wyjątkiem tego, że wszystkie procedury są wywoływane poprawnie. Używa dyktu pod maską, w elemencie o nazwie data. Możesz przeczytać dokumentację Pythona lub użyć prostej implementacji listy kierunkowej, która działa w Pythonie 3 . Przepraszamy za nieuwzględnienie tego słowa dosłownie: nie jestem pewien co do jego praw autorskich.

3. Dziedzicz z abstrakcyjnych klas bazowych : Dziedziczenie z collections.abc pomoże Ci uzyskać wszystkie prawidłowe protokoły i implementacje dla nowej klasy. Jest to przesada w przypadku słownika dwukierunkowego, chyba że może on również szyfrować i buforować w bazie danych.

TL; DR - użyj tego dla swojego kodu. Przeczytaj Trey Hunnera jest artykuł o szczegóły.

Może coś takiego:

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))

Musisz zdecydować, co chcesz zrobić, jeśli więcej niż jeden klucz ma daną wartość; Dwukierunkowość danej pary może być łatwo przebita przez jakąś później wstawioną parę. Zaimplementowałem jeden możliwy wybór.

Przykład:

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

Po pierwsze, musisz upewnić się, że kluczem do mapowania wartości jest jeden do jednego, w przeciwnym razie nie jest możliwe zbudowanie mapy dwukierunkowej.

Po drugie, jak duży jest zbiór danych? Jeśli danych jest mało, po prostu użyj 2 oddzielnych map i zaktualizuj obie podczas aktualizacji. Albo lepiej, użyj istniejącego rozwiązania, takiego jak Bidict , które jest tylko opakowaniem 2 dykt z wbudowaną aktualizacją / usuwaniem.

Ale jeśli zbiór danych jest duży i utrzymywanie 2 dykt nie jest pożądane:

• Jeśli zarówno klucz, jak i wartość są liczbami, rozważ możliwość użycia interpolacji w celu przybliżenia mapowania. Jeśli zdecydowana większość par klucz-wartość może być objęta funkcją mapowania (i jej
  funkcją odwrotną), wystarczy zarejestrować wartości odstające na mapach.

• Jeśli większość dostępu jest jednokierunkowa (klucz-> wartość), to jest całkowicie w porządku, aby budować odwrotną mapę stopniowo, aby wymienić czas na
  przestrzeń.

Kod:

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]