问题:在Python中进行逆字典查找

通过了解字典中的值,是否有任何简单的方法来找到密钥?

我只能想到的是:

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

Is there any straightforward way of finding a key by knowing the value within a dictionary?

All I can think of is this:

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

回答 0

空无一人。不要忘记,可以在任意数量的键上找到该值,包括0或大于1。

There is none. Don’t forget that the value may be found on any number of keys, including 0 or more than 1.


回答 1

您的列表理解力会遍历所有dict项,找到所有匹配项,然后仅返回第一个键。该生成器表达式将仅迭代到返回第一个值所需的程度:

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

dd字典在哪里。StopIteration如果未找到匹配项,则会加注,因此您可能想捕获该匹配项并返回更合适的异常,例如ValueErrorKeyError

Your list comprehension goes through all the dict’s items finding all the matches, then just returns the first key. This generator expression will only iterate as far as necessary to return the first value:

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

where dd is the dict. Will raise StopIteration if no match is found, so you might want to catch that and return a more appropriate exception like ValueError or KeyError.


回答 2

在某些情况下,字典是一对一映射

例如,

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

There are cases where a dictionary is a one:one mapping

Eg,

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

Your approach is ok if you are only doing a single lookup. However if you need to do more than one lookup it will be more efficient to create an inverse dictionary

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

If there is a possibility of multiple keys with the same value, you will need to specify the desired behaviour in this case.

If your Python is 2.6 or older, you can use

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

回答 3

这个版本比您的版本短26%,但功能相同,即使对于冗余/模棱两可的值(也将返回您的第一个匹配项)。但是,它的速度可能是您的速度的两倍,因为它会两次根据字典创建一个列表。

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

This version is 26% shorter than yours but functions identically, even for redundant/ambiguous values (returns the first match, as yours does). However, it is probably twice as slow as yours, because it creates a list from the dict twice.

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

Or if you prefer brevity over readability you can save one more character with

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

And if you prefer efficiency, @PaulMcGuire’s approach is better. If there are lots of keys that share the same value it’s more efficient not to instantiate that list of keys with a list comprehension and instead use use a generator:

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

回答 4

由于这仍然非常相关,因此我第一次花了点时间解决这个问题,我将发布我的(在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'

它将为您提供第一个匹配的值。

Since this is still very relevant, the first Google hit and I just spend some time figuring this out, I’ll post my (working in Python 3) solution:

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'

It will give you the first value that matches.


回答 5

也许像字典这样的类(如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))

Maybe a dictionary-like class such as DoubleDict down below is what you want? You can use any one of the provided metaclasses in conjuction with DoubleDict or may avoid using any metaclass at all.

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

回答 6

不,如果不查看所有键并检查所有键的值,就无法有效地做到这一点。因此,您将需要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])
}

No, you can not do this efficiently without looking in all the keys and checking all their values. So you will need O(n) time to do this. If you need to do a lot of such lookups you will need to do this efficiently by constructing a reversed dictionary (can be done also in O(n)) and then making a search inside of this reversed dictionary (each search will take on average O(1)).

Here is an example of how to construct a reversed dictionary (which will be able to do one to many mapping) from a normal dictionary:

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)

For example if your

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

your h_reversed will be

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

回答 7

据我所知,还没有一种方法,但是要做的一种方法是创建一个用于按键正常查找的字典,另一个用于按值反向查找的字典。

这里有一个这样的实现示例:

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

这确实意味着在键中查找一个值可能会导致多个结果,这些结果可以作为简单列表返回。

There isn’t one as far as I know of, one way however to do it is to create a dict for normal lookup by key and another dict for reverse lookup by value.

There’s an example of such an implementation here:

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

This does mean that looking up the keys for a value could result in multiple results which can be returned as a simple list.


回答 8

我知道这可能被认为是“浪费的”,但是在这种情况下,我经常将键作为附加列存储在值记录中:

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

这是一个折衷方案,让人感觉错了,但是它很简单而且有效,当然取决于值是元组而不是简单的值。

I know this might be considered ‘wasteful’, but in this scenario I often store the key as an additional column in the value record:

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

it’s a tradeoff and feels wrong, but it’s simple and works and of course depends on values being tuples rather than simple values.


回答 9

制作反向字典

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

如果您要进行很多反向查找

Make a reverse dictionary

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

If you have a lot of reverse lookups to do


回答 10

通过字典中的值可以是任何类型的对象,它们不能以其他方式进行哈希或索引。因此,对于该集合类型,通过值查找键是不自然的。任何类似的查询只能在O(n)时间内执行。因此,如果这是一项经常性的任务,则应该查看一些像Jon sujjested这样的键的索引,或者甚至是一些空间索引(DB或http://pypi.python.org/pypi/Rtree/)。

Through values in dictionary can be object of any kind they can’t be hashed or indexed other way. So finding key by the value is unnatural for this collection type. Any query like that can be executed in O(n) time only. So if this is frequent task you should take a look for some indexing of key like Jon sujjested or maybe even some spatial index (DB or http://pypi.python.org/pypi/Rtree/ ).


回答 11

我将字典用作一种“数据库”,因此我需要找到一个可以重用的密钥。就我而言,如果键的值为None,则可以将其获取并重用,而不必“分配”另一个ID。只是想我会分享。

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]

我喜欢这个,因为我不必尝试捕获任何错误,例如StopIterationIndexError。如果有可用的密钥,free_id则将包含一个。如果没有,那么它将简单地为None。可能不是pythonic,但我真的不想在try这里使用…

I’m using dictionaries as a sort of “database”, so I need to find a key that I can reuse. For my case, if a key’s value is None, then I can take it and reuse it without having to “allocate” another id. Just figured I’d share it.

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]

I like this one because I don’t have to try and catch any errors such as StopIteration or IndexError. If there’s a key available, then free_id will contain one. If there isn’t, then it will simply be None. Probably not pythonic, but I really didn’t want to use a try here…


声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。