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

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

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

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

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

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

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

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

8 Solutions collect form web for “Структура данных для сопоставлений 1: 1 в python?”

 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] 

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

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

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

Пример:

 a = "some really really big text spending a lot of memory" number_to_text = {1: a} text_to_number = {a: 1} 

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

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

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

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

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

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

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

Подклассы OneToOneDict из dict – я знаю, что обычно не рекомендуется , но я думаю, что у меня есть общие случаи использования. dict1 довольно прост, он ( 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' 

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

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

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

Это странно написано – «ключ или значение (или оба)» не чувствуют себя хорошо. Либо они все целые числа, либо они не все целые числа.

Похоже, что они целые.

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

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

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

 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')] 
  • Существует ли стандартная структура данных Python, которая хранит вещи в отсортированном порядке?
  • Как реализовано set ()?
  • Хранение функций в словаре
  • Python - вычисляет функции многомерной вероятности плотности на большом наборе данных?
  • Создайте список, подобный объекту, используя bitarray
  • Лучшая структура данных для трехмерных данных?
  • Структура данных для хранения табличных данных в памяти?
  • Префикс поиска с полмиллиарда строк
  •  
    Interesting Posts for Van-Lav

    Интеграция AppEngine Paypal дает SSLCertificateError на localhost, используя Python

    Загрузка файла фрейма django rest с вложенными перезаписываемыми сериализаторами

    В диктовке dicts, как вы эмулируете поведение Auto-vivification Perl?

    Как заблокировать все соединение SQLite (заблокированное чтение + заблокированная запись)?

    Как я могу получить исходный код функции Python?

    архитектура django npm и узлов

    Можно ли выпустить «VACUUM ANALYZE <tablename>» из psycopg2 или sqlalchemy для PostgreSQL?

    Python argparse: введите несоответствия при объединении «вариантов», «nargs» и «default»,

    Сортировка имен файлов в каталоге в порядке возрастания

    Python: все месяцы?

    Python – проверка того, является ли один список подмножеством другого

    Модуль «trace» не имеет атрибута «modname» при попытке отладки в PyCharm (Python 3.6)

    Словарь с множественными ключами, где порядок ключей не имеет значения

    Сценарий проверки носа с аргументами командной строки

    MySQL Connector / Python InterfaceError: «Не удалось разобрать пакет EOF»

    Python - лучший язык программирования в мире.