Python dict - очень полезная структура данных:
d = {'a': 1, 'b': 2}
d['a'] # get 1
Иногда вам также нужно индексировать по значениям.
d[1] # get 'a'
Какой самый эффективный способ реализовать эту структуру данных? Любой официальный рекомендовать способ сделать это?
Вот класс для двунаправленного текста dict, вдохновленный поиском ключа по значению в словаре Python и измененный, чтобы разрешить следующие 2) и 3).
Обратите внимание:
bd.inverse автоматически обновляется при изменении стандартного dict bd.bd.inverse[value] всегда представляет собой список из key, такой что bd[key] == value.bidict из https://pypi.python.org/pypi/bidict, здесь мы можем иметь 2 ключа одинакового значения, это очень важно.Код:
class bidict(dict):
def __init__(self, *args, **kwargs):
super(bidict, self).__init__(*args, **kwargs)
self.inverse = {}
for key, value in self.items():
self.inverse.setdefault(value,[]).append(key)
def __setitem__(self, key, value):
if key in self:
self.inverse[self[key]].remove(key)
super(bidict, self).__setitem__(key, value)
self.inverse.setdefault(value,[]).append(key)
def __delitem__(self, key):
self.inverse.setdefault(self[key],[]).remove(key)
if self[key] in self.inverse and not self.inverse[self[key]]:
del self.inverse[self[key]]
super(bidict, self).__delitem__(key)
Пример использования:
bd = bidict({'a': 1, 'b': 2})
print(bd) # {'a': 1, 'b': 2}
print(bd.inverse) # {1: ['a'], 2: ['b']}
bd['c'] = 1 # Now two keys have the same value (= 1)
print(bd) # {'a': 1, 'c': 1, 'b': 2}
print(bd.inverse) # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print(bd) # {'a': 1, 'b': 2}
print(bd.inverse) # {1: ['a'], 2: ['b']}
del bd['a']
print(bd) # {'b': 2}
print(bd.inverse) # {2: ['b']}
bd['b'] = 3
print(bd) # {'b': 3}
print(bd.inverse) # {2: [], 3: ['b']}
Вы можете использовать тот же самый dict, добавив пару ключей, значение в обратном порядке.
d={'a':1,'b':2}
revd=dict([reversed(i) for i in d.items()])
d.update(revd)
Двунаправленная хеш-таблица бедного человека должна была бы использовать только два словаря (это уже настроенные структуры данных).
В индексе также есть bidict пакет:
Источник для bidict можно найти в github:
Ниже фрагмент кода реализует обратимое (биективное) отображение:
class BijectionError(Exception):
"""Must set a unique value in a BijectiveMap."""
def __init__(self, value):
self.value = value
msg = 'The value "{}" is already in the mapping.'
super().__init__(msg.format(value))
class BijectiveMap(dict):
"""Invertible map."""
def __init__(self, inverse=None):
if inverse is None:
inverse = self.__class__(inverse=self)
self.inverse = inverse
def __setitem__(self, key, value):
if value in self.inverse:
raise BijectionError(value)
self.inverse._set_item(value, key)
self._set_item(key, value)
def __delitem__(self, key):
self.inverse._del_item(self[key])
self._del_item(key)
def _del_item(self, key):
super().__delitem__(key)
def _set_item(self, key, value):
super().__setitem__(key, value)
Преимущество этой реализации заключается в том, что атрибут inverse для BijectiveMap снова является BijectiveMap. Поэтому вы можете делать такие вещи, как:
>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True
Что-то вроде этого, может быть:
import itertools
class BidirDict(dict):
def __init__(self, iterable=(), **kwargs):
self.update(iterable, **kwargs)
def update(self, iterable=(), **kwargs):
if hasattr(iterable, 'iteritems'):
iterable = iterable.iteritems()
for (key, value) in itertools.chain(iterable, kwargs.iteritems()):
self[key] = value
def __setitem__(self, key, value):
if key in self:
del self[key]
if value in self:
del self[value]
dict.__setitem__(self, key, value)
dict.__setitem__(self, value, key)
def __delitem__(self, key):
value = self[key]
dict.__delitem__(self, key)
dict.__delitem__(self, value)
def __repr__(self):
return '%s(%s)' % (type(self).__name__, dict.__repr__(self))
Вам нужно решить, что вы хотите, если более одного ключа имеет заданное значение; двунаправленность данной пары может быть легко скроена какой-либо более поздней парой, которую вы вставили. Я реализовал один из возможных вариантов.
Пример:
bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1'] # a
print bd['myvalue2'] # b
Во-первых, вы должны убедиться, что ключ для сопоставления значений один к одному, в противном случае невозможно построить двунаправленную карту.
Во-вторых, насколько велик набор данных? Если данных не так много, просто используйте 2 отдельных карты и обновляйте их оба при обновлении. Или лучше, используйте существующее решение, например Bidict, которое представляет собой всего лишь оболочку из 2-х диктов, с встроенным обновлением/удалением.
Но если набор данных большой, а поддержка 2 dicts нежелательна:
Если оба ключа и значение являются числовыми, рассмотрите возможность использования Интерполяция для аппроксимации отображения. Если подавляющее большинство пары ключ-значение могут быть покрыты функцией отображения (и ее обратная функция), тогда вам нужно только записать выбросы на картах.
Если большая часть доступа является однонаправленной (key- > value), то она полностью
ok, чтобы построить обратную карту постепенно, чтобы торговать временем для
пространство.
код:
d = {1: "one", 2: "two" }
reverse = {}
def get_key_by_value(v):
if v not in reverse:
for _k, _v in d.items():
if _v == v:
reverse[_v] = _k
break
return reverse[v]