Odwrotne przeszukiwanie słownika w Pythonie


102

Czy istnieje prosty sposób na znalezienie klucza poprzez znajomość wartości w słowniku?

Myślę tylko o tym:

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



Google poprowadziło mnie tutaj ... I muszę powiedzieć ... dlaczego nikt nie używa, iteritemsjak dla mnie, to robi 40x szybszą różnicę ... używając metody () .next
Angry 84

4
Jeśli masz dużo odwrotnych wyszukiwań do zrobienia:reverse_dictionary = {v:k for k,v in dictionary.items()}
Austin,

Odpowiedzi:


5

Nie ma żadnego. Nie zapominaj, że wartość można znaleźć na dowolnej liczbie kluczy, w tym 0 lub więcej niż 1.


2
python ma metodę .index na listach, która zwraca pierwszy znaleziony indeks z określoną wartością lub wyjątek, jeśli nie został znaleziony ... czy jest jakiś powód, dla którego takiej semantyki nie można zastosować do słowników?
Brian Jack

@BrianJack: Słowniki nie są uporządkowane, tak jak zestawy. Spójrz na collections.OrderedDict dla implementacji, które zamówione.
Martijn Pieters

3
.index musi tylko zagwarantować, że zwraca pojedynczą wartość i nie musi być najpierw leksykalnie, tylko że jest to pierwsze dopasowanie i że jego zachowanie jest stabilne (wielokrotne wywołania tego samego dict w czasie powinny dawać ten sam pasujący element). O ile słowniki nie zmieniają kolejności swoich niezmodyfikowanych skrótów w czasie, gdy inne elementy są dodawane, usuwane lub modyfikowane, nadal działałyby odpowiednio. Naiwna implementacja: dictObject.items (). Index (key)
Brian Jack

chodzi głównie o .Index () jest to, że z definicji nie dbamy o duplikaty tylko, że możemy patrzeć pojedynczy element konsekwentnie
Brian Jack

130
Brzydzę się takimi brakami odpowiedzi. „Przestań próbować robić to, co słusznie chcesz!” jest nie do zaakceptowania odpowiedź. Dlaczego zostało to zaakceptowane? Jak świadczą wyżej ocenione odpowiedzi na to pytanie, odwrotne wyszukiwanie słownika można w trywialny sposób zaimplementować w mniej niż 80 znakach czystego języka Python. Nie ma nic bardziej „prostego” niż to. Paul McGuire „s rozwiązanie jest prawdopodobnie najbardziej skuteczny, ale wszystkie prace. </sigh>
Cecil Curry

95

Twoja lista składa się z wszystkich elementów dykta, znajdując wszystkie dopasowania, a następnie zwraca pierwszy klucz. To wyrażenie generatora będzie iterować tylko tak daleko, jak to konieczne, aby zwrócić pierwszą wartość:

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

gdzie ddjest dyktando. Podniesie, StopIterationjeśli nie zostanie znalezione dopasowanie, więc możesz chcieć to złapać i zwrócić bardziej odpowiedni wyjątek, taki jak ValueErrorlub KeyError.


1
Tak Powinien prawdopodobnie zgłosić ten sam wyjątek co listObject.index (klucz), gdy klucza nie ma na liście.
Brian Jack,

7
również, keys = { key for key,value in dd.items() if value=='value' }aby uzyskać zestaw wszystkich kluczy, jeśli kilka pasuje.
askewchan

6
@askewchan - nie ma prawdziwej potrzeby zwracania tego jako zestawu, klucze dyktowania muszą już być unikalne, po prostu zwracają listę - lub lepiej, zwracają wyrażenie generatora i pozwól wywołującemu umieścić je w dowolnym kontenerze.
PaulMcG

55

Są przypadki, w których słownik jest jeden: jedno mapowanie

Na przykład,

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

Twoje podejście jest w porządku, jeśli wykonujesz tylko jedno wyszukiwanie. Jeśli jednak potrzebujesz wykonać więcej niż jedno wyszukiwanie, skuteczniejsze będzie utworzenie słownika odwrotnego

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

Jeśli istnieje możliwość, że wiele kluczy ma tę samą wartość, w tym przypadku należy określić żądane zachowanie.

Jeśli Twój Python jest w wersji 2.6 lub starszej, możesz użyć

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

6
Niezła optymalizacja. Ale myślę, że chciałeś zamienić swoją listę 2-krotek w słownik za pomocą dict ():ivd=dict([(v,k) for (k,v) in d.items()])
płyty grzewcze

4
@hobs po prostu użyj słowa ze zrozumieniem zamiast rozumienia listy:invd = { v:k for k,v in d.items() }
askewchan

Zrozumienia @gnibbler dict nie zostały przeniesione z powrotem do Pythona 2.6, więc jeśli chcesz zachować przenośność, musisz znosić 6 dodatkowych znaków dla dict () wokół generatora 2-krotek lub listy składającej się z 2 -krotki
płyty kuchenne

