Python dict
to 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ć?
python
hashtable
bidirectional
Juanjo Conti
źródło
źródło
{1: ['a', 'A'], 2: 'b'}
. Zobacz moją odpowiedź, jak to zrobić.Odpowiedzi:
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:
bd.inverse
aktualizuje się automatycznie pobd
zmodyfikowaniu standardowego dyktowania .bd.inverse[value]
jest zawsze lista zkey
takimi, którebd[key] == value
.bidict
moduł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']}
źródło
self[key]
w__delitem__()
za pomocą pojedynczegovalue = self[key]
przypisania ponownie używanego do takich wyszukiwań. Ale ... tak. To nieistotne. Dzięki za niesamowite, Basj !Możesz użyć tego samego dyktu, dodając parę klucz, wartość w odwrotnej kolejności.
źródło
d.update( dict((d[k], k) for k in d) )
.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())
.d={'a':1, 'b':2, 1: 'b'}
dict(map(reversed, a_dict.items()))
.d.update(revd)
są świetne, jednak nadal rozważam głosowanie za. Pomyślmy o tym.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:
źródło
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
inverse
atrybut aBijectiveMap
jest ponownie aBijectiveMap
. 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
źródło
Niestety najwyżej oceniona odpowiedź
bidict
nie działa.Istnieją trzy opcje:
Dykt podklasy : Możesz utworzyć podklasę
dict
, ale uważaj. Musisz napisać niestandardowe implementacjeupdate
,pop
,initializer
,setdefault
. Wdict
implementacje nie nazywają__setitem__
. Dlatego najwyżej oceniana odpowiedź zawiera problemy.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.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.
źródło
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
źródło
dict([('a', 'b'), ('b', 'c')]); dict['b']
->'c'
zamiast klucza'a'
.print bd['myvalue2']
odpowiedzieć na to pytanieb, c
([b, c]
albo(b, c)
, albo cokolwiek innego)?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]
źródło