Odwrotne przeszukiwanie słownika w Pythonie

Czy istnieje prosty sposób na znalezienie klucza poprzez znajomość wartości w słowniku?

Myślę tylko o tym:

key = [key for key, value in dict_obj.items() if value == 'value'][0]

Nie ma żadnego. Nie zapominaj, że wartość można znaleźć na dowolnej liczbie kluczy, w tym 0 lub więcej niż 1.

Twoja lista składa się z wszystkich elementów dykta, znajdując wszystkie dopasowania, a następnie zwraca pierwszy klucz. To wyrażenie generatora będzie iterować tylko tak daleko, jak to konieczne, aby zwrócić pierwszą wartość:

key = next(key for key, value in dd.items() if value == 'value')

gdzie ddjest dyktando. Podniesie, StopIterationjeśli nie zostanie znalezione dopasowanie, więc możesz chcieć to złapać i zwrócić bardziej odpowiedni wyjątek, taki jak ValueErrorlub KeyError.

Są przypadki, w których słownik jest jeden: jedno mapowanie

Na przykład,

d = {1: "one", 2: "two" ...}

Twoje podejście jest w porządku, jeśli wykonujesz tylko jedno wyszukiwanie. Jeśli jednak potrzebujesz wykonać więcej niż jedno wyszukiwanie, skuteczniejsze będzie utworzenie słownika odwrotnego

ivd = {v: k for k, v in d.items()}

Jeśli istnieje możliwość, że wiele kluczy ma tę samą wartość, w tym przypadku należy określić żądane zachowanie.

Jeśli Twój Python jest w wersji 2.6 lub starszej, możesz użyć

ivd = dict((v, k) for k, v in d.items())

Ta wersja jest o 26% krótsza od twojej, ale działa identycznie, nawet dla zbędnych / niejednoznacznych wartości (zwraca pierwsze dopasowanie, tak jak twoja). Jest jednak prawdopodobnie dwa razy wolniejszy niż twój, ponieważ dwukrotnie tworzy listę na podstawie dyktowania.

key = dict_obj.keys()[dict_obj.values().index(value)]

Lub jeśli wolisz zwięzłość niż czytelność, możesz zapisać jeszcze jedną postać

key = list(dict_obj)[dict_obj.values().index(value)]

A jeśli wolisz wydajność, podejście @ PaulMcGuire jest lepsze. Jeśli istnieje wiele kluczy, które mają tę samą wartość, bardziej efektywne jest nie tworzenie instancji tej listy kluczy ze zrozumieniem listy i zamiast tego użyć generatora:

key = (key for key, value in dict_obj.items() if value == 'value').next()

Ponieważ jest to nadal bardzo istotne, pierwsze trafienie Google i spędziłem trochę czasu na zastanowieniu się nad tym, opublikuję moje rozwiązanie (działające w Pythonie 3):

testdict = {'one'   : '1',
            'two'   : '2',
            'three' : '3',
            'four'  : '4'
            }

value = '2'

[key for key in testdict.items() if key[1] == value][0][0]

Out[1]: 'two'

Otrzymasz pierwszą pasującą wartość.

Może chcesz uzyskać klasę podobną do słownika, taką jak DoubleDictponiżej? Możesz użyć dowolnej z dostarczonych metaklas w połączeniu z DoubleDictdowolną metaklasą lub możesz w ogóle jej uniknąć.

import functools
import threading

################################################################################

class _DDChecker(type):

    def __new__(cls, name, bases, classdict):
        for key, value in classdict.items():
            if key not in {'__new__', '__slots__', '_DoubleDict__dict_view'}:
                classdict[key] = cls._wrap(value)
        return super().__new__(cls, name, bases, classdict)

    @staticmethod
    def _wrap(function):
        @functools.wraps(function)
        def check(self, *args, **kwargs):
            value = function(self, *args, **kwargs)
            if self._DoubleDict__forward != \
               dict(map(reversed, self._DoubleDict__reverse.items())):
                raise RuntimeError('Forward & Reverse are not equivalent!')
            return value
        return check

################################################################################

class _DDAtomic(_DDChecker):

    def __new__(cls, name, bases, classdict):
        if not bases:
            classdict['__slots__'] += ('_DDAtomic__mutex',)
            classdict['__new__'] = cls._atomic_new
        return super().__new__(cls, name, bases, classdict)

    @staticmethod
    def _atomic_new(cls, iterable=(), **pairs):
        instance = object.__new__(cls, iterable, **pairs)
        instance.__mutex = threading.RLock()
        instance.clear()
        return instance

    @staticmethod
    def _wrap(function):
        @functools.wraps(function)
        def atomic(self, *args, **kwargs):
            with self.__mutex:
                return function(self, *args, **kwargs)
        return atomic

