Реверсивный словарь для python

Я хотел бы сохранить некоторые данные в Python в аналогичной форме со словарем: {1:'a', 2:'b'} . Каждое значение будет уникальным, не только среди других значений, но и среди клавиш.

Есть ли простая структура данных, которую я могу использовать для получения соответствующего объекта, независимо от того, спрашиваю я, используя «ключ» или «значение»? Например:

 >>> a = {1:'a', 2:'b'} >>> a[1] 'a' >>> a['b'] 2 >>> a[3] KeyError 

«Ключи» являются стандартными наборами python, значениями являются короткие (<256char) строки.

Мое текущее решение – создание словаря с переводом и поиск его, если я не могу найти результат в оригинальном словаре:

 pointsreversed = dict((v, k) for k, v in points.iteritems()) def lookup(key): return points.get(key) or pointsreversed.key() 

Это использует в два раза больше места, что не очень удобно (мои словари могут составлять до нескольких сотен мегабайт) и в среднем на 50% медленнее.

EDIT: как упоминалось в нескольких ответах, два dicts не используют двойное использование памяти, так как это только словарь, а не элементы внутри, это дублирование.

Есть ли решение, которое улучшает это?

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

Отображение 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). Обратите внимание, однако, что ни этот, ни ваш оригинал не будут использовать в два раза больше места: диктофон занимает только место для ссылок (эффективно указатели), а также накладные расходы на общую занятость. Пространство, занятое вашими данными, не будет повторяться дважды, поскольку на него указывают те же объекты.

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

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

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

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

Еще один окончательный вариант – комбинаторное хеширование, в котором вы объединяете ключ и значение в специальный вид хеша, который позволяет вам эффективно искать хеш, даже если у вас нет обоих значений. Я не мог найти хорошее комбинаторное хеш-объяснение онлайн, но он находится в TAoCP, том 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]