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

86

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ć?

Juanjo Conti
źródło
Jeśli wolisz, możemy założyć, że wartości są niezmienne, podobnie jak klucze.
Juanjo Conti
4
Co byś oddał za ten dykt: {'a': 1, 'b': 2, 'A': 1}
PaulMcG
2
@PaulMcGuire: Wróciłbym {1: ['a', 'A'], 2: 'b'}. Zobacz moją odpowiedź, jak to zrobić.
Basj
4
Uwaga dla moderatora: to nie jest duplikat strony stackoverflow.com/questions/1456373/two-way-reverse-map . To ostatnie ma 1) bardzo niejasne sformułowanie 2) brak MCVE 3) zajmuje się tylko przypadkiem mapy bijektywnej (patrz pierwszy komentarz do tego pytania), która jest dużo bardziej restrykcyjna niż to rzeczywiste pytanie, które jest bardziej ogólne. Myślę więc, że oznaczenie tego jako duplikatu jest tutaj, w tym konkretnym przypadku, mylące. Jeśli naprawdę jeden powinien być duplikatem innego, powinno być odwrotnie, ponieważ ten tutaj obejmuje przypadek ogólny, podczas gdy drugi (patrz odpowiedzi) nie obejmuje przypadku nieobiektywnego.
Basj

Odpowiedzi:

67

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']}
Basj
źródło
2
Bardzo zgrabne rozwiązanie niejednoznacznej sprawy!
Tobias Kienzler,
2
Myślę, że ta struktura danych jest bardzo przydatna w wielu praktycznych problemach.
0xc0de
6
To jest fenomenalne. Jest zwięzły; to samodokumentacja; jest dość wydajny; po prostu działa. Moim jedynym zastrzeżeniem byłoby zoptymalizowanie powtarzanych wyszukiwań self[key]w __delitem__()za pomocą pojedynczego value = self[key]przypisania ponownie używanego do takich wyszukiwań. Ale ... tak. To nieistotne. Dzięki za niesamowite, Basj !
Cecil Curry
1
A co z wersją Pythona 3?
zelusp
1
Podoba mi się ta odpowiedź na przykład. Zaakceptowana odpowiedź jest nadal poprawna i myślę, że zaakceptowana odpowiedź powinna pozostać jako zaakceptowana odpowiedź, ale jest to trochę bardziej wyraźne, jeśli chodzi o jej samodzielne zdefiniowanie, tylko dlatego, że wyraźnie stwierdza, że ​​aby zmienić słownik, należy umieścić wartości do listy, ponieważ nie może istnieć mapowanie jeden do jednego, ponieważ słownik ma relację jeden do wielu z kluczami do wartości.
Searchengine
41

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)
Emil
źródło
5
+1 Ładne, praktyczne rozwiązanie. Innym sposobem, aby napisać: d.update( dict((d[k], k) for k in d) ).
FMc
4
+1 Do zgrabnego użycia reverse (). Nie jestem zdecydowany, czy jest to bardziej czytelne niż wyraźne dict((v, k) for (k, v) in d.items()). W każdym razie, można przejść bezpośrednio do .update par: d.update(reversed(i) for i in d.items()).
Beni Cherniavsky-Paskin
22
Zauważ, że to się nie udaje, np.d={'a':1, 'b':2, 1: 'b'}
Tobias Kienzler
3
Nieznaczne zmiany: dict(map(reversed, a_dict.items())).
0xc0de
13
Dodawanie odwrotnych mapowań do oryginalnego słownika to okropny pomysł. Jak pokazują powyższe uwagi, nie jest to bezpieczne w ogólnym przypadku. Po prostu utrzymuj dwa oddzielne słowniki. Ponieważ pierwsze dwie linijki tej odpowiedzi ignorujące końcowe d.update(revd)są świetne, jednak nadal rozważam głosowanie za. Pomyślmy o tym.
Cecil Curry
36

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 :

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

miku
źródło
1
2 dykty wymagają podwójnego wstawiania i usuwania.
Juanjo Conti
12
@Juanjo: prawie każda dwukierunkowa / odwracalna tablica mieszająca będzie obejmować „podwójne wstawianie i usuwanie”, albo jako część implementacji struktury, albo jako część jej używania. Utrzymanie dwóch indeksów to naprawdę jedyny szybki sposób, aby to zrobić, AFAIK.
Walter Mundt
7
Oczywiście; Chodziło mi o to, że ręczne zajęcie się indeksem 2 jest problemem.
Juanjo Conti
1
@Basj Myślę, że to poprawne, że nie jest akceptowane, ponieważ posiadanie więcej niż jednej wartości oznacza, że ​​nie jest już bijection i jest niejednoznaczne dla wyszukiwania wstecznego.
user193130
1
@Basj Cóż, rozumiem, że byłyby przypadki użycia, które przydałyby się, aby mieć więcej niż jedną wartość na klucz, więc może ten typ struktury danych powinien istnieć jako podklasa bidict. Jednakże, ponieważ normalne dyktowanie jest mapowane na pojedynczy obiekt, myślę, że bardziej sensowne jest, aby strona odwrotna była również taka sama. (Dla wyjaśnienia, chociaż wartość może być również zbiorem, miałem na myśli, że klucz pierwszego dyktu powinien być tego samego typu, co wartość odwróconego dict)
user193130
4

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
jme
źródło
2

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.

Charles Merriam
źródło
1

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        
Matt Anderson
źródło
1
Nie jestem pewien, czy jest to problem, ale używając powyższej implementacji, czy nie byłoby problemów, gdyby klucze i wartości nakładały się? Więc dict([('a', 'b'), ('b', 'c')]); dict['b']-> 'c'zamiast klucza 'a'.
tgray
1
Nie stanowi to problemu dla przykładu PO, ale może być dobrym zastrzeżeniem do uwzględnienia.
tgray
Jak możemy print bd['myvalue2']odpowiedzieć na to pytanie b, c( [b, c]albo (b, c), albo cokolwiek innego)?
Basj
0

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]
NeoWang
źródło