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

Question

Я хотел бы сохранить некоторые данные в 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: как упоминалось в нескольких ответах, два диктофона не используют двойное использование памяти, поскольку это только словарь, а не элементы внутри, то есть дублирование.

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

Answer 1

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

Python mapping inverse

Python 1:1 mappings

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

Answer 2

Вставка обратной пары (ключ, значение) в то же Словаре:

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

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

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

Answer 3

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

Answer 4

Это another solution с использованием класса, определенного пользователем.

И код ...

# 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] 

Answer 5

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

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

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

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

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

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

Answer 6

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