Структура данных для сопоставлений 1:1 в python?

Ответ 1

class TwoWay:
    def __init__(self):
       self.d = {}
    def add(self, k, v):
       self.d[k] = v
       self.d[v] = k
    def remove(self, k):
       self.d.pop(self.d.pop(k))
    def get(self, k):
       return self.d[k]

Ответ 2

Другой альтернативой является создание нового класс, который объединяет два словаря, один для каждого вида поиска. Что скорее всего, будет быстрым, но используйте вдвое больше памяти, чем одиночный dict.

Не совсем. Вы оценили это? Поскольку оба словаря будут использовать ссылки на те же объекты как ключи и значения, тогда потраченная память будет просто структурой словаря. Это намного меньше дважды и является фиксированным количеством, независимо от размера вашей информации.

Я имею в виду, что фактические данные не будут скопированы. Таким образом, вы потратили бы небольшую дополнительную память.

Пример:

a = "some really really big text spending a lot of memory"

number_to_text = {1: a}
text_to_number = {a: 1}

Только одна копия "действительно большой" строки существует, поэтому вы в конечном итоге тратите немного больше памяти. Это общедоступно.

Я не могу представить себе решение, в котором у вас будет ключевая скорость поиска при поиске по значению, если вы не потратите хотя бы достаточно памяти для хранения хеш-таблицы обратного поиска (это именно то, что делается в вашем "объединить два решения dict s" ).

Ответ 3

Другой альтернативой является создание нового класса, который объединяет два словаря, по одному для каждого вида поиска. Это, скорее всего, будет использовать вдвое больше памяти, чем один диктов.

Не совсем так, потому что они просто держат две ссылки на одни и те же данные. На мой взгляд, это не плохое решение.

Вы рассматривали поиск базы данных в памяти? Я не уверен, как он будет сравнивать скорость, но поиск в реляционных базах данных может быть очень быстрым.

Ответ 4

Вот мое собственное решение этой проблемы: http://github.com/spenthil/pymathmap/blob/master/pymathmap.py

Цель состоит в том, чтобы сделать его максимально прозрачным для пользователя. Единственным введенным значимым атрибутом является partner.

OneToOneDict подклассы из dict - я знаю, что обычно не рекомендуется, но я думаю, что у меня есть общие случаи использования. Бэкэнд довольно прост, он (dict1) сохраняет слабое значение для "партнера" OneToOneDict (dict2), которое является его обратным. При изменении dict1 dict2 соответственно изменяется и наоборот.

Из docstring:

>>> dict1 = OneToOneDict()
>>> dict2 = OneToOneDict()
>>> dict1.partner = dict2
>>> assert(dict1 is dict2.partner)
>>> assert(dict2 is dict1.partner)
>>> dict1['one'] = '1'
>>> dict2['2'] = '1'
>>> dict1['one'] = 'wow'
>>> assert(dict1 == dict((v,k) for k,v in dict2.items()))
>>> dict1['one'] = '1'
>>> assert(dict1 == dict((v,k) for k,v in dict2.items()))
>>> dict1.update({'three': '3', 'four': '4'})
>>> assert(dict1 == dict((v,k) for k,v in dict2.items()))
>>> dict3 = OneToOneDict({'4':'four'})
>>> assert(dict3.partner is None)
>>> assert(dict3 == {'4':'four'})
>>> dict1.partner = dict3
>>> assert(dict1.partner is not dict2)
>>> assert(dict2.partner is None)
>>> assert(dict1.partner is dict3)
>>> assert(dict3.partner is dict1)
>>> dict1.setdefault('five', '5')
>>> dict1['five']
'5'
>>> dict1.setdefault('five', '0')
>>> dict1['five']
'5'

Когда я получаю свободное время, я намереваюсь сделать версию, которая не хранит вещи дважды. Не знаю, когда это будет:)

Ответ 5

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

Ответ 6

"Мы можем гарантировать, что либо ключ, либо значение (или оба) будут целыми"

Это странно написано - "ключ или значение (или оба)" не кажется правильным. Либо они все целые числа, либо они не все целые числа.

Похоже, что все целые числа.

Или, похоже, вы думаете о замене целевого объекта на целочисленное значение, поэтому у вас есть только один экземпляр, на который ссылается целое число. Это ложная экономика. Просто держите целевой объект. Все объекты Python - в действительности - ссылки. Очень мало фактического копирования делается.

Предположим, что вы просто имеете два целых числа и можете выполнять поиск по одной из пары. Один из способов сделать это - использовать очереди кучи или модуль bisect для поддержки упорядоченных списков целых наборов ключевых значений.

См. http://docs.python.org/library/heapq.html#module-heapq

См. http://docs.python.org/library/bisect.html#module-bisect

У вас есть один набор кортежей heapq (key,value). Или, если ваш основной объект более сложный, кортежи (key,object).

У вас есть еще один набор кортежей heapq (value,key). Или, если ваш основной объект более сложный, кортежи (otherkey,object).

"Вставка" становится двумя вставками, по одному в каждый список, состоящий из heapq.

Ключевой поиск находится в одной очереди; поиск значения находится в другой очереди. Сделайте поиск с помощью bisect(list,item).

Ответ 7

Как использовать sqlite? Просто создайте: memory: database с таблицей с двумя столбцами. Вы даже можете добавлять индексы, а затем запрашивать один из них. Оберните его в класс, если это то, что вы собираетесь использовать много.

Ответ 8

Так получилось, что я все время задаю этот вопрос (вчера, в частности). Я согласен с подходом к созданию двух словарей. Сделайте несколько тестов, чтобы узнать, сколько памяти он принимает. Мне никогда не нужно было изменять его, но вот как я его абстрактно, если он используется:

class BiDict(list):
    def __init__(self,*pairs):
        super(list,self).__init__(pairs)
        self._first_access = {}
        self._second_access = {}
        for pair in pairs:
            self._first_access[pair[0]] = pair[1]
            self._second_access[pair[1]] = pair[0]
            self.append(pair)

    def _get_by_first(self,key):
        return self._first_access[key]

    def _get_by_second(self,key):
        return self._second_access[key]

    # You'll have to do some overrides to make it mutable
    # Methods such as append, __add__, __del__, __iadd__
    # to name a few will have to maintain ._*_access

class Constants(BiDict):
    # An implementation expecting an integer and a string
    get_by_name = BiDict._get_by_second
    get_by_number = BiDict._get_by_first

t = Constants(
        ( 1, 'foo'),
        ( 5, 'bar'),
        ( 8, 'baz'),
    )

>>> print t.get_by_number(5)
bar
>>> print t.get_by_name('baz')
8
>>> print t
[(1, 'foo'), (5, 'bar'), (8, 'baz')]