Обратный поиск по словарю в Python - PullRequest
80 голосов
/ 02 апреля 2010

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

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

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

Ответы [ 14 ]

76 голосов
/ 03 апреля 2010

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

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

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

46 голосов
/ 03 апреля 2010

В некоторых случаях словарь представляет собой одно: одно отображение

Например,

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())
30 голосов
/ 26 июля 2012

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

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

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

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

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

key = (key for key, value in dict_obj.items() if value == 'value').next()
16 голосов
/ 02 апреля 2010

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

5 голосов
/ 12 февраля 2016

Так как это все еще очень актуально, первый хит 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'

Это даст вам первое значение, которое соответствует.

5 голосов
/ 24 июля 2012

Может быть, вам нужен словарный класс, такой как 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))
2 голосов
/ 21 ноября 2014

Нет, вы не можете сделать это эффективно, не просматривая все ключи и не проверяя все их значения. Так что вам понадобится 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])
}
2 голосов
/ 02 апреля 2010

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

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

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

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

0 голосов
/ 30 июня 2018

Создать обратный словарь. Затем выполните обычный поиск.

Пример обратного просмотра телефонной книги:

normDic = {'KVOTHE':['789-2583']
        ,'DENNA':['987-6453']}

revDic = {'789-2583':['KVOTHE']
        ,'987-6453':['DENNA']}

numInput = str(input('Enter number:\n>>'))

if numInput in revDic:
    print('Contact found:', revDic[numInput], numInput)
0 голосов
/ 12 октября 2017

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

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.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...