Как реализовать эффективную двунаправленную хеш-таблицу?

86

Python dict- очень полезная структура данных:

d = {'a': 1, 'b': 2}

d['a'] # get 1

Иногда вам также нужно индексировать по значениям.

d[1] # get 'a'

Какой самый эффективный способ реализовать эту структуру данных? Любой официальный рекомендуемый способ сделать это?

Хуанхо Конти
источник
Если хотите, мы можем предположить, что значения неизменны, как и ключи.
Juanjo Conti,
4
Что бы вы ответили на этот диктат: {'a': 1, 'b': 2, 'A': 1}
PaulMcG
2
@PaulMcGuire: Я бы вернулся {1: ['a', 'A'], 2: 'b'}. См. Мой ответ, как это сделать.
Basj
4
Примечание модератору: это не дубликат stackoverflow.com/questions/1456373/two-way-reverse-map . Последний имеет 1) очень расплывчатую формулировку 2) нет MCVE 3) касается только случая биективной карты (см. Первый комментарий в этом вопросе), что намного более ограничительно, чем этот фактический вопрос, который является более общим. Поэтому я считаю, что в данном конкретном случае отметка как дубликат вводит в заблуждение. Если действительно один должен быть дубликатом другого, должно быть наоборот, поскольку этот здесь охватывает общий случай, тогда как другой (см. Ответы) не охватывает небиективный случай.
Basj

Ответы:

68

Вот класс для двунаправленного текста dict, вдохновленный поиском ключа из значения в словаре Python и измененный, чтобы разрешить следующие 2) и 3).

Обратите внимание, что :

  • 1) Обратный каталог bd.inverse автоматически обновляется при изменении стандартного dict bd.
  • 2) обратный каталог bd.inverse[value] всегда список из keyтаких , что bd[key] == value.
  • 3) В отличие от 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']}
Basj
источник
2
Очень изящное решение неоднозначного дела!
Тобиас Кинцлер
2
Я считаю, что эта структура данных очень полезна во многих практических задачах.
0xc0de
6
Это феноменально. Это лаконично; самодокументируется; это достаточно эффективно; это просто работает. Моя единственная придирка заключалась в том, чтобы оптимизировать повторяющиеся поиски self[key]в __delitem__()с помощью одного value = self[key]назначения, повторно используемого для таких поисков. Но ... да. Это ничтожно мало. Спасибо за чистую крутизну , Basj !
Cecil Curry
1
Как насчет версии Python 3?
zelusp
1
Мне нравится этот ответ для примера. Принятый ответ по-прежнему верен, и я думаю, что принятый ответ должен оставаться принятым ответом, но это немного более ясно для его определения самостоятельно, просто потому, что в нем четко указано, что для переворота словаря вы должны поместить обратный значений в список, поскольку не может быть сопоставления «один-к-одному», потому что словарь имеет отношение «один-ко-многим» с парами «ключ-значение».
searchchengine27
41

Вы можете использовать тот же самый словарь, добавив пару ключ-значение в обратном порядке.

d = {'a': 1, 'b': 2}
revd = dict ([перевернуто (i) для i в d.items ()])
d.update (revd)
Эмиль
источник
5
+1 Красивое, практичное решение. Другой способ написать это: d.update( dict((d[k], k) for k in d) ).
FMc
4
+1 За аккуратное использование перевернутого (). Я не уверен, читабельнее ли это, чем явное dict((v, k) for (k, v) in d.items()). В любом случае, вы можете передать пары непосредственно .update: d.update(reversed(i) for i in d.items()).
Бени Чернявский-Паскин
22
Обратите внимание , это не удается , например , дляd={'a':1, 'b':2, 1: 'b'}
Tobias Kienzler
3
Незначительное изменение: dict(map(reversed, a_dict.items())).
0xc0de
13
Добавление обратных отображений к исходному словарю - ужасная идея. Как показывают приведенные выше комментарии, делать это не безопасно в общем случае. Просто поддерживайте два отдельных словаря. Однако, поскольку первые две строки этого ответа, игнорирующие трейлинг d.update(revd), великолепны, я все еще думаю о голосовании. Давайте подумаем об этом.
Cecil Curry
36

Двунаправленная хеш-таблица для бедняков будет использовать всего два словаря (это уже хорошо настроенные структуры данных).

В индексе также есть пакет bidict :

Исходный код для bidict можно найти на github:

мику
источник
1
2 dicts требует двойных вставок и удалений.
Juanjo Conti,
12
@Juanjo: почти любая двунаправленная / обратимая хеш-таблица будет включать «двойные вставки и удаления», либо как часть реализации структуры, либо как часть ее использования. Ведение двух индексов - действительно единственный быстрый способ сделать это, AFAIK.
Walter Mundt
7
Конечно; Я имел в виду, что проблема с индексом 2 вручную - это проблема.
Juanjo Conti,
1
@Basj Я думаю, что это правильно, что это не принято, поскольку наличие более одного значения означает, что это больше не взаимно однозначное соответствие и неоднозначно для обратного поиска.
user193130
1
@Basj Что ж, я понимаю, что были бы варианты использования, в которых было бы полезно иметь более одного значения для каждого ключа, поэтому, возможно, этот тип структуры данных должен существовать как подкласс двунаправленного текста. Однако, поскольку нормальный dict сопоставляется с одним объектом, я думаю, что гораздо разумнее, чтобы обратное тоже было таким же. (Чтобы уточнить, хотя значение также может быть коллекцией, я имел в виду, что ключ первого dict должен быть того же типа, что и значение обратного dict)
user193130
4

Приведенный ниже фрагмент кода реализует обратимую (биективную) карту:

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атрибут a BijectiveMapснова равен a BijectiveMap. Поэтому вы можете делать такие вещи, как:

>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True
JME
источник
2

К сожалению, самый высоко оцененный ответ bidictне работает.

Есть три варианта:

  1. Подкласс dict : вы можете создать подкласс dict, но будьте осторожны. Вам нужно написать пользовательские реализации update, pop, initializer, setdefault. В dictреализации не называют __setitem__. Вот почему у самого высоко оцененного ответа есть проблемы.

  2. Наследовать от UserDict : это похоже на dict, за исключением того, что все процедуры выполняются правильно. Он использует dict под капотом в элементе с именем data. Вы можете прочитать документацию Python или использовать простую реализацию списка направлений, который работает в Python 3 . Извините за то, что не включил его дословно: я не уверен в его авторских правах.

  3. Наследование от абстрактных базовых классов : наследование от collections.abc поможет вам получить все правильные протоколы и реализации для нового класса. Это перебор для двунаправленного словаря, если он не может также зашифровать и кэшировать в базе данных.

TL; DR - Используйте это для своего кода. Read Трей Hunner «s статья для деталей.

Чарльз Мерриам
источник
1

Примерно так, может быть:

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        
Мэтт Андерсон
источник
1
Я не уверен, что это проблема, но, используя приведенную выше реализацию, не возникнет ли проблем, если ключи и значения будут перекрываться? Так что dict([('a', 'b'), ('b', 'c')]); dict['b']-> 'c'вместо ключа 'a'.
tgray
1
Это не проблема для примера OP, но может быть хорошим отказом от ответственности.
tgray
Как мы можем ответить на этот print bd['myvalue2']вопрос b, c(или [b, c], или (b, c), или что-нибудь еще)?
Basj
0

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

Во-вторых, насколько велик набор данных? Если данных не так много, просто используйте 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]
NeoWang
источник