dizionario Inverse ricerca in Python

Question

C'è un modo semplice di trovare una chiave conoscendo il valore all'interno di un dizionario?

Tutto quello che posso pensare è questo:

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

Answer 1

Non v'è nessuno. Non dimenticare che il valore può essere trovato su qualsiasi numero di chiavi, incluso 0 o più di 1.

Answer 2

Non ce n'è uno per quanto ne so, un modo per farlo è creare un ditt per normale ricerca per chiave e un'altra dict per ricerca inversa per valore.

C'è un esempio di tale applicazione qui:

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

Questo significa che guardando le chiavi per un valore potrebbe risultare in molteplici risultati che possono essere restituiti come un semplice elenco.

Answer 3

Attraverso valori nel dizionario può essere oggetto di qualsiasi tipo non possono essere hashing o indicizzato altro modo. Quindi trovare la chiave in base al valore è innaturale per questo tipo di raccolta. Qualsiasi query del genere può essere eseguita solo nel tempo O (n). Quindi, se questo è il compito frequente si dovrebbe dare uno sguardo per alcuni l'indicizzazione di chiave come Jon sujjested o forse anche un po 'di indice spaziale (DB o http://pypi.python.org/pypi/Rtree/).

Answer 4

ci sono casi in cui un dizionario è uno:

esempio una mappatura,

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

Il tuo approccio è ok se si sta solo facendo una sola ricerca. Tuttavia, se avete bisogno di fare più di una ricerca sarà più efficace per creare un dizionario inversa

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

Se c'è una possibilità di più chiavi con lo stesso valore, sarà necessario specificare il comportamento desiderato in questo Astuccio.

Se il Python è 2.6 o precedente, è possibile utilizzare

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

Answer 5

Il tuo elenco di comprensione passa attraverso tutti gli elementi del dict trovare tutte le partite, poi basta restituisce la prima chiave. Questa espressione generatore iterare solo quanto necessario per restituire il primo valore:

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

dove dd è il dict. Solleverà StopIteration se non viene trovata alcuna corrispondenza, quindi potrebbe essere utile rilevarla e restituire un'eccezione più appropriata come ValueError o KeyError.

Answer 6

So che questo potrebbe essere considerato 'spreco', ma in questo scenario che spesso memorizzare la chiave come una colonna aggiuntiva nel record del valore:

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

si tratta di un compromesso e si sente male, ma è semplice e funziona e, naturalmente, dipende dal fatto che i valori siano tuple piuttosto che valori semplici.

Answer 7

Forse una classe simile a un dizionario come DoubleDict in basso è ciò che desideri?È possibile utilizzare uno qualsiasi dei metaclassi forniti in combinazione con DoubleDict o evitare di utilizzare qualsiasi 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)) 

Answer 8

Questa versione è il 26% più corta yours ma funziona esattamente, anche per valori ridondanti/ambiguo (restituisce la prima corrispondenza, come vostro fa). Tuttavia, probabilmente è due volte più lento del tuo, perché crea una lista dal ditt due volte.

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

O se preferite brevità sopra la leggibilità è possibile salvare più di un carattere con

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

E se si preferisce l'efficienza, @approach di PaulMcGuire è meglio. Se ci sono un sacco di chiavi che condividono lo stesso valore è più efficiente di non istanziare quella lista di chiavi con una lista di comprensione e di utilizzare invece utilizzare un generatore:

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

Answer 9

key in dict.values() 

Questo è letteralmente

Answer 10

No, non puoi farlo in modo efficiente senza guardare tutte le chiavi e controllare tutti i loro valori. Quindi avrai bisogno del tempo di O(n) per farlo. Se è necessario eseguire molte ricerche di questo tipo, è necessario farlo in modo efficiente costruendo un dizionario invertito (può essere fatto anche in O(n)) e quindi effettuare una ricerca all'interno di questo dizionario invertito (ciascuna ricerca richiederà in media O(1)).

Ecco un esempio di come costruire un dizionario invertita (che sarà in grado di fare uno a molti mappatura) da un dizionario normale:

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) 

Ad esempio se il vostro

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

il tuo h_reversed sarà

{ 
    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

Poiché questo è ancora molto rilevante, il primo Google ha colpito e ho appena passare un po 'di tempo per capire questo fuori, vi posterò la mia (che lavorano in Python 3) Soluzione:

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' 

che vi darà il primo valore che corrisponde.

Answer 12

Sto usando i dizionari come una sorta di "database", quindi ho bisogno di trovare una chiave che possa riutilizzare. Per il mio caso, se il valore di una chiave è None, allora posso prenderlo e riutilizzarlo senza dover "allocare" un altro id. Ho pensato di condividerlo.

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] 

Mi piace questo perché non ho per cercare di catturare eventuali errori quali StopIteration o IndexError. Se è disponibile una chiave, allora free_id ne conterrà una. Se non c'è, allora sarà semplicemente None. Probabilmente non pythonic, ma non volevo davvero usare uno try qui ...

Answer 13

Come valore potrebbe essere inesistente in dict, un codice più divinatorio e auto-documentato sarebbe:

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. 

Infatti dicts non sono fatti per rispondere a tali problematiche, se si verifica questo problema su un nuovo programma progettato, quindi dovresti probabilmente rivedere il tuo design.