################################################################################

class _DDAtomicChecker(_DDAtomic):

    @staticmethod
    def _wrap(function):
        return _DDAtomic._wrap(_DDChecker._wrap(function))

################################################################################

class DoubleDict(metaclass=_DDAtomicChecker):

    __slots__ = '__forward', '__reverse'

    def __new__(cls, iterable=(), **pairs):
        instance = super().__new__(cls, iterable, **pairs)
        instance.clear()
        return instance

    def __init__(self, iterable=(), **pairs):
        self.update(iterable, **pairs)

    ########################################################################

    def __repr__(self):
        return repr(self.__forward)

    def __lt__(self, other):
        return self.__forward < other

    def __le__(self, other):
        return self.__forward <= other

    def __eq__(self, other):
        return self.__forward == other

    def __ne__(self, other):
        return self.__forward != other

    def __gt__(self, other):
        return self.__forward > other

    def __ge__(self, other):
        return self.__forward >= other

    def __len__(self):
        return len(self.__forward)

    def __getitem__(self, key):
        if key in self:
            return self.__forward[key]
        return self.__missing_key(key)

    def __setitem__(self, key, value):
        if self.in_values(value):
            del self[self.get_key(value)]
        self.__set_key_value(key, value)
        return value

    def __delitem__(self, key):
        self.pop(key)

    def __iter__(self):
        return iter(self.__forward)

    def __contains__(self, key):
        return key in self.__forward

    ########################################################################

    def clear(self):
        self.__forward = {}
        self.__reverse = {}

    def copy(self):
        return self.__class__(self.items())

    def del_value(self, value):
        self.pop_key(value)

    def get(self, key, default=None):
        return self[key] if key in self else default

    def get_key(self, value):
        if self.in_values(value):
            return self.__reverse[value]
        return self.__missing_value(value)

    def get_key_default(self, value, default=None):
        return self.get_key(value) if self.in_values(value) else default

    def in_values(self, value):
        return value in self.__reverse

    def items(self):
        return self.__dict_view('items', ((key, self[key]) for key in self))

    def iter_values(self):
        return iter(self.__reverse)

    def keys(self):
        return self.__dict_view('keys', self.__forward)

    def pop(self, key, *default):
        if len(default) > 1:
            raise TypeError('too many arguments')
        if key in self:
            value = self[key]
            self.__del_key_value(key, value)
            return value
        if default:
            return default[0]
        raise KeyError(key)

    def pop_key(self, value, *default):
        if len(default) > 1:
            raise TypeError('too many arguments')
        if self.in_values(value):
            key = self.get_key(value)
            self.__del_key_value(key, value)
            return key
        if default:
            return default[0]
        raise KeyError(value)

    def popitem(self):
        try:
            key = next(iter(self))
        except StopIteration:
            raise KeyError('popitem(): dictionary is empty')
        return key, self.pop(key)

    def set_key(self, value, key):
        if key in self:
            self.del_value(self[key])
        self.__set_key_value(key, value)
        return key

    def setdefault(self, key, default=None):
        if key not in self:
            self[key] = default
        return self[key]

    def setdefault_key(self, value, default=None):
        if not self.in_values(value):
            self.set_key(value, default)
        return self.get_key(value)

    def update(self, iterable=(), **pairs):
        for key, value in (((key, iterable[key]) for key in iterable.keys())
                           if hasattr(iterable, 'keys') else iterable):
            self[key] = value
        for key, value in pairs.items():
            self[key] = value

    def values(self):
        return self.__dict_view('values', self.__reverse)

    ########################################################################

    def __missing_key(self, key):
        if hasattr(self.__class__, '__missing__'):
            return self.__missing__(key)
        if not hasattr(self, 'default_factory') \
           or self.default_factory is None:
            raise KeyError(key)
        return self.__setitem__(key, self.default_factory())

    def __missing_value(self, value):
        if hasattr(self.__class__, '__missing_value__'):
            return self.__missing_value__(value)
        if not hasattr(self, 'default_key_factory') \
           or self.default_key_factory is None:
            raise KeyError(value)
        return self.set_key(value, self.default_key_factory())

    def __set_key_value(self, key, value):
        self.__forward[key] = value
        self.__reverse[value] = key

    def __del_key_value(self, key, value):
        del self.__forward[key]
        del self.__reverse[value]

    ########################################################################

    class __dict_view(frozenset):

        __slots__ = '__name'

        def __new__(cls, name, iterable=()):
            instance = super().__new__(cls, iterable)
            instance.__name = name
            return instance

        def __repr__(self):
            return 'dict_{}({})'.format(self.__name, list(self))

Nie, nie można tego skutecznie zrobić bez zaglądania do wszystkich kluczy i sprawdzania wszystkich ich wartości. Będziesz więc potrzebował O(n)czasu, aby to zrobić. Jeśli potrzebujesz wykonać wiele takich wyszukiwań, będziesz musiał to zrobić efektywnie, konstruując odwrócony słownik (można to również zrobić w O(n)), a następnie przeszukując ten odwrócony słownik (każde wyszukiwanie zajmie średnio O(1)).

Oto przykład, jak skonstruować odwrócony słownik (który będzie w stanie wykonać jedno do wielu mapowań) ze zwykłego słownika:

for i in h_normal:
    for j in h_normal[i]:
        if j not in h_reversed:
            h_reversed[j] = set([i])
        else:
            h_reversed[j].add(i)

Na przykład, jeśli twój

h_normal = {
  1: set([3]), 
  2: set([5, 7]), 
  3: set([]), 
  4: set([7]), 
  5: set([1, 4]), 
  6: set([1, 7]), 
  7: set([1]), 
  8: set([2, 5, 6])
}

twoja h_reversedwola

{
  1: set([5, 6, 7]),
  2: set([8]), 
  3: set([1]), 
  4: set([5]), 
  5: set([8, 2]), 
  6: set([8]), 
  7: set([2, 4, 6])
}

O ile mi wiadomo, nie ma takiego, jednak jednym ze sposobów jest utworzenie dyktu do normalnego wyszukiwania według klucza, a drugim do wyszukiwania wstecznego według wartości.

Oto przykład takiej implementacji:

http://code.activestate.com/recipes/415903-two-dict-classes-which-can-lookup-keys-by-value-an/

Oznacza to, że wyszukiwanie kluczy pod kątem wartości może skutkować wieloma wynikami, które można zwrócić jako prostą listę.

Wiem, że można to uznać za `` marnotrawstwo '', ale w tym scenariuszu często przechowuję klucz jako dodatkową kolumnę w rekordzie wartości:

d = {'key1' : ('key1', val, val...), 'key2' : ('key2', val, val...) }

jest to kompromis i wydaje się zły, ale jest prosty i działa i oczywiście zależy od wartości będących krotkami, a nie prostymi wartościami.

Stwórz słownik zwrotny

reverse_dictionary = {v:k for k,v in dictionary.items()} 

Jeśli masz dużo do zrobienia odwrotnego wyszukiwania

Wartości w słowniku mogą być obiektami dowolnego rodzaju, których nie można haszować ani indeksować w inny sposób. Zatem znajdowanie klucza według wartości jest nienaturalne dla tego typu kolekcji. Każde takie zapytanie może zostać wykonane tylko w czasie O (n). Więc jeśli jest to częste zadanie, powinieneś spojrzeć na indeksowanie klucza, takiego jak Jon Sujjested, a może nawet indeks przestrzenny (DB lub http://pypi.python.org/pypi/Rtree/ ).

Używam słowników jako pewnego rodzaju „bazy danych”, więc muszę znaleźć klucz, którego będę mógł ponownie użyć. W moim przypadku, jeśli wartość klucza to None, mogę go wziąć i ponownie użyć bez konieczności „przydzielania” innego identyfikatora. Pomyślałem, że się tym podzielę.

db = {0:[], 1:[], ..., 5:None, 11:None, 19:[], ...}

keys_to_reallocate = [None]
allocate.extend(i for i in db.iterkeys() if db[i] is None)
free_id = keys_to_reallocate[-1]

Podoba mi się ten, ponieważ nie muszę próbować wyłapywać żadnych błędów, takich jak StopIterationlub IndexError. Jeśli jest dostępny klucz, free_idbędzie go zawierał. Jeśli nie, to po prostu będzie None. Prawdopodobnie nie pythoniczne, ale naprawdę nie chciałem trytutaj używać ...