Búsqueda de diccionario inversa en Python

Question

¿Hay alguna manera directa de encontrar una clave conociendo el valor dentro de un diccionario?

Todo lo que puedo pensar es la siguiente:

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

Answer 1

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

Answer 2

No hay ninguno que yo sepa, pero una forma de hacerlo es crear un dict para búsqueda normal por clave y otra dict para búsqueda inversa por valor.

Hay un ejemplo de este tipo de implementación aquí:

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

Esto quiere decir que busca las llaves para un valor podría dar lugar a varios resultados que pueden ser devueltos como una simple lista.

Answer 3

Los valores en el diccionario pueden ser objeto de cualquier tipo, no se pueden codificar ni indexar de otra manera. Así que encontrar clave por el valor no es natural para este tipo de colección. Cualquier consulta como esa se puede ejecutar solo en el tiempo O (n). Entonces, si esta es una tarea frecuente, debería buscar alguna indexación de clave como Jon sujjested o incluso algún índice espacial (DB o http://pypi.python.org/pypi/Rtree/).

Answer 4

Hay casos en los que un diccionario es un uno:

por ejemplo, un mapeo,

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

Su enfoque está bien si sólo se está haciendo una búsqueda única. Sin embargo, si lo que necesita hacer más de una consulta de que será más eficiente para crear un diccionario inverso

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

Si hay una posibilidad de múltiples teclas con el mismo valor, se necesita especificar el comportamiento deseado en este caso.

Si el pitón es de 2,6 o más, puede utilizar

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

Answer 5

Su lista por comprensión pasa a través de todos los elementos de la dict encontrar todos los partidos, a continuación, sólo devuelve la primera clave. Esta expresión generador solamente se repetirá la medida de lo necesario devolver el primer valor:

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

donde dd es el dict. Aumentará StopIteration si no se encuentra una coincidencia, por lo que es posible que desee detectarlo y devolver una excepción más apropiada como ValueError o KeyError.

Answer 6

Sé que esto puede ser considerado 'despilfarro', pero en este escenario a menudo almacenar la clave como una columna adicional en el registro de valor:

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

Es un compromiso y se siente mal, pero es simple y funciona y, por supuesto, depende de que los valores sean tuplas en lugar de valores simples.

Answer 7

Tal vez una clase similar a un diccionario como DoubleDict abajo es lo que quieres?Puede usar cualquiera de las metaclases provistas en conjunción con DoubleDict o puede evitar el uso de 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)) 

Answer 8

Esta versión es 26% más corta que yours pero funciona de forma idéntica, incluso para valores redundantes/ambiguas (devuelve el primer partido, como hace la suya). Sin embargo, es probablemente el doble de lento que el tuyo, porque crea una lista del dict dos veces.

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

O si lo prefiere la brevedad sobre la legibilidad puede guardar un personaje más con

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

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

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

Answer 9

key in dict.values() 

Esto es, literalmente, se

Answer 10

No, no puedes hacer esto de manera eficiente sin mirar todas las teclas y verificar todos sus valores. Por lo tanto, necesitará O(n) para hacerlo. 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 de O(1)).

Aquí es un ejemplo de cómo construir un diccionario invertido (que será capaz de hacer uno a muchos mapeo) 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 su

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

su h_reversed habrá

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

Answer 11

Dado que este es todavía muy relevante, Google el primer golpe y acabo de pasar algún tiempo calcular esto, voy a publicar mi (trabajando en Python 3) Solución:

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' 

que le dará el primer valor que coincida.

Answer 12

Estoy usando diccionarios como una especie de "base de datos", así que necesito encontrar una clave que pueda volver a utilizar. Para mi caso, si el valor de una clave es None, entonces puedo tomarlo y reutilizarlo sin tener que "asignar" otra identificación. Pensé que lo compartiría.

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 para tratar de detectar cualquier error o como StopIterationIndexError. Si hay una clave disponible, entonces free_id contendrá una. Si no hay, entonces simplemente será None. Probablemente no sea pitónico, pero realmente no quería usar un try aquí ...

Answer 13

Como valor podría ser inexistente en dict, un código más Pythonic y auto-documentado sería:

a # Value to search against 
x = None # Searched key 
for k, v in d.items(): 
    if v == a: 
     x = k 
     break 
x # Now contains the key or None if not found. 

De hecho dicts no están hechos para responder a estas problemáticas, si se encuentra con este problema en un nuevo programa diseñado, entonces probablemente debería revisar su diseño.