Pencarian kamus terbalik dengan Python

Adakah cara mudah untuk menemukan kunci dengan mengetahui nilainya di dalam kamus?

Yang bisa saya pikirkan hanyalah ini:

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

Tidak ada. Jangan lupa bahwa nilainya dapat ditemukan di sejumlah kunci, termasuk 0 atau lebih dari 1.

Pemahaman daftar Anda melewati semua item dict menemukan semua kecocokan, lalu mengembalikan kunci pertama. Ekspresi generator ini hanya akan mengulang sejauh yang diperlukan untuk mengembalikan nilai pertama:

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

dimana dddikt. Akan meningkat StopIterationjika tidak ada kecocokan yang ditemukan, jadi Anda mungkin ingin menangkapnya dan mengembalikan pengecualian yang lebih sesuai seperti ValueErroratau KeyError.

Ada beberapa kasus di mana kamus adalah pemetaan satu: satu

Misalnya,

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

Pendekatan Anda tidak masalah jika Anda hanya melakukan satu pencarian. Namun jika Anda perlu melakukan lebih dari satu pencarian, akan lebih efisien untuk membuat kamus terbalik

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

Jika ada kemungkinan beberapa kunci dengan nilai yang sama, Anda perlu menentukan perilaku yang diinginkan dalam kasus ini.

Jika Python Anda 2.6 atau lebih tua, Anda bisa menggunakan

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

Versi ini 26% lebih pendek dari versi Anda tetapi fungsinya sama, bahkan untuk nilai yang berlebihan / ambigu (mengembalikan kecocokan pertama, seperti milik Anda). Namun, ini mungkin dua kali lebih lambat dari Anda, karena ini membuat daftar dari dict dua kali.

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

Atau jika Anda lebih suka singkat daripada keterbacaan, Anda dapat menyimpan satu karakter lagi dengan

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

Dan jika Anda lebih suka efisiensi, pendekatan @ PaulMcGuire lebih baik. Jika ada banyak kunci yang memiliki nilai yang sama, lebih efisien untuk tidak membuat contoh daftar kunci tersebut dengan pemahaman daftar dan sebagai gantinya gunakan generator:

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

Karena ini masih sangat relevan, Google hit pertama dan saya hanya meluangkan waktu untuk mencari tahu, saya akan memposting solusi saya (bekerja dengan 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'

Ini akan memberi Anda nilai pertama yang cocok.

Mungkin kelas seperti kamus seperti DoubleDictdi bawah ini yang Anda inginkan? Anda dapat menggunakan salah satu dari metaclass yang disediakan sehubungan dengan DoubleDictatau mungkin menghindari penggunaan metaclass sama sekali.

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

Tidak, Anda tidak dapat melakukan ini secara efisien tanpa melihat semua kunci dan memeriksa semua nilainya. Jadi, Anda perlu O(n)waktu untuk melakukan ini. Jika Anda perlu melakukan banyak pencarian seperti itu, Anda perlu melakukan ini secara efisien dengan membuat kamus terbalik (dapat juga dilakukan di O(n)) dan kemudian melakukan pencarian di dalam kamus terbalik ini (setiap pencarian akan mengambil rata-rata O(1)).

Berikut adalah contoh bagaimana membuat kamus terbalik (yang akan dapat melakukan pemetaan satu ke banyak) dari kamus 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)

Misalnya jika Anda

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

Anda h_reversedakan menjadi

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

Sejauh yang saya tahu, tidak ada satu pun, namun satu cara untuk melakukannya adalah dengan membuat dikt untuk pencarian normal berdasarkan kunci dan dikt lain untuk pencarian terbalik berdasarkan nilai.

Ada contoh penerapan seperti itu di sini:

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

Ini berarti bahwa mencari kunci untuk suatu nilai dapat menghasilkan banyak hasil yang dapat dikembalikan sebagai daftar sederhana.

Saya tahu ini mungkin dianggap 'boros', tetapi dalam skenario ini saya sering menyimpan kunci sebagai kolom tambahan dalam catatan nilai:

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

itu tradeoff dan terasa salah, tetapi sederhana dan berhasil dan tentu saja tergantung pada nilai-nilai menjadi tuple daripada nilai-nilai sederhana.

Buat kamus terbalik

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

Jika Anda memiliki banyak pencarian terbalik yang harus dilakukan

Melalui nilai dalam kamus dapat berupa objek apa pun yang tidak dapat di-hash atau diindeks dengan cara lain. Jadi, menemukan kunci berdasarkan nilainya tidaklah wajar untuk jenis koleksi ini. Setiap query seperti itu dapat dijalankan hanya dalam waktu O (n). Jadi jika ini adalah tugas yang sering Anda harus melihat beberapa pengindeksan kunci seperti Jon sujjested atau bahkan beberapa indeks spasial (DB atau http://pypi.python.org/pypi/Rtree/ ).

Saya menggunakan kamus sebagai semacam "database", jadi saya perlu menemukan kunci yang dapat saya gunakan kembali. Untuk kasus saya, jika nilai kunci adalah None, maka saya dapat mengambilnya dan menggunakannya kembali tanpa harus "mengalokasikan" id lain. Hanya berpikir saya akan membagikannya.

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]

Saya suka yang ini karena saya tidak perlu mencoba dan menangkap kesalahan seperti StopIterationatau IndexError. Jika ada kunci yang tersedia, maka free_idakan berisi satu. Jika tidak ada, maka itu akan terjadi None. Mungkin bukan pythonic, tapi saya benar-benar tidak ingin menggunakan a di trysini ...