Recherche inversée de dictionnaire en Python

Existe-t-il un moyen simple de trouver une clé en connaissant la valeur dans un dictionnaire?

Tout ce que je peux penser, c'est ceci:

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

Il n'y en a pas. N'oubliez pas que la valeur peut être trouvée sur n'importe quel nombre de clés, y compris 0 ou plus de 1.

Votre compréhension de liste passe par tous les éléments du dict pour trouver toutes les correspondances, puis renvoie simplement la première clé. Cette expression de générateur n'itérera que dans la mesure nécessaire pour renvoyer la première valeur:

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

où ddest le dict. Sera déclenché StopIterationsi aucune correspondance n'est trouvée, vous voudrez peut-être l'attraper et renvoyer une exception plus appropriée comme ValueErrorou KeyError.

Il y a des cas où un dictionnaire est un: un mappage

Par exemple,

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

Votre approche est correcte si vous ne faites qu'une seule recherche. Cependant, si vous devez faire plus d'une recherche, il sera plus efficace de créer un dictionnaire inverse

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

S'il existe une possibilité de plusieurs clés avec la même valeur, vous devrez spécifier le comportement souhaité dans ce cas.

Si votre Python est 2.6 ou plus ancien, vous pouvez utiliser

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

Cette version est 26% plus courte que la vôtre mais fonctionne de manière identique, même pour les valeurs redondantes / ambiguës (renvoie la première correspondance, comme la vôtre). Cependant, il est probablement deux fois plus lent que le vôtre, car il crée deux fois une liste à partir du dict.

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

Ou si vous préférez la brièveté à la lisibilité, vous pouvez enregistrer un caractère supplémentaire avec

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

Et si vous préférez l'efficacité, l' approche de @ PaulMcGuire est meilleure. S'il y a beaucoup de clés qui partagent la même valeur, il est plus efficace de ne pas instancier cette liste de clés avec une compréhension de liste et d'utiliser à la place un générateur:

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

Comme cela est toujours très pertinent, le premier succès de Google et je passe juste un peu de temps à le comprendre, je posterai ma solution (travaillant 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'

Cela vous donnera la première valeur qui correspond.

Peut-être qu'une classe semblable à un dictionnaire comme DoubleDictci-dessous est ce que vous voulez? Vous pouvez utiliser l'une des métaclasses fournies en conjonction avec DoubleDictou éviter d'utiliser une métaclasse du tout.

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

Non, vous ne pouvez pas le faire efficacement sans chercher dans toutes les clés et vérifier toutes leurs valeurs. Vous aurez donc besoin de O(n)temps pour le faire. Si vous avez besoin de faire beaucoup de telles recherches, vous devrez le faire efficacement en construisant un dictionnaire inversé (peut être fait également dans O(n)) et en effectuant une recherche à l'intérieur de ce dictionnaire inversé (chaque recherche prendra en moyenne O(1)).

Voici un exemple de la façon de construire un dictionnaire inversé (qui pourra faire un à plusieurs mappages) à partir d'un dictionnaire 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)

Par exemple si votre

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_reversedseras

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

À ma connaissance, il n'y en a pas, une façon de le faire est de créer un dict pour la recherche normale par clé et un autre dict pour la recherche inversée par valeur.

Il y a un exemple d'une telle implémentation ici:

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

Cela signifie que la recherche des clés pour une valeur peut entraîner plusieurs résultats qui peuvent être renvoyés sous forme de liste simple.

Je sais que cela peut être considéré comme un `` gaspillage '', mais dans ce scénario, je stocke souvent la clé en tant que colonne supplémentaire dans l'enregistrement de valeur:

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

c'est un compromis et se sent mal, mais c'est simple et fonctionne et dépend bien sûr du fait que les valeurs sont des tuples plutôt que de simples valeurs.

Faire un dictionnaire inversé

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

Si vous avez beaucoup de recherches inversées à faire

Grâce aux valeurs dans le dictionnaire peuvent être des objets de toute sorte, elles ne peuvent pas être hachées ou indexées d'une autre manière. Donc, trouver la clé par la valeur n'est pas naturel pour ce type de collection. Toute requête comme celle-ci ne peut être exécutée qu'en temps O (n). Donc, si c'est une tâche fréquente, vous devriez jeter un œil pour une indexation de clé comme Jon sujjested ou peut-être même un index spatial (DB ou http://pypi.python.org/pypi/Rtree/ ).

J'utilise des dictionnaires comme une sorte de "base de données", je dois donc trouver une clé que je peux réutiliser. Dans mon cas, si la valeur d'une clé est None, alors je peux la prendre et la réutiliser sans avoir à "allouer" un autre identifiant. Je pensais juste que je le partagerais.

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]

J'aime celui-ci parce que je n'ai pas à essayer de détecter des erreurs telles que StopIterationou IndexError. Si une clé est disponible, elle free_iden contiendra une. S'il n'y en a pas, ce sera simplement le cas None. Probablement pas pythonique, mais je ne voulais vraiment pas utiliser un tryici ...