@hobs, dodałem to do mojej odpowiedzi.
John La Rooy

32

Ta wersja jest o 26% krótsza od twojej, ale działa identycznie, nawet dla zbędnych / niejednoznacznych wartości (zwraca pierwsze dopasowanie, tak jak twoja). Jest jednak prawdopodobnie dwa razy wolniejszy niż twój, ponieważ dwukrotnie tworzy listę na podstawie dyktowania.

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

Lub jeśli wolisz zwięzłość niż czytelność, możesz zapisać jeszcze jedną postać

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

A jeśli wolisz wydajność, podejście @ PaulMcGuire jest lepsze. Jeśli istnieje wiele kluczy, które mają tę samą wartość, bardziej efektywne jest nie tworzenie instancji tej listy kluczy ze zrozumieniem listy i zamiast tego użyć generatora:

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

2
Zakładając niepodzielną operację, czy gwarantuje się, że klucze i wartości są w tej samej odpowiedniej kolejności?
Noctis Skytower

1
@NoctisSkytower Tak, dict.keys()i dict.values()gwarantujemy, że będą korespondować, o ile dictnie będą mutowane między połączeniami.
płyty grzewcze

7

Ponieważ jest to nadal bardzo istotne, pierwsze trafienie Google i spędziłem trochę czasu na zastanowieniu się nad tym, opublikuję moje rozwiązanie (działające w Pythonie 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'

Otrzymasz pierwszą pasującą wartość.


6

Może chcesz uzyskać klasę podobną do słownika, taką jak DoubleDictponiżej? Możesz użyć dowolnej z dostarczonych metaklas w połączeniu z DoubleDictdowolną metaklasą lub możesz w ogóle jej uniknąć.

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

4

Nie, nie można tego skutecznie zrobić bez zaglądania do wszystkich kluczy i sprawdzania wszystkich ich wartości. Będziesz więc potrzebował O(n)czasu, aby to zrobić. Jeśli potrzebujesz wykonać wiele takich wyszukiwań, będziesz musiał to zrobić efektywnie, konstruując odwrócony słownik (można to również zrobić w O(n)), a następnie przeszukując ten odwrócony słownik (każde wyszukiwanie zajmie średnio O(1)).

Oto przykład, jak skonstruować odwrócony słownik (który będzie w stanie wykonać jedno do wielu mapowań) ze zwykłego słownika:

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)

Na przykład, jeśli twój

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

twoja h_reversedwola

{
  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

O ile mi wiadomo, nie ma takiego, jednak jednym ze sposobów jest utworzenie dyktu do normalnego wyszukiwania według klucza, a drugim do wyszukiwania wstecznego według wartości.

Oto przykład takiej implementacji:

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

Oznacza to, że wyszukiwanie kluczy pod kątem wartości może skutkować wieloma wynikami, które można zwrócić jako prostą listę.


Zwróć uwagę, że istnieje wiele, wiele możliwych wartości, które nie są prawidłowymi kluczami.
Ignacio Vazquez-Abrams

1

Wiem, że można to uznać za `` marnotrawstwo '', ale w tym scenariuszu często przechowuję klucz jako dodatkową kolumnę w rekordzie wartości:

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

jest to kompromis i wydaje się zły, ale jest prosty i działa i oczywiście zależy od wartości będących krotkami, a nie prostymi wartościami.


1

Stwórz słownik zwrotny

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

Jeśli masz dużo do zrobienia odwrotnego wyszukiwania


Działa to tylko wtedy, gdy istnieje mapowanie 1: 1 między kluczami i wartościami.
Noel Yap

0

Wartości w słowniku mogą być obiektami dowolnego rodzaju, których nie można haszować ani indeksować w inny sposób. Zatem znajdowanie klucza według wartości jest nienaturalne dla tego typu kolekcji. Każde takie zapytanie może zostać wykonane tylko w czasie O (n). Więc jeśli jest to częste zadanie, powinieneś spojrzeć na indeksowanie klucza, takiego jak Jon Sujjested, a może nawet indeks przestrzenny (DB lub http://pypi.python.org/pypi/Rtree/ ).


-1

Używam słowników jako pewnego rodzaju „bazy danych”, więc muszę znaleźć klucz, którego będę mógł ponownie użyć. W moim przypadku, jeśli wartość klucza to None, mogę go wziąć i ponownie użyć bez konieczności „przydzielania” innego identyfikatora. Pomyślałem, że się tym podzielę.

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]

Podoba mi się ten, ponieważ nie muszę próbować wyłapywać żadnych błędów, takich jak StopIterationlub IndexError. Jeśli jest dostępny klucz, free_idbędzie go zawierał. Jeśli nie, to po prostu będzie None. Prawdopodobnie nie pythoniczne, ale naprawdę nie chciałem trytutaj używać ...

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.