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

Question

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

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

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

'Ключи' - это стандартные значения Python, а значения - короткие (<256чар) строки. </p>

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

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

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

РЕДАКТИРОВАТЬ: как уже упоминалось в нескольких ответах, два диктата не удваивают использование памяти, поскольку дублирование - это только словарь, а не элементы внутри.

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

Answer 1

Если ваши ключи и значения не накладываются друг на друга, один очевидный подход заключается в том, чтобы просто хранить их в одном и том же файле. то есть:

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

И код ...

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

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

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

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

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