Búsqueda de diccionario inverso en Python

¿Existe alguna forma sencilla de encontrar una clave conociendo el valor dentro de un diccionario?

Todo lo que puedo pensar es esto:

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

No hay ninguno. No olvide que el valor se puede encontrar en cualquier número de claves, incluido 0 o más de 1.

La comprensión de su lista pasa por todos los elementos del dict encontrando todas las coincidencias, luego solo devuelve la primera clave. Esta expresión generadora solo iterará tanto como sea necesario para devolver el primer valor:

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

donde ddesta el dict. Aumentará StopIterationsi no se encuentra ninguna coincidencia, por lo que es posible que desee detectar eso y devolver una excepción más apropiada como ValueErroro KeyError.

Hay casos en los que un diccionario es uno: un mapeo

P.ej,

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

Su enfoque está bien si solo está haciendo una única búsqueda. Sin embargo, si necesita hacer más de una búsqueda, será más eficiente crear un diccionario inverso.

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

Si existe la posibilidad de varias claves con el mismo valor, deberá especificar el comportamiento deseado en este caso.

Si su Python es 2.6 o anterior, puede usar

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

Esta versión es un 26% más corta que la suya, pero funciona de manera idéntica, incluso para valores redundantes / ambiguos (devuelve la primera coincidencia, como la suya). Sin embargo, probablemente sea dos veces más lento que el suyo, porque crea una lista a partir del dict dos veces.

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

O si prefiere la brevedad a la legibilidad, puede guardar un carácter más con

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

Y si prefiere la eficiencia, el enfoque de @ PaulMcGuire es mejor. Si hay muchas claves que comparten el mismo valor, es más eficiente no crear una instancia de esa lista de claves con una lista de comprensión y, en su lugar, usar un generador:

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

Dado que esto sigue siendo muy relevante, el primer éxito de Google y solo dedico un tiempo a resolver esto, publicaré mi solución (trabajando en 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'

Le dará el primer valor que coincida.

¿Quizás una clase similar a un diccionario como la que se DoubleDictmuestra a continuación es lo que desea? Puede usar cualquiera de las metaclases proporcionadas junto con DoubleDicto puede evitar usar cualquier metaclase en absoluto.

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

No, no puede hacer esto de manera eficiente sin mirar todas las claves y verificar todos sus valores. Entonces necesitará O(n)tiempo para hacer esto. Si necesita hacer muchas de estas búsquedas, deberá hacerlo de manera eficiente construyendo un diccionario invertido (también se puede hacer en O(n)) y luego haciendo una búsqueda dentro de este diccionario invertido (cada búsqueda tomará un promedio O(1)).

A continuación se muestra un ejemplo de cómo construir un diccionario inverso (que podrá hacer una asignación de uno a varios) a partir de un diccionario 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 ejemplo, si tu

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

tu h_reversedserá

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

No hay uno que yo sepa, sin embargo, una forma de hacerlo es crear un dictado para la búsqueda normal por clave y otro dictado para la búsqueda inversa por valor.

Hay un ejemplo de tal implementación aquí:

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

Esto significa que buscar las claves para un valor podría dar como resultado múltiples resultados que se pueden devolver como una lista simple.

Sé que esto podría considerarse un 'desperdicio', pero en este escenario, a menudo guardo la clave como una columna adicional en el registro de valor:

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

es una compensación y se siente mal, pero es simple y funciona y, por supuesto, depende de que los valores sean tuplas en lugar de valores simples.

Hacer un diccionario inverso

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

Si tiene muchas búsquedas inversas que hacer

Los valores en el diccionario pueden ser objetos de cualquier tipo y no pueden ser indexados o indexados de otra manera. Por lo tanto, encontrar la clave por el valor no es natural para este tipo de colección. Cualquier consulta como esa se puede ejecutar solo en tiempo O (n). Entonces, si esta es una tarea frecuente, debe buscar alguna indexación de clave como Jon sujjested o tal vez incluso algún índice espacial (DB o http://pypi.python.org/pypi/Rtree/ ).

Estoy usando diccionarios como una especie de "base de datos", así que necesito encontrar una clave que pueda reutilizar. En mi caso, si el valor de una clave es None, entonces puedo tomarla y reutilizarla sin tener que "asignar" otra identificación. Solo pensé en compartirlo.

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]

Me gusta este porque no tengo que intentar detectar ningún error como StopIterationoIndexError . Si hay una clave disponible, free_idcontendrá una. Si no lo hay, simplemente lo será None. Probablemente no sea pitónico, pero realmente no quería usar un tryaquí ...