Обратимый словарь для Python

Похожие сообщения:

обратное отображение Python

Отображения Python 1: 1

Конечно, если все значения и ключи уникальны, не могли бы вы просто использовать один словарь и изначально вставить как ключ: значение, так и значение: ключ?

Если ваши ключи и значения не пересекаются, один из очевидных подходов - просто сохранить их в одном dict. то есть:

class BidirectionalDict(dict):
    def __setitem__(self, key, val):
        dict.__setitem__(self, key, val)
        dict.__setitem__(self, val, key)

    def __delitem__(self, key):
        dict.__delitem__(self, self[key])
        dict.__delitem__(self, key)

d = BidirectionalDict()
d['foo'] = 4
print d[4]   # Prints 'foo'

(Вы также, вероятно, захотите реализовать такие вещи, как методы __init__, update и iter*, чтобы они действовали как настоящий dict, в зависимости от того, сколько функций вам нужно).

Это должно включать только один поиск, хотя может не сэкономить много памяти (в конце концов, у вас все равно вдвое больше записей dict). Однако обратите внимание, что ни этот, ни ваш оригинал не будут занимать вдвое больше места: dict занимает место только для ссылок (фактически указателей), плюс накладные расходы на превышение доступности. Пространство, занимаемое вашими данными, не будет повторяться дважды, поскольку указаны одни и те же объекты.

В «Искусстве компьютерного программирования» в Vokume 3 Knuth есть раздел, посвященный поиску вторичных ключей. Для целей вашего вопроса значение можно рассматривать как вторичный ключ.

Первое предложение - сделать то, что вы сделали: составить эффективный индекс ключей по значению.

Второе предложение - настроить большое b-дерево, которое является составным индексом кластеризованных данных, где узлы ветвления содержат значения, а листья содержат ключевые данные и указатели на более крупную запись (если она есть).

Если данные геометрические (как у вас), есть вещи, называемые почтовыми деревьями. Он может ответить на такие вопросы, как ближайший объект к точке x. Вот несколько примеров: http://simsearch.yury.name/russir/01nncourse-hand.pdf Другой простой вариант для такого рода запросов - дерево квадрантов и дерево kd. http://en.wikipedia.org/wiki/Quadtree

Другой последний вариант - комбинаторное хеширование, при котором вы объединяете ключ и значение в специальный вид хеша, который позволяет вам выполнять эффективный поиск по хешу, даже если у вас нет обоих значений. Я не смог найти в Интернете хорошее объяснение комбинаторного хеша, но оно есть в TAoCP, Volume 3 Second Edition на странице 573.

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

Он не должен использовать «вдвое больше места». Словари просто хранят ссылки на данные, а не сами данные. Итак, если у вас есть миллион строк, занимающих миллиард байтов, то каждый словарь может занять дополнительные 10-20 миллионов байтов - крошечную долю от общего хранилища. Использование двух словарей - это правильно.

Вставьте перевернутую пару (ключ, значение) в один и тот же dict:

a = {1:'a', 2:'b'}
a.update(dict((v, k) for k, v in a.iteritems()))

Тогда вы сможете делать и то, и другое, как вам нужно:

print a[1]
print a['a']

Вот другое решение, использующее определенный пользователем класс.

А код ...

# search a dictionary for key or value
# using named functions or a class
# tested with Python25 by Ene Uran 01/19/2008

def find_key(dic, val):
    """return the key of dictionary dic given the value"""
    return [k for k, v in symbol_dic.iteritems() if v == val][0]

def find_value(dic, key):
    """return the value of dictionary dic given the key"""
    return dic[key]

class Lookup(dict):
    """
    a dictionary which can lookup value by key, or keys by value
    """
    def __init__(self, items=[]):
        """items can be a list of pair_lists or a dictionary"""
        dict.__init__(self, items)

    def get_key(self, value):
        """find the key(s) as a list given a value"""
        return [item[0] for item in self.items() if item[1] == value]

    def get_value(self, key):
        """find the value given a key"""
        return self[key]

Я так делаю уже много лет. Мне лично нравится простота этого решения больше, чем других существующих решений.

d = {1: 'a', 2: 'b'}
dict(zip(d.values(), d.keys()))