Структура данных для отображений 1: 1 в Python?

Question

У меня проблема, которая требует обратимого 1: 1 сопоставления ключей со значениями.

Это означает, что иногда я хочу найти значение по ключу, но иногда я хочу найти ключ по значению. И ключи, и значения гарантированы уникальными.

x = D[y]
y == D.inverse[x]

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

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

Так есть ли лучшая структура, которую я могу использовать?

• Мое приложение требует, чтобы это было очень быстро и использовало как можно меньше памяти.
• Структура должна быть изменчивой, и очень желательно, чтобы изменение объекта не вызывало его замедления (например, для принудительного полного переиндексации)
• Мы можем гарантировать, что либо ключ, либо значение (или оба) будут целыми числами
• Вероятно, структура понадобится для хранения тысяч или, возможно, миллионов предметов.
• Ключи и Valus гарантированно будут уникальными, то есть len (set (x)) == len (x) для для x в [D.keys (), D.valuies ()]

Answer 1

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

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

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

Пример:

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

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

Существует только одна копия «действительно большой» строки, так что в итоге вы тратите чуть больше памяти. Обычно это доступно.

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

Answer 2

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]

Answer 3

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

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

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

Answer 4

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

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

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

Из строки документации:

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

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

Answer 5

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

Answer 6

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

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

Звучит так, будто все они целые.

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

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

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

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

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

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

«Вставка» становится двумя вставками, по одному в каждый список со структурой heapq.

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

Answer 7

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

Answer 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')]