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

Если ваши ключи и значения не пересекаются, один из очевидных подходов - просто сохранить их в одном 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 есть раздел поиска вторичных ключей. Для целей вашего вопроса значение можно рассматривать как вторичный ключ.

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

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

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

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

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

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

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

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

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

Вставить перевернутую пару (ключ, значение) в один и тот же 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]

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