Python dict
- очень полезная структура данных:
d = {'a': 1, 'b': 2}
d['a'] # get 1
Иногда вам также нужно индексировать по значениям.
d[1] # get 'a'
Какой самый эффективный способ реализовать эту структуру данных? Любой официальный рекомендуемый способ сделать это?
python
hashtable
bidirectional
Хуанхо Конти
источник
источник
{1: ['a', 'A'], 2: 'b'}
. См. Мой ответ, как это сделать.Ответы:
Вот класс для двунаправленного текста
dict
, вдохновленный поиском ключа из значения в словаре Python и измененный, чтобы разрешить следующие 2) и 3).Обратите внимание, что :
bd.inverse
автоматически обновляется при изменении стандартного dictbd
.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']}
источник
self[key]
в__delitem__()
с помощью одногоvalue = self[key]
назначения, повторно используемого для таких поисков. Но ... да. Это ничтожно мало. Спасибо за чистую крутизну , Basj !Вы можете использовать тот же самый словарь, добавив пару ключ-значение в обратном порядке.
источник
d.update( dict((d[k], k) for k in d) )
.dict((v, k) for (k, v) in d.items())
. В любом случае, вы можете передать пары непосредственно .update:d.update(reversed(i) for i in d.items())
.d={'a':1, 'b':2, 1: 'b'}
dict(map(reversed, a_dict.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
атрибут aBijectiveMap
снова равен aBijectiveMap
. Поэтому вы можете делать такие вещи, как:>>> foo = BijectiveMap() >>> foo['steve'] = 42 >>> foo.inverse {42: 'steve'} >>> foo.inverse.inverse {'steve': 42} >>> foo.inverse.inverse is foo True
источник
К сожалению, самый высоко оцененный ответ
bidict
не работает.Есть три варианта:
Подкласс dict : вы можете создать подкласс
dict
, но будьте осторожны. Вам нужно написать пользовательские реализацииupdate
,pop
,initializer
,setdefault
. Вdict
реализации не называют__setitem__
. Вот почему у самого высоко оцененного ответа есть проблемы.Наследовать от UserDict : это похоже на dict, за исключением того, что все процедуры выполняются правильно. Он использует dict под капотом в элементе с именем
data
. Вы можете прочитать документацию Python или использовать простую реализацию списка направлений, который работает в Python 3 . Извините за то, что не включил его дословно: я не уверен в его авторских правах.Наследование от абстрактных базовых классов : наследование от collections.abc поможет вам получить все правильные протоколы и реализации для нового класса. Это перебор для двунаправленного словаря, если он не может также зашифровать и кэшировать в базе данных.
TL; DR - Используйте это для своего кода. Read Трей Hunner «s статья для деталей.
источник
Примерно так, может быть:
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
источник
dict([('a', 'b'), ('b', 'c')]); dict['b']
->'c'
вместо ключа'a'
.print bd['myvalue2']
вопросb, c
(или[b, c]
, или(b, c)
, или что-нибудь еще)?Во-первых, вы должны убедиться, что соответствие ключей и значений однозначно, иначе построить двунаправленную карту будет невозможно.
Во-вторых, насколько велик набор данных? Если данных не так много, просто используйте 2 отдельные карты и обновляйте их обе при обновлении. Или лучше использовать существующее решение, такое как Bidict , которое представляет собой просто оболочку из двух слов, со встроенным обновлением / удалением.
Но если набор данных большой и поддержка двух диктовок нежелательна:
Если и ключ, и значение являются числовыми, рассмотрите возможность использования интерполяции для аппроксимации сопоставления. Если подавляющее большинство пар ключ-значение может быть охвачено функцией сопоставления (и ее
обратной функцией), то вам нужно только записать выбросы в карты.
Если большая часть доступа является однонаправленной (ключ-> значение), то вполне нормально построить обратную карту постепенно, чтобы обменивать время на
пространство.
Код:
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]
источник