Обратный поиск в словаре в Python

Есть ли простой способ найти ключ, зная значение в словаре?

Все, о чем я могу думать, это следующее:

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

Здесь ничего нет. Не забывайте, что значение может быть найдено на любом количестве ключей, включая 0 или более 1.

Ваше понимание списка просматривает все элементы dict, находя все совпадения, а затем просто возвращает первый ключ. Это выражение генератора будет повторяться только до тех пор, пока это необходимо, чтобы вернуть первое значение:

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

где ddдикт. Будет повышаться, StopIterationесли совпадение не найдено, поэтому вы можете перехватить это и вернуть более подходящее исключение, например ValueErrorили KeyError.

Бывают случаи, когда словарь - это отображение один: один

Например,

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

Ваш подход подходит, если вы выполняете только один поиск. Однако, если вам нужно выполнить более одного поиска, будет более эффективным создать обратный словарь.

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

Если есть вероятность того, что несколько ключей с одинаковым значением, вам нужно будет указать желаемое поведение в этом случае.

Если ваш Python 2.6 или старше, вы можете использовать

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

Эта версия на 26% короче вашей, но работает идентично даже для избыточных / неоднозначных значений (возвращает первое совпадение, как и ваша). Однако он, вероятно, в два раза медленнее, чем ваш, потому что он создает список из dict дважды.

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

Или, если вы предпочитаете краткость удобочитаемости, вы можете сохранить еще один символ с помощью

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

А если вы предпочитаете эффективность, лучше подойдет подход @ PaulMcGuire . Если есть много ключей, которые имеют одно и то же значение, более эффективно не создавать экземпляр этого списка ключей с пониманием списка и вместо этого использовать генератор:

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

Поскольку это все еще очень актуально, первый хит Google, и я просто потратил некоторое время на то, чтобы понять это, я опубликую свое (работающее на 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'

Это даст вам первое совпадающее значение.

Может быть, DoubleDictвам нужен класс, похожий на словарь, такой как ниже? Вы можете использовать любой из предоставленных метаклассов в сочетании с DoubleDictлюбым метаклассом или можете вообще не использовать его.

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

Нет, вы не можете сделать это эффективно, не заглянув во все ключи и не проверив все их значения. Так что O(n)для этого вам понадобится время. Если вам нужно выполнить много таких поисков, вам нужно будет сделать это эффективно, построив перевернутый словарь (можно сделать также в O(n)), а затем выполнить поиск внутри этого перевернутого словаря (каждый поиск будет выполняться в среднем O(1)).

Вот пример того, как построить перевернутый словарь (который сможет выполнять сопоставление от одного ко многим) из обычного словаря:

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)

Например, если ваш

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

ваша h_reversedбудет

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

Насколько мне известно, его нет, но один из способов сделать это - создать диктант для обычного поиска по ключу, а другой - для обратного поиска по значению.

Вот пример такой реализации:

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

Это означает, что поиск ключей для значения может привести к нескольким результатам, которые могут быть возвращены в виде простого списка.

Я знаю, что это можно считать «расточительным», но в этом сценарии я часто сохраняю ключ как дополнительный столбец в записи значения:

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

это компромисс и кажется неправильным, но он прост и работает и, конечно, зависит от значений, являющихся кортежами, а не простыми значениями.

Сделайте обратный словарь

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

Если вам нужно выполнить много обратных поисков

# oneline solution using zip
>> x = {'a':100, 'b':999}
>> y = dict(zip(x.values(), x.keys()))  
>> y
{100: 'a', 999: 'b'}

Через значения в словаре могут быть объектами любого типа, они не могут быть хешированы или проиндексированы другим способом. Так что поиск ключа по значению неестественен для этого типа коллекции. Любой подобный запрос может быть выполнен только за O (n) раз. Поэтому, если это частая задача, вам следует поискать индексацию ключа, например Jon sujjested, или, возможно, даже некоторый пространственный индекс (DB или http://pypi.python.org/pypi/Rtree/ ).

Я использую словари как своего рода «базу данных», поэтому мне нужно найти ключ, который можно использовать повторно. В моем случае, если значение ключа равно None, я могу взять его и повторно использовать без необходимости «выделять» другой идентификатор. Просто подумал, что поделюсь этим.

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]

Мне нравится этот, потому что мне не нужно пытаться отловить какие-либо ошибки, такие как StopIterationили IndexError. Если есть доступный ключ, он free_idбудет содержать его. Если нет, то просто будет None. Наверное, не питонический, но я действительно не хотел использовать tryздесь ...