Pesquisa inversa de dicionário em Python

Existe alguma maneira simples de encontrar uma chave sabendo o valor em um dicionário?

Só consigo pensar no seguinte:

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

Não há nenhum. Não se esqueça de que o valor pode ser encontrado em qualquer número de chaves, incluindo 0 ou mais de 1.

A compreensão de sua lista passa por todos os itens do dicionário, encontrando todas as correspondências e, em seguida, retorna apenas a primeira chave. Esta expressão geradora irá iterar apenas o necessário para retornar o primeiro valor:

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

onde ddestá o dict. Irá aumentar StopIterationse nenhuma correspondência for encontrada, então você pode querer capturar isso e retornar uma exceção mais apropriada como ValueErrorou KeyError.

Existem casos em que um dicionário é um: um mapeamento

Por exemplo,

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

Sua abordagem está ok se você estiver fazendo apenas uma única pesquisa. No entanto, se você precisar fazer mais de uma pesquisa, será mais eficiente criar um dicionário inverso

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

Se houver a possibilidade de várias chaves com o mesmo valor, você precisará especificar o comportamento desejado neste caso.

Se seu Python for 2.6 ou mais antigo, você pode usar

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

Esta versão é 26% mais curta que a sua, mas funciona de forma idêntica, mesmo para valores redundantes / ambíguos (retorna a primeira correspondência, como a sua). No entanto, é provavelmente duas vezes mais lento que o seu, porque cria uma lista do dict duas vezes.

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

Ou se você preferir brevidade em vez de legibilidade, você pode salvar mais um caractere com

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

E se você preferir eficiência, a abordagem de @PaulMcGuire é melhor. Se houver muitas chaves que compartilham o mesmo valor, é mais eficiente não instanciar essa lista de chaves com uma compreensão de lista e, em vez disso, usar um gerador:

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

Como isso ainda é muito relevante, o primeiro hit do Google e eu acabei de passar algum tempo tentando descobrir isso, postarei minha solução (trabalhando em Python 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'

Ele fornecerá o primeiro valor correspondente.

Talvez uma aula semelhante a um dicionário, como DoubleDicta seguir, seja o que você deseja? Você pode usar qualquer uma das metaclasses fornecidas em conjunto com DoubleDictou pode evitar o uso de qualquer metaclasse.

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

Não, você não pode fazer isso de forma eficiente sem olhar em todas as chaves e verificar todos os seus valores. Portanto, você precisará de O(n)tempo para fazer isso. Se você precisar fazer muitas dessas pesquisas, precisará fazer isso de forma eficiente, construindo um dicionário invertido (também pode ser feito em O(n)) e, em seguida, fazendo uma pesquisa dentro desse dicionário invertido (cada pesquisa levará uma média O(1)).

Aqui está um exemplo de como construir um dicionário invertido (que será capaz de fazer um para muitos mapeamentos) a partir de um dicionário normal:

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)

Por exemplo, se o seu

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

sua h_reversedvontade será

{
  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])
}

Não há um que eu saiba, mas uma maneira de fazer isso é criar um dict para pesquisa normal por chave e outro dict para pesquisa reversa por valor.

Há um exemplo de tal implementação aqui:

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

Isso significa que procurar as chaves por um valor pode resultar em vários resultados que podem ser retornados como uma lista simples.

Sei que isso pode ser considerado 'desperdício', mas, neste cenário, geralmente armazeno a chave como uma coluna adicional no registro de valor:

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

é uma troca e parece errado, mas é simples e funciona e, claro, depende de valores serem tuplas em vez de valores simples.

Faça um dicionário reverso

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

Se você tiver muitas pesquisas reversas para fazer

Por meio de valores no dicionário, podem ser objetos de qualquer tipo, eles não podem ser hash ou indexados de outra maneira. Portanto, encontrar a chave pelo valor não é natural para este tipo de coleção. Qualquer consulta como essa pode ser executada apenas em tempo O (n). Portanto, se esta é uma tarefa frequente, você deve procurar alguma indexação de chave como Jon sujjested ou talvez até algum índice espacial (DB ou http://pypi.python.org/pypi/Rtree/ ).

Estou usando dicionários como uma espécie de "banco de dados", então preciso encontrar uma chave que possa reutilizar. No meu caso, se o valor de uma chave for None, posso pegá-la e reutilizá-la sem ter que "alocar" outro id. Só pensei em compartilhar.

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]

Gosto deste porque não tenho de tentar detectar erros como StopIterationou IndexError. Se houver uma chave disponível, então free_idconterá uma. Se não houver, simplesmente será None. Provavelmente não é pythônico, mas eu realmente não queria usar um tryaqui